Polynomial complete problems in automata theory

DOI10.1016/0020-0190(83)90067-4zbMath0508.68030OpenAlexW2052581866MaRDI QIDQ1838038

I. K. Rystsov

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

zbMATH Keywords

deterministic finite state automata

Mathematics Subject Classification ID

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

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

• Multiple-entry finite automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item