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
Basic information
Original name Forbidden patterns for ordered automata
Authors KLÍMA, Ondřej (203 Czech Republic, guarantor, belonging to the institution) and Libor POLÁK (203 Czech Republic, belonging to the institution).
Edition Journal of Automata, Languages and Combinatorics, Institut fur Informatik, Justus-Liebig-Universitat Giessen, 2020, 1430-189X.
Other information
Original language English
Type of outcome Article in a journal
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Germany
Confidentiality degree is not subject to a state or trade secret
WWW URL
RIV identification code RIV/00216224:14310/20:00114579
Organization unit Faculty of Science
Doi http://dx.doi.org/10.25596/jalc-2020-141
Keywords in English deterministic automata; varieties of regular languages; varieties of automata
Tags rivok
Tags International impact, Reviewed
Changed by Changed by: doc. Mgr. Ondřej Klíma, Ph.D., učo 3868. Changed: 16/12/2020 14:09.
Abstract
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.
Links
GA15-02862S, research and development projectName: Aplikace algebry a kombinatoriky v teorii formálních jazyků
Investor: Czech Science Foundation
PrintDisplayed: 8/9/2024 07:01