Další formáty:
BibTeX
LaTeX
RIS
@article{1641256,
author = {Klíma, Ondřej and Polák, Libor},
article_location = {AMSTERDAM},
article_number = {DEC 31 2019},
doi = {http://dx.doi.org/10.1016/j.tcs.2019.10.020},
keywords = {Regular languages; Minimal automaton; Syntactic monoid},
language = {eng},
issn = {0304-3975},
journal = {Theoretical Computer Science},
title = {Syntactic structures of regular languages},
url = {https://doi.org/10.1016/j.tcs.2019.10.020},
volume = {800},
year = {2019}
}
TY - JOUR
ID - 1641256
AU - Klíma, Ondřej - Polák, Libor
PY - 2019
TI - Syntactic structures of regular languages
JF - Theoretical Computer Science
VL - 800
IS - DEC 31 2019
SP - 125-141
EP - 125-141
PB - North Holland
SN - 03043975
KW - Regular languages
KW - Minimal automaton
KW - Syntactic monoid
UR - https://doi.org/10.1016/j.tcs.2019.10.020
L2 - https://doi.org/10.1016/j.tcs.2019.10.020
N2 - Given a regular language, its canonical lattice automaton is defined - this is a modification of the notions of the minimal automaton and the canonical meet automaton of the language. Secondly, the concept of the syntactic lattice algebra is introduced as an analogy of the syntactic monoid and of the syntactic semiring. The above three syntactic structures are constructed as certain transformation algebras of the corresponding automata. This leads to a unified approach to the study of syntactic structures of regular languages. The basic properties of the new notions are stated, showing, among others, the minimality of the canonical lattice automaton and the minimality of the syntactic lattice algebra. Using the syntactic lattice algebra, a new characterization of the membership problem for reversible languages is given.
ER -
KLÍMA, Ondřej a Libor POLÁK. Syntactic structures of regular languages. \textit{Theoretical Computer Science}. AMSTERDAM: North Holland, 2019, roč.~800, DEC 31 2019, s.~125-141. ISSN~0304-3975. Dostupné z: https://dx.doi.org/10.1016/j.tcs.2019.10.020.
|
