Skip to main content
SpringerLink
Log in

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

  • Published:
Journal of Logic, Language and Information Aims and scope Submit manuscript

Abstract

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 (Bourreau et al. 2012), 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(L), 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(L) 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(MCFL) is not a full AFL, where \(\mathbf {MCFL}\) denotes the class of multiple context-free languages, closing an open question in Bourreau et al. (2012). More importantly, our proof gives an insight into the relation between the non-closure under inverse homomorphism of \(\mathbf {IO(MCFL)}\) and how IO-substitution breaks semilinearity.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Notes

  1. For readers familiar with the \(\lambda \)-calculus, the precise conditions under which a letter on which an IO-substitution is performed can be renamed are similar to the \(\alpha \)-equivalence on \(\lambda \)-terms: variables can be renamed under the constraint that no other variable is “captured” by this renaming. We do not detail such constraints in the present work. The analogy with \(\lambda \)-calculus is made explicit in (Bourreau et al. 2012).

  2. Such a strict convention is to be compared with Barendregt’s convention on variables in the \(\lambda \)-calculus.

  3. The corresponding version of this lemma is given as the factorization lemma in Fischer (1968a). We use a different name as we already used the terminology of factorization in Sect. 3.2.

References

  • Bourreau, P. (2013). Traitement d’ellipses: Deux approches par les grammaires catégorielles abstraites. In Actes de Traitement Automatique du Langage Naturel—TALN 2013.

  • Bourreau, P., Kallmeyer, L., & Salvati, S. (2012). On IO-copying and mildly-context sensitive formalisms. In Proceedings of Formal Grammar 2012.

  • Chomsky, N. (1956). Three models for the description of language. IRE Transactions on Information Theory, 2, 113–124.

    Article  Google Scholar 

  • Culy, C. (1987). The complexity of the vocabulary of bambara. In W. Savitch, E. Bach, W. Marsh, & G. Safran-Naveh (Eds.), The formal complexity of natural language, Studies in linguistics and philosophy (Vol. 33, pp. 349–357). Netherlands: Springer.

    Chapter  Google Scholar 

  • Damm, W. (1982). The IO- and OI-hierarchies. Theoretical Computer Science, 20, 95–207.

    Article  Google Scholar 

  • de Groote, P. (2001). Towards abstract categorial grammars. In Proceedings of the conference on Association for computational linguistics, 39th Annual meeting and 10th conference of the European chapter, pp. 148–155.

  • Fischer, M. J. (1968a). Grammars with macro-like productions. Ph.D. thesis, Harvard University.

  • Fischer, M. J. (1968b). Grammars with macro-like productions. In IEEE conference record of 9th annual symposium on switching and automata theory, pp. 131–142.

  • Huybregts, R. (1984). The weak inadequacy of context-free phrase structure grammars. In Van Preferie naar Kern, pp. 81–90.

  • Joshi, A. K. (1985). Tree-adjoining grammars: How much context-sensitivity is required to provide reasonable strucutral descriptions? In Natural language parsing: psychological, computational and theoretical perspectives, pp. 206–250.

  • Kallmeyer, L. (2010). On mildly context-sensitive non-linear rewriting. Research on Language and Computation, 8(2), 341–363.

    Article  Google Scholar 

  • Kobele, G. M. (2006). Generating Copies: An investigation into structural identity in language and grammar. Ph.D. thesis, UCLA.

  • Kobele, G. M. (2007). Parsing ellipsis. Unpublished Manuscript.

  • Michaelis, J. (1998). Derivational minimalism is mildly context-sensitive. In M. Moortgat (Ed.), LACL, Lecture Notes in Computer Science (Vol. 2014, pp. 179–198). Berlin: Springer.

    Google Scholar 

  • Michaelis, J. & Kracht, M. (1997). Semilinearity as a syntactic invariant. In Proceedings of logical aspects of computational linguistics.

  • Muskens, R. (2001). Lambda Grammars and the syntax-semantics interface. In van Rooy, R. & Stokhof, M., (Eds.), Proceedings of the thirteenth amsterdam colloquium, (pp. 150–155). North-Holland: Amsterdam

  • Radzinski, D. (1990). Unbounded syntactic copying in mandarin chinese. Linguistics and Philosophy, 13(1), 113–127.

    Article  Google Scholar 

  • Salvati, S. & Kobele, G. (2013). The IO and OI hierarchies revisited. In Proceedings of the 40th international colloquium on automata, languages and programming (to be published)

  • Sarkar, A. & Joshi, A. (1996). Coordination in tree adjoining grammars: Formalization and implementation. In Proceedings of the 16th conference on Computational linguistics, COLING’96 (Vol. 2, pp. 610–615), Stroudsburg, PA: Association for Computational Linguistics.

  • Seki, H., Matsamura, T., Mamoru, F., & Kasami, T. (1991). On multiple context-free grammars. Theoretical Computer Science, 88(2), 191–229.

    Article  Google Scholar 

  • Shieber, S. (1985). Evidence against the context-freeness of natural language. Linguistic and Philosophy, 8, 333–343.

    Article  Google Scholar 

  • Stabler, E. P. (1996). Derivational minimalism. In Retoré, C., (Ed.), LACL, Lecture Notes in Computer Science, (Vol. 1328, pp. 68–95). Berlin: Springer.

  • Vijay-Shanker, K., Weir, D. J., & Joshi, A. K. (1987). Characterizing structural descriptions produced by various grammatical formalisms. In Proceedings of the 25th annual meeting of the association for computational linguistics, Stanford.

Download references

Acknowledgments

This work was funded by the Deutsche Forchungsgemeinschaft, under the project SFB 991 “Die Struktur von Repräsentationen in Sprache, Kognition und Wissenschaft”. I am thankful to Sylvain Salvati for the motivating discussions on this topic; to Laura Kallmeyer for her insights on the notions of universally-linear sets; and to Christian Wurm who helped me to improve the formal definitions with his feedbacks. The responsibility for any mistakes contained herein rests solely on me.

Author information

Authors and Affiliations

  1. Institut für Sprache und Information, Heine-Heinrich Universität Düsseldorf, Universitätstr. 1, 40225, Düsseldorf, Germany

    Pierre Bourreau

Authors
  1. Pierre Bourreau
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pierre Bourreau.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bourreau, P. On the Effect of the IO-Substitution on the Parikh Image of Semilinear Full AFLs. J of Log Lang and Inf 24, 1–26 (2015). https://doi.org/10.1007/s10849-014-9211-2

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10849-014-9211-2

Keywords

Search

Navigation