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. (shrink)

Four different kinds of grammars that can define crossing dependencies in human language are compared here: (i) context sensitive rewrite grammars with rules that depend on context, (ii) matching grammars with constraints that filter the generative structure of the language, (iii) copying grammars which can copy structures of unbounded size, and (iv) generating grammars in which crossing dependencies are generated from a finite lexical basis. Context sensitive rewrite grammars are syntactically, semantically and computationally unattractive. Generating grammars have a collection of (...) nice properties that ensure they define only “mildly context sensitive” languages, and Joshi has proposed that human languages have those properties too. But for certain distinctive kinds of crossing dependencies in human languages, copying or matching analyses predominate. Some results relevant to the viability of mildly context sensitive analyses and some open questions are reviewed. (shrink)