On Cloning Context-Freeness
| dc.creator | Moennich, Uwe | |
| dc.date | 1997-07-22 | |
| dc.date.accessioned | 2026-07-07T09:10:55Z | |
| dc.date.available | 2026-07-07T09:10:55Z | |
| dc.description | To Rogers (1994) we owe the insight that monadic second order predicate logic with multiple successors (MSO) is well suited in many respects as a realistic formal base for syntactic theorizing. However, the agreeable formal properties of this logic come at a cost: MSO is equivalent with the class of regular tree automata/grammars, and, thereby, with the class of context-free languages. This paper outlines one approach towards a solution of MSO's expressivity problem. On the background of an algebraically refined Chomsky hierarchy, which allows the definition of several classes of languages--in particular, a whole hierarchy between CF and CS--via regular tree grammars over unambiguously derivable alphabets of varying complexity plus their respective yield-functions, it shows that not only some non-context-free string languages can be captured by context-free means in this way, but that this approach can be generalized to the corresponding structures. I.e., non-recognizable sets of structures can--up to homomorphism--be coded context-freely. Since the class of languages covered--Fischer's (1968} OI family of indexed languages--includes all attested instances of non-context-freeness in natural language, there exists an indirect, to be sure, but completely general way to formally describe the natural languages using a weak framework like MSO. | |
| dc.description | 36pp., uses AMS-LaTeX, tree-dvips, natbib | |
| dc.identifier | https://arxiv.org/abs/cmp-lg/9707013 | |
| dc.identifier | http://arxiv.org/abs/cmp-lg/9707013 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/151501 | |
| dc.subject | Computation and Language | |
| dc.title | On Cloning Context-Freeness | |
| dc.type | text |