David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
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)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
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):345-381.
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. [REVIEW] Journal of Logic, Language and Information 13 (4):421-438.
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 downloads6 ( #230,125 of 1,410,123 )
Recent downloads (6 months)1 ( #177,589 of 1,410,123 )
How can I increase my downloads?