Forbidden patterns for ordered automata

J 2020

Forbidden patterns for ordered automata

KLÍMA, Ondřej a Libor POLÁK

Základní údaje

Originální název

Forbidden patterns for ordered automata

Autoři

KLÍMA, Ondřej (203 Česká republika, garant, domácí) a Libor POLÁK (203 Česká republika, domácí)

Vydání

Journal of Automata, Languages and Combinatorics, Institut fur Informatik, Justus-Liebig-Universitat Giessen, 2020, 1430-189X

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL

Kód RIV

RIV/00216224:14310/20:00114579

Organizační jednotka

Přírodovědecká fakulta

DOI

http://dx.doi.org/10.25596/jalc-2020-141

EID Scopus

2-s2.0-85089837623

Klíčová slova anglicky

deterministic automata; varieties of regular languages; varieties of automata

Štítky

rivok

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 16. 12. 2020 14:09, doc. Mgr. Ondřej Klíma, Ph.D.

Anotace

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.

Návaznosti

GA15-02862S, projekt VaV

Název: Aplikace algebry a kombinatoriky v teorii formálních jazyků

Investor: Grantová agentura ČR, Aplikace algebry a kombinatoriky v teorii formálních jazyků

Citovat

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.

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

Přehled o publikaci