The complexity of intersecting finite automata having few final states
DOI10.1007/S00037-014-0089-9zbMATH Open1353.68109OpenAlexW2130671965MaRDI QIDQ347114FDOQ347114
Authors: Michael Blondin, A. Krebs, Pierre McKenzie 
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algebraic theory of languages and automata (68Q70)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Relationships between nondeterministic and deterministic tape complexities
- On uniformity within \(NC^ 1\)
- The complexity of intersecting finite automata having few final states
- Problems complete for deterministic logarithmic space
- Title not available (Why is that?)
- On finite monoids having only trivial subgroups
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Title not available (Why is that?)
- Structure and importance of logspace-MOD class
- New problems complete for nondeterministic log space
- Title not available (Why is that?)
- Fourier analysis on finite abelian groups
- On Relating Time and Space to Size and Depth
- 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
- 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
- Bounded-depth circuits
- Undirected ST-connectivity in log-space
- The Parallel Complexity of Abelian Permutation Group Problems
- Finite monoids and the fine structure of NC 1
- Title not available (Why is that?)
- Title not available (Why is that?)
- The membership problem in aperiodic transformation monoids
- Fast Management of Permutation Groups I
- Title not available (Why is that?)
- Title not available (Why is that?)
- Relationships among $PL$, $\#L$, and the determinant
- The emptiness problem for intersections of regular languages
- Logic Meets Algebra: the Case of Regular Languages
- Descriptional and computational complexity of finite automata -- a survey
- Classifying problems on linear congruences and Abelian permutation groups using logspace counting classes
Cited In (12)
- The complexity of interacting automata
- Constrained synchronization and subset synchronization problems for weakly acyclic automata
- An intersection problem for finite automata
- The complexity of intersecting finite automata having few final states
- On the complexity of intersecting regular, context-free, and tree languages
- The intersection problem for finite semigroups
- The intersection problem for finite semigroups
- The intersection problem for finite monoids
- The emptiness problem for intersections of regular languages
- Title not available (Why is that?)
- Decision problems for reversible and permutation automata
- On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\)
This page was built for publication: The complexity of intersecting finite automata having few final states
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q347114)
