Journal of Logic, Language and Information 24 (1):1-26 (2015)
AbstractBack in the 1980’s, the class of mildly context-sensitive formalisms was introduced so as to capture the syntax of natural languages. While the languages generated by such formalisms are constrained by the constant-growth property, the most well-known and used ones—like tree-adjoining grammars or multiple context-free grammars—generate languages which verify the stronger property of being semilinear. In, the operation of IO-substitution was created so as to exhibit mildly-context sensitive classes of languages which are not semilinear. In the present article, we extend the notion of semilinearity, and characterize the Parikh image of the languages in IO, the closure of a class L of semilinear languages under IO-substitution, as universally-semilinear. Based on this result and on the work of Fischer on macro-grammars, we then show that IO is not closed under inverse homomorphism when L is closed under inverse homomorphism, and encompasses the class of regular languages. This result proves that IO is not a full AFL, where \ denotes the class of multiple context-free languages, closing an open question in Bourreau et al.. More importantly, our proof gives an insight into the relation between the non-closure under inverse homomorphism of \}\) and how IO-substitution breaks semilinearity
Similar books and articles
Highly constrained unification grammars.Daniel Feinstein & Shuly Wintner - 2008 - Journal of Logic, Language and Information 17 (3):345-381.
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.
Contexts and the Concept of Mild Context-Sensitivity.M. Kudlek, C. Martín-Vide, A. Mateescu & V. Mitrana - 2003 - Linguistics and Philosophy 26 (6):703 - 725.
Global index grammars and descriptive power.José M. Castaño - 2004 - Journal of Logic, Language and Information 13 (4):403-419.
Second-order abstract categorial grammars as hyperedge replacement grammars.Makoto Kanazawa - 2010 - Journal of Logic, Language and Information 19 (2):137-161.
Two Models of Minimalist, Incremental Syntactic Analysis.Edward P. Stabler - 2013 - Topics in Cognitive Science 5 (3):611-633.
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.
Product-free Lambek calculus and context-free grammars.Mati Pentus - 1997 - Journal of Symbolic Logic 62 (2):648-660.
A descriptive characterisation of linear languages.Tore Langholm - 2006 - Journal of Logic, Language and Information 15 (3):233-250.
Formal languages defined by the underlying structure of their words.J. P. Ressayre - 1988 - Journal of Symbolic Logic 53 (4):1009-1026.
Extended Pregroup Grammars Applied to Natural Languages.Aleksandra Kiślak-Malinowska - 2012 - Logic and Logical Philosophy 21 (3):229-252.
Added to PP
Historical graph of downloads
Citations of this work
No citations found.
References found in this work
Review on "Three Models for the Description of Language" by Noam Chomsky. [REVIEW]Lars Svenonius - 1956 - Journal of Symbolic Logic 23 (1):71-72.
Evidence against the context-freeness of natural language.Stuart M. Shieber - 1985 - Linguistics and Philosophy 8 (3):333 - 343.
The complexity of the vocabulary of bambara.Christopher Culy - 1985 - Linguistics and Philosophy 8 (3):345 - 351.
Lambda Grammars and the Syntax-Semantics Interface.Reinhard Muskens - 2001 - In Robert Van Rooij & Martin Stokhof (eds.), Proceedings of the Thirteenth Amsterdam Colloquium. Amsterdam: ILLC. pp. 150-155.
Three Models for the Description of Language.N. Chomsky - 1956 - IRE Transactions on Information Theory 2:113-124.