Complexity of checking whether two automata are synchronized by the same language
classification
💻 cs.FL
keywords
automatonlanguageresetparticularwhetherwordwordsautomata
read the original abstract
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 PSPACE-complete problem to check whether the language of reset words for a given automaton coincides with the language of reset words for some particular automaton.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.