Reset Complexity of Ideal Languages
arXiv:1404.2816
Abstract
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 language. We also compare the reset complexity and the state complexity for languages related to slowly synchronizing automata and study uniqueness question for automata yielding the minimum of reset complexity.
Cited by in corpus (7)
- Completely Reachable Automata
- Finitely generated ideal languages and synchronizing automata
- Principal ideal languages and synchronizing automata
- Complexity of checking whether two automata are synchronized by the same language
- Synchronizing automata and the language of minimal reset words
- On the interplay between Babai and Cerny's conjectures
- Representation of (Left) Ideal Regular Languages by Synchronizing Automata