The emptiness problem for intersections of regular languages
From MaRDI portal
Publication:5096847
DOI10.1007/3-540-55808-X_33zbMath1493.68191OpenAlexW1547995103MaRDI QIDQ5096847
Klaus-Joern Lange, Peter Rossmanith
Publication date: 18 August 2022
Published in: Mathematical Foundations of Computer Science 1992 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-55808-x_33
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
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 ⋮ Lamplighter groups and automata ⋮ The intersection problem for finite monoids ⋮ A finite state intersection approach to propositional satisfiability ⋮ Simple picture processing based on finite automata and regular grammars ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ A parametric analysis of the state-explosion problem in model checking ⋮ Diagnosability of repairable faults ⋮ On computational complexity of set automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On uniform circuit complexity
- Hierarchies of complete problems
- Space-bounded reducibility among combinatorial problems
- A taxonomy of problems with fast parallel algorithms
- Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
- Relativization of questions about log space computability
- On the complexity of finite, pushdown, and stack automata
- Real-time computations with restricted nondeterminism
This page was built for publication: The emptiness problem for intersections of regular languages