Publication details
Language equations
| Authors | |
|---|---|
| Year of publication | 2021 |
| Type | Chapter of a book |
| MU Faculty or unit | |
| Citation | |
| Description | Equations with formal languages as unknowns naturally appear whenever sets of words are being used. In particular, they are fundamental for the theory of formal grammars, with systems of equations of the form $X_i=\varphi(X_1, \ldots, X_n)$ representing the inductive nature of the context-free grammars and their natural variants. Some variants of these systems naturally represent finite automata and a basic class of cellular automata. Equations of the general form are notable for their computational completeness, with universal computation encoded in extremely simple examples. The chapter provides a survey of the known results on language equations, classifying them according to the methods of research, and comparing similar properties of different families. |