On the effect of the IO-substitution on the Parikh image of semilinear full AFLs

DOI10.1007/S10849-014-9211-2zbMATH Open1362.68129arXiv1311.0632OpenAlexW2047752295MaRDI QIDQ302175FDOQ302175

Authors: Pierre Bourreau 

Publication date: 4 July 2016

Published in: Journal of Logic, Language and Information (Search for Journal in Brave)

Abstract: Back in the 80s, 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 mildly-context sensitive formalisms, like tree-adjoining grammars or multiple context-free grammars, generate languages which verify the stronger property of being semilinear. In (Bourreau et al., 2012), the operation of IO-ubstitution was created so as to exhibit mildly context-sensitive classes of languages which are not semilinear, although they verify the constant-growth property. In the present article, we extend the notion of semilinearity, and characterise the Parikh image of the IO-MCFLs (i.e. languages which belong to the closure of MCFLs under IO-subsitution) as universally-linear. Based on this result and on the work of Fischer on macro-grammars, we then show IO-MCFLs are not closed under inverse homomorphism, which proves that the family of IO-MCFLs is not an abstract family of languages.

Full work available at URL: https://arxiv.org/abs/1311.0632

Recommendations

• On IO-copying and mildly-context sensitive formalisms
• On multiple context-free grammars
• Linear context-free tree languages and inverse homomorphisms
• Linear context-free tree languages and inverse homomorphisms
• An inverse homomorphic characterization of full principal AFL

zbMATH Keywords

formal languagesabstract family of languagesconstant-growthIO macro-grammarsmildly context-sensitive formalismsmultiple context-free grammarssemilinearity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Three models for the description of language
• The IO- and OI-hierarchies
• On multiple context-free grammars
• Title not available (Why is that?)
• Derivational minimalism
• Title not available (Why is that?)
• On IO-copying and mildly-context sensitive formalisms
• The IO and OI hierarchies revisited

Cited In (1)

• On IO-copying and mildly-context sensitive formalisms

This page was built for publication: On the effect of the IO-substitution on the Parikh image of semilinear full AFLs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q302175)