| KLÍMA, Ondřej a Libor POLÁK. Forbidden patterns for ordered automata. Journal of Automata, Languages and Combinatorics. Institut fur Informatik, Justus-Liebig-Universitat Giessen, 2020, roč. 25, 2-3, s. 141-169. ISSN 1430-189X. Dostupné z: https://dx.doi.org/10.25596/jalc-2020-141. |
Další formáty:
BibTeX
LaTeX
RIS
@article{1710536,
author = {Klíma, Ondřej and Polák, Libor},
article_number = {2-3},
doi = {http://dx.doi.org/10.25596/jalc-2020-141},
keywords = {deterministic automata; varieties of regular languages; varieties of automata},
language = {eng},
issn = {1430-189X},
journal = {Journal of Automata, Languages and Combinatorics},
title = {Forbidden patterns for ordered automata},
url = {https://www.jalc.de/issues/2020/issue_25_2-3/jalc-2020-141-169.php},
volume = {25},
year = {2020}
}
TY - JOUR
ID - 1710536
AU - Klíma, Ondřej - Polák, Libor
PY - 2020
TI - Forbidden patterns for ordered automata
JF - Journal of Automata, Languages and Combinatorics
VL - 25
IS - 2-3
SP - 141-169
EP - 141-169
PB - Institut fur Informatik, Justus-Liebig-Universitat Giessen
SN - 1430189X
KW - deterministic automata
KW - varieties of regular languages
KW - varieties of automata
UR - https://www.jalc.de/issues/2020/issue_25_2-3/jalc-2020-141-169.php
L2 - https://www.jalc.de/issues/2020/issue_25_2-3/jalc-2020-141-169.php
N2 - The contribution concerns decision procedures in the algebraic theory of regular lan-guages. Among others, various versions of forbidden patterns or configurations in automata are treated in the existing literature. Basically, one looks for certain subgraphs of the minimal automaton of a given language to decide whether this language does not belong to a given significant class of regular languages. We survey numerous known examples and we build a general theory covering the most of familiar ones. The chosen formalism differs from existing ones and the generalization to ordered automata enables us to reformulate some of known examples in a uniform shape. We also describe certain sufficient assumptions on the forbidden pattern which ensure that the corresponding class of languages forms a robust class in the sense of natural closure properties.
ER -
KLÍMA, Ondřej a Libor POLÁK. Forbidden patterns for ordered automata. \textit{Journal of Automata, Languages and Combinatorics}. Institut fur Informatik, Justus-Liebig-Universitat Giessen, 2020, roč.~25, 2-3, s.~141-169. ISSN~1430-189X. Dostupné z: https://dx.doi.org/10.25596/jalc-2020-141.
|
