Decision problems for reversible and permutation automata

DOI10.1007/978-3-031-71112-1_22MaRDI QIDQ6666806

Alexander Okhotin, Maria Radionova

Publication date: 20 January 2025

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of intersecting finite automata having few final states
• Minimizing finite automata is computationally hard
• The parallel complexity of finite-state automata problems
• Hierarchies of complete problems
• Space-bounded reducibility among combinatorial problems
• \texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata
• Undirected connectivity in log-space
• Problems complete for deterministic logarithmic space
• Inference of Reversible Languages
• Minimal Reversible Deterministic Finite Automata
• Operations on Permutation Automata
• The emptiness problem for intersections of regular languages
• Permutation automata
• Minimal and Hyper-Minimal Biautomata
• On the accepting state complexity of operations on permutation automata

This page was built for publication: Decision problems for reversible and permutation automata