On automata recognizing birecurrent sets
From MaRDI portal
Publication:1625603
DOI10.1016/j.tcs.2018.06.043zbMath1412.68135arXiv1711.01061OpenAlexW2963068996MaRDI QIDQ1625603
Publication date: 29 November 2018
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1711.01061
computational complexitydeterministic finite-state automatonpartial automatonbirecurrent languagebirecurrent set
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Cites Work
- Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
- Rank of a finite automaton
- Subset Synchronization and Careful Synchronization of Binary Finite Automata
- COMPLETELY REDUCIBLE SETS
- Birecurrent sets
- RANK PROBLEMS FOR COMPOSITE TRANSFORMATIONS