nLab semilinearity

Contents

Contents

Idea

The definition of semilinearity first appeared in Parikh’s theorem Parikh (1961) and has then gained significance in linguistics.

Definition

A formal grammar is semilinear if the languages it generates are regular when forgetting the order.

References

  • Rohit J Parikh. Language generating devices. Quarterly Progress Report, 60:199–212, 1961.
  • Jens Michaelis and Marcus Kracht. Semilinearity as a syntactic invariant. In Jaime G. Carbonell, J¨org Siekmann, G. Goos, J. Hartmanis, J. van Leeuwen, and Christian Retor´e, editors, Logical Aspects of Computational Linguistics, volume 1328, pages 329–345. Springer Berlin Heidelberg, Berlin, Heidelberg, 1997.

Last revised on November 24, 2020 at 17:41:44. See the history of this page for a list of all contributions to it.