Journal of Logic, Language and Information 15 (3) (2006)
|Abstract||Lautemann et al. (1995) gave a descriptive characterisation of the class of context-free languages, showing that a language is context-free iff it is definable as the set of words satisfying some sentence of a particular logic (fragment) over words. The present notes discuss how to specialise this result to the class of linear languages. Somewhat surprisingly, what would seem the most straightforward specialisation actually fails, due to the fact that linear grammars fail to admit a Greibach normal form. We identify an alternative specialisation, based on an alternative characterisation of context-free languages, also noted by Lautemann et al. (1995).|
|Keywords||No keywords specified (fix it)|
|Through your library||Configure|
Similar books and articles
Geoffrey K. Pullum & Gerald Gazdar (1982). Natural Languages and Context-Free Languages. Linguistics and Philosophy 4 (4):471 - 504.
Mati Pentus (1997). Product-Free Lambek Calculus and Context-Free Grammars. Journal of Symbolic Logic 62 (2):648-660.
Daniel Feinstein & Shuly Wintner (2008). Highly Constrained Unification Grammars. Journal of Logic, Language and Information 17 (3).
Paulo Oliva (2008). An Analysis of Gödel's Dialectica Interpretation Via Linear Logic. Dialectica 62 (2):269–290.
Philippe de Groote & Sylvain Pogodalla (2004). On the Expressive Power of Abstract Categorial Grammars: Representing Context-Free Formalisms. Journal of Logic, Language and Information 13 (4).
J. P. Ressayre (1988). Formal Languages Defined by the Underlying Structure of Their Words. Journal of Symbolic Logic 53 (4):1009-1026.
Stephan Kepser & Jim Rogers (2011). The Equivalence of Tree Adjoining Grammars and Monadic Linear Context-Free Tree Grammars. Journal of Logic, Language and Information 20 (3):361-384.
Added to index2009-01-28
Total downloads4 ( #178,800 of 549,196 )
Recent downloads (6 months)0
How can I increase my downloads?