The complexity of intersecting finite automata having few final states
From MaRDI portal
Publication:347114
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
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 1
- 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