Polynomial complete problems in automata theory
From MaRDI portal
Publication:1838038
DOI10.1016/0020-0190(83)90067-4zbMath0508.68030OpenAlexW2052581866MaRDI QIDQ1838038
Publication date: 1983
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(83)90067-4
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (23)
Constrained synchronization and subset synchronization problems for weakly acyclic automata ⋮ Synchronizing words and monoid factorization, yielding a new parameterized complexity class? ⋮ On the complexity of existence of homing sequences for nondeterministic finite state machines ⋮ Using SAT solvers for synchronization issues in non-deterministic automata ⋮ Problems on finite automata and the exponential time hypothesis ⋮ Weak equivalence of automata ⋮ Careful synchronization of partial deterministic finite automata ⋮ Synchronizing words under \textsf{LTL} constraints ⋮ Synchronizing deterministic push-down automata can be really hard ⋮ Preimage problems for deterministic finite automata ⋮ D2-SYNCHRONIZATION IN NONDETERMINISTIC AUTOMATA ⋮ Complexity of Preimage Problems for Deterministic Finite Automata ⋮ Constrained synchronization and commutativity ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ Unnamed Item ⋮ The relation between preset distinguishing sequences and synchronizing sequences ⋮ Synchronizing Automata over Nested Words ⋮ Synchronization problems in automata without non-trivial cycles ⋮ Rank of a finite automaton ⋮ Semicomputable points in Euclidean spaces ⋮ Problems on Finite Automata and the Exponential Time Hypothesis ⋮ Complexities of Some Problems Related to Synchronizing, Non-Synchronizing and Monotonic Automata ⋮ Reset complexity and completely reachable automata with simple idempotents
Cites Work
This page was built for publication: Polynomial complete problems in automata theory
