Informace o publikaci
Language equations
| Autoři | |
|---|---|
| Rok publikování | 2021 |
| Druh | Kapitola v knize |
| Fakulta / Pracoviště MU | |
| Citace | |
| Popis | 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. |