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