Language equations

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14310%2F21%3A00123159" target="_blank" >RIV/00216224:14310/21:00123159 - isvavai.cz</a>
Result on the web
<a href="https://www.ems-ph.org/books/show_abstract.php?proj_nr=248&vol=1&rank=21" target="_blank" >https://www.ems-ph.org/books/show_abstract.php?proj_nr=248&vol=1&rank=21</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4171/Automata-1/21" target="_blank" >10.4171/Automata-1/21</a>

Result language
angličtina
Original language name
Language equations
Original language 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.
Czech name
—
Czech description
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Book/collection name
Handbook of Automata Theory: Volume I. Theoretical Foundations Volume II. Automata in Mathematics and Selected Applications
ISBN
9783985470068
Number of pages of the result
35
Pages from-to
765-799
Number of pages of the book
1608
Publisher name
European Mathematical Society Publishing House
Place of publication
Berlin
UT code for WoS chapter
—

Similar results(10)