Complexity of Checking Whether Two Automata Are Synchronized by the Same Language

DOI10.1007/978-3-319-09704-6_27zbMath1416.68107arXiv1405.3576OpenAlexW2222006297MaRDI QIDQ5496198

Marina Maslennikova

Publication date: 7 August 2014

Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1405.3576

zbMATH Keywords

PSPACE-completenessreset wordsynchronizing automatonideal languagereset complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Strongly connected synchronizing automata and the language of minimal reset words ⋮ Representation of (Left) Ideal Regular Languages by Synchronizing Automata ⋮ Reset Complexity of Ideal Languages Over a Binary Alphabet

This page was built for publication: Complexity of Checking Whether Two Automata Are Synchronized by the Same Language