On the Effect of the IO-Substitution on the Parikh Image of Semilinear Full AFLs

Journal of Logic, Language and Information 24 (1):1-26 (2015)
  Copy   BIBTEX


Back 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



    Upload a copy of this work     Papers currently archived: 76,363

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Highly constrained unification grammars.Daniel Feinstein & Shuly Wintner - 2008 - Journal of Logic, Language and Information 17 (3):345-381.
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.
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.
Learning correction grammars.Lorenzo Carlucci, John Case & Sanjay Jain - 2009 - Journal of Symbolic Logic 74 (2):489-516.


Added to PP

8 (#988,891)

6 months
2 (#299,675)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

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.

View all 6 references / Add more references