Informace o publikaci

Forbidden patterns for ordered automata


KLÍMA Ondřej POLÁK Libor

Rok publikování 2020
Druh Článek v odborném periodiku
Časopis / Zdroj Journal of Automata, Languages and Combinatorics
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Klíčová slova deterministic automata; varieties of regular languages; varieties of automata
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info