The emptiness problem for intersections of regular languages

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (12)

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