Informace o publikaci
Forbidden patterns for ordered automata
| Autoři | |
|---|---|
| Rok publikování | 2020 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Journal of Automata, Languages and Combinatorics |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | https://www.jalc.de/issues/2020/issue_25_2-3/jalc-2020-141-169.php |
| Doi | http://dx.doi.org/10.25596/jalc-2020-141 |
| 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: |