KLÍMA, Ondřej and Libor POLÁK. Forbidden patterns for ordered automata. Journal of Automata, Languages and Combinatorics. Institut fur Informatik, Justus-Liebig-Universitat Giessen, 2020, vol. 25, 2-3, p. 141-169. ISSN 1430-189X. Available from: https://dx.doi.org/10.25596/jalc-2020-141. |
Other formats:
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 and Libor POLÁK. Forbidden patterns for ordered automata. \textit{Journal of Automata, Languages and Combinatorics}. Institut fur Informatik, Justus-Liebig-Universitat Giessen, 2020, vol.~25, 2-3, p.~141-169. ISSN~1430-189X. Available from: https://dx.doi.org/10.25596/jalc-2020-141.
|