On Cloning Context-Freeness
<|reference_start|>On Cloning Context-Freeness: 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.<|reference_end|>
@article{moennich1997on,
    title={On Cloning Context-Freeness},
    author={Uwe Moennich (Tuebingen University/SfS)},
    journal={arXiv preprint arXiv:cmp-lg/9707013},
    year={1997},
    number={Arbeitspapiere des SFB 340, Bericht Nr. 114},
    archivePrefix={arXiv},
    eprint={cmp-lg/9707013},
    primaryClass={cmp-lg cs.CL}
}