Journal of Logic, Language and Information 15 (3):233-250 (2006)
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||Descriptive complexity Linear languages Greibach normal form|
|Categories||categorize this paper)|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Natural Languages and Context-Free Languages.Geoffrey K. Pullum & Gerald Gazdar - 1980 - Linguistics and Philosophy 4 (4):471 - 504.
Product-Free Lambek Calculus and Context-Free Grammars.Mati Pentus - 1997 - Journal of Symbolic Logic 62 (2):648-660.
Highly Constrained Unification Grammars.Daniel Feinstein & Shuly Wintner - 2008 - Journal of Logic, Language and Information 17 (3):345-381.
An Analysis of Gödel's Dialectica Interpretation Via Linear Logic.Paulo Oliva - 2008 - Dialectica 62 (2):269–290.
On the Expressive Power of Abstract Categorial Grammars: Representing Context-Free Formalisms. [REVIEW]Philippe de Groote & Sylvain Pogodalla - 2004 - Journal of Logic, Language and Information 13 (4):421-438.
Formal Languages Defined by the Underlying Structure of Their Words.J. P. Ressayre - 1988 - Journal of Symbolic Logic 53 (4):1009-1026.
The Equivalence of Tree Adjoining Grammars and Monadic Linear Context-Free Tree Grammars.Stephan Kepser & Jim Rogers - 2011 - Journal of Logic, Language and Information 20 (3):361-384.
Added to index2009-01-28
Total downloads15 ( #309,090 of 2,154,061 )
Recent downloads (6 months)1 ( #398,005 of 2,154,061 )
How can I increase my downloads?