The complexity of intersecting finite automata having few final states

DOI10.1007/s00037-014-0089-9zbMath1353.68109MaRDI QIDQ347114

Andreas Krebs, Pierre McKenzie, Michael Blondin

Publication date: 30 November 2016

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-014-0089-9

zbMATH Keywords

NP-completeness; finite automata; monoids; intersection problem; logspace; point-spread problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q70: Algebraic theory of languages and automata

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Constrained synchronization and subset synchronization problems for weakly acyclic automata, The intersection problem for finite monoids

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Descriptional and computational complexity of finite automata -- a survey
• Classifying problems on linear congruences and Abelian permutation groups using logspace counting classes
• Fourier analysis on finite abelian groups
• On varieties of rational languages and variable length codes. II
• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• Membership testing in commutative transformation semigroups
• Parallel algorithms for solvable permutation groups
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Hierarchies of complete problems
• On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\)
• A note on closure properties of logspace MOD classes
• Complete classifications for the communication complexity of regular languages
• Relationships between nondeterministic and deterministic tape complexities
• On uniformity within \(NC^ 1\)
• The Complexity of Intersecting Finite Automata Having Few Final States
• Bounded-depth circuits
• Undirected ST-connectivity in log-space
• Problems complete for deterministic logarithmic space
• The Parallel Complexity of Abelian Permutation Group Problems
• Finite monoids and the fine structure of NC ¹
• Structure and importance of logspace-MOD class
• New problems complete for nondeterministic log space
• On Relating Time and Space to Size and Depth
• The membership problem in aperiodic transformation monoids
• Fast Management of Permutation Groups I
• Relationships among $PL$, $\#L$, and the determinant
• The emptiness problem for intersections of regular languages
• Logic Meets Algebra: the Case of Regular Languages
• On finite monoids having only trivial subgroups