Publication details
Forbidden patterns for ordered automata
| Authors | |
|---|---|
| Year of publication | 2020 |
| Type | Article in Periodical |
| Magazine / Source | Journal of Automata, Languages and Combinatorics |
| MU Faculty or unit | |
| Citation | |
| Web | 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 |
| Keywords | deterministic automata; varieties of regular languages; varieties of automata |
| Description | 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. |
| Related projects: |