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.
|