nLab semilinearity

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.