Computer Science – Computation and Language
Scientific paper
1997-07-22
Computer Science
Computation and Language
36pp., uses AMS-LaTeX, tree-dvips, natbib
Scientific paper
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.
No associations
LandOfFree
On Cloning Context-Freeness does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Cloning Context-Freeness, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Cloning Context-Freeness will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-700132