The complexity of intersecting finite automata having few final states
From MaRDI portal
Publication:347114
DOI10.1007/s00037-014-0089-9zbMath1353.68109OpenAlexW2130671965MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Algebraic theory of languages and automata (68Q70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (2)
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
This page was built for publication: The complexity of intersecting finite automata having few final states
