On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\)

DOI10.1016/S0304-3975(02)00830-7zbMath1044.68098OpenAlexW2002992445MaRDI QIDQ1401330

Anastasios Viglas, George Karakostas, Richard J. Lipton

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00830-7

zbMATH Keywords

\(\mathcal{NL},\mathcal{NP}\)Complexity class separationsFinite state automata intersection

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (8)

On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection ⋮ On the Complexity of Intersecting Regular, Context-Free, and Tree Languages ⋮ The complexity of intersecting finite automata having few final states ⋮ Problems on finite automata and the exponential time hypothesis ⋮ On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape ⋮ On conditional decomposability ⋮ A finite state intersection approach to propositional satisfiability ⋮ The Complexity of Predicting Atomicity Violations

Cites Work

• On time versus space. II
• Space-bounded reducibility among combinatorial problems
• On Time Versus Space
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\)