Language equations

C 2021

Language equations

KUNC, Michal a Alexander OKHOTIN

Základní údaje

Originální název

Language equations

Autoři

KUNC, Michal a Alexander OKHOTIN

Vydání

Berlin, Handbook of Automata Theory: Volume I. Theoretical Foundations Volume II. Automata in Mathematics and Selected Applications, od s. 765-799, 35 s. 2021

Nakladatel

European Mathematical Society Publishing House

Další údaje

Jazyk

angličtina

Typ výsledku

Kapitola resp. kapitoly v odborné knize

Obor

10101 Pure mathematics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Odkazy

URL

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14310/21:00123159

Organizační jednotka

Přírodovědecká fakulta

ISBN

978-3-98547-006-8

DOI

https://doi.org/10.4171/Automata-1/21

Klíčová slova anglicky

Language equations; formal grammars; computability

Štítky

rivok

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 9. 12. 2021 11:01, Mgr. Marie Novosadová Šípková, DiS.

Anotace

V originále

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.

Citovat

KUNC, Michal a Alexander OKHOTIN. Language equations. In Jean-Éric Pin. Handbook of Automata Theory: Volume I. Theoretical Foundations Volume II. Automata in Mathematics and Selected Applications. Berlin: European Mathematical Society Publishing House, 2021, s. 765-799. ISBN 978-3-98547-006-8. Dostupné z: https://doi.org/10.4171/Automata-1/21.

@inbook{1808041,
   author = {Kunc, Michal and Okhotin, Alexander},
   address = {Berlin},
   booktitle = {Handbook of Automata Theory: Volume I. Theoretical Foundations Volume II. Automata in Mathematics and Selected Applications},
   doi = {https://doi.org/10.4171/Automata-1/21},
   editor = {Jean-Éric Pin},
   keywords = {Language equations; formal grammars; computability},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Berlin},
   isbn = {978-3-98547-006-8},
   pages = {765-799},
   publisher = {European Mathematical Society Publishing House},
   title = {Language equations},
   url = {https://www.ems-ph.org/books/show_abstract.php?proj_nr=248&vol=1&rank=21},
   year = {2021}
}

TY  - CHAP
ID  - 1808041
AU  - Kunc, Michal - Okhotin, Alexander
PY  - 2021
TI  - Language equations
VL  - Neuveden
PB  - European Mathematical Society Publishing House
CY  - Berlin
SN  - 9783985470068
KW  - Language equations
KW  - formal grammars
KW  - computability
UR  - https://www.ems-ph.org/books/show_abstract.php?proj_nr=248&vol=1&rank=21
N2  - 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.
ER  -

KUNC, Michal a Alexander OKHOTIN. Language equations. In Jean-Éric Pin. \textit{Handbook of Automata Theory: Volume I. Theoretical Foundations Volume II. Automata in Mathematics and Selected Applications}. Berlin: European Mathematical Society Publishing House, 2021, s.~765-799. ISBN~978-3-98547-006-8. Dostupné z: https://doi.org/10.4171/Automata-1/21.

Přehled o publikaci