2020
Forbidden patterns for ordered automata
KLÍMA, Ondřej and Libor POLÁKBasic 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
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
References:
RIV identification code
RIV/00216224:14310/20:00114579
Organization unit
Faculty of Science
EID Scopus
2-s2.0-85089837623
Keywords in English
deterministic automata; varieties of regular languages; varieties of automata
Tags
Tags
International impact, Reviewed
Changed: 16/12/2020 14:09, doc. Mgr. Ondřej Klíma, Ph.D.
Abstract
V originále
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 project |
|