# Masarykova univerzita

Informace o publikaci

# Language equations

Autoři OKHOTIN Alexander 2021 Kapitola v knize 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.

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.