Semilinearity as a syntactic invariant | SpringerLink
Skip to main content
Springer Nature Link
Log in

Semilinearity as a syntactic invariant

  • Conference paper
  • First Online:
Logical Aspects of Computational Linguistics (LACL 1996)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 1328))

Abstract

Mildly context sensitive grammar formalisms such as multi-component TAGs and linear context free rewrite systems have been introduced to capture the full complexity of natural languages. We show that, in a formal sense, Old Georgian can be taken to provide an example of a non-semilinear language. This implies that none of the aforementioned grammar formalisms is strong enough to generate this language.

This paper has been worked out at the University of Potsdam within the Innovationskolleg ‘Formale Modelle kognitiver Komplexität’ (INKII/A 12) funded by the Deutsche Forschungsgemeinschaft (DFG). We have benefitted largely from discussions with Annius Groenink. Many thanks also to Winfried Boeder for his help concerning Old Georgian, and to two anonymous referees for fixing up severed of the “very non-English” formulations within the preceeding version of this paper.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Winfried Boeder. Suffixaufnahme in Kartvelian. In [12], pages 151–215.

    Google Scholar 

  2. M. A. Browning. Bounding conditions on representations. Linguistic Inquiry 22:541–562, 1991.

    Google Scholar 

  3. Nick Evans. Multiple-case in Kayardild: Anti-iconic suffix ordering and the diachronic filter. In [12], pages 396–428.

    Google Scholar 

  4. Seymour Ginsburg and Edwin H. Spanier. Bounded ALGOL-like languages. Transactions of the American Mathematical Society, 113:333–368, 1964.

    Article  MathSciNet  Google Scholar 

  5. Annius V. Groenink. Mild context-sensitivity and tuple-based generalizations of context-free grammar. In D. E. Johnson and L. S. Moss, editors, Special Issue on the Mathematics of Language, Linguistics and Philosophy, forthcoming. Also available as Report CS-R9634, Centrum voor Wiskunde en Informatica (CWI), Amsterdam, 1996.

    Google Scholar 

  6. Riny Huybregts. The weak inadequacy of context-free phrase structure grammars. In G. de Haan, M. Trommelen, and W. Zonneveld, editors, Van Periferie naar Kern, pages 81–99. Foris Publications, Dordrecht, 1984.

    Google Scholar 

  7. Aravind K. Joshi. Tree adjoinig grammars: How much context-sensitivity is required to provide reasonable structural descriptions? In D. Dowty, L. Karttunen, and A. Zwicky, editors, Natural Language Parsing. Theoretical, Computational and Psychological Perspective, pages 206–250. Cambridge University Press, New York, 1985.

    Google Scholar 

  8. Aravind K. Joshi, K. Vijay-Shanker, and David J. Weir. The convergence of mildly context-sensitive grammar formalisms. In P. Sells, S. Shieber, and T. Wasow, editors, Foundational Issues in Natural Language Processing, pages 31–81. MIT Press, Cambridge (Mass.), 1991.

    Google Scholar 

  9. Alexis Manaster-Ramer. Dutch as a formal language. Linguistics and Philosophy, 10:221–246, 1987.

    Article  Google Scholar 

  10. Rohit J. Parikh. On context-free languages. Journal of the Association for Computing Machinery, 13:570–581, 1966.

    MATH  MathSciNet  Google Scholar 

  11. Frans Plank. (Re-)introducing Suffixaufnahme. In [12], pages 3–110.

    Google Scholar 

  12. Frans Plank, editor. Double Case. Agreement by Suffixaufnahme. Oxford University Press, New York, 1995.

    Google Scholar 

  13. Daniel Radzinski. Chinese number-names, tree adjoining languages, and mild context-sensitivity. Computational Linguistics, 17:277–299, 1991.

    Google Scholar 

  14. Owen Rambow. Formal and Computational Aspects of Natural Language Syntax. PhD thesis, University of Pennsylvania, Philadelphia, PA, 1994.

    Google Scholar 

  15. K. Vijay-Shanker and David J. Weir. The equivalence of four extensions of context-free grammars. Mathematical Systems Theory, 27:511–546, 1994.

    Article  MathSciNet  Google Scholar 

  16. David J. Weir. Characterizing Mildly Context-Sensitive Grammar Formalisms. PhD thesis, University of Pennsylvania, Philadelphia, PA, 1988.

    Google Scholar 

  17. Kenneth Wexler and Peter W. Culicover. Formal Principles of Language Aquisition. MIT Press, Cambridge (Mass.), 1980.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Linguistik/Innovationskolleg, Universität Potsdam, Postfach 60 15 53, D-14415, Potsdam

    Jens Michaelis

  2. II. Mathematisches Institut, Freie Universität Berlin, Arnimallee 3, D-14195, Berlin

    Marcus Kracht

Authors
  1. Jens Michaelis
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marcus Kracht
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Christian Retoré

Rights and permissions

Reprints and permissions

Copyright information

© 1997 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Michaelis, J., Kracht, M. (1997). Semilinearity as a syntactic invariant. In: Retoré, C. (eds) Logical Aspects of Computational Linguistics. LACL 1996. Lecture Notes in Computer Science, vol 1328. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0052165

Download citation

  • DOI: https://doi.org/10.1007/BFb0052165

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-63700-4

  • Online ISBN: 978-3-540-69631-5

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation