A descriptive characterisation of linear languages
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) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,705 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesGeoffrey 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.
Analytics
Monthly downloads |
Added to index2009-01-28Total downloads4 ( #178,800 of 549,196 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
