24 citations · 28 across the 5 of their papers we have counts for
5 papers
Representation of (Left) Ideal Regular Languages by Synchronizing Automata
Marina Maslennikova, Emanuele Rodaro
We follow language theoretic approach to synchronizing automata and Černý's conjecture initiated in a series of recent papers. We find a precise lower bound for the reset complexit…
Complexity of checking whether two automata are synchronized by the same language
Marina Maslennikova
A deterministic finite automaton is said to be synchronizing if it has a reset word, i.e. a word that brings all states of the automaton to a particular one. We prove that it is a…
Reset Complexity of Ideal Languages
Marina Maslennikova
We present a new characteristic of a regular ideal language called reset complexity. We find some bounds on the reset complexity in terms of the state complexity of a given languag…
Finitely generated ideal languages and synchronizing automata
Vladimir V. Gusev, Marina I. Maslennikova, Elena V. Pribavkina
We study representations of ideal languages by means of strongly connected synchronizing automata. For every finitely generated ideal language L we construct such an automaton with…
Principal ideal languages and synchronizing automata
Vladimir V. Gusev, Marina I. Maslennikova, Elena V. Pribavkina
We study ideal languages generated by a single word. We provide an algorithm to construct a strongly connected synchronizing automaton for which such a language serves as the langu…