The emptiness problem for intersections of regular languages

DOI10.1007/3-540-55808-X_33MaRDI QIDQ5096847zbMATH OpenOpenAlexFDO

Authors Klaus-Jörn 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

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

Recommendations

• The complexity of intersecting finite automata having few final states
• On emptiness and counting for alternating finite automata
• The complexity of intersecting finite automata having few final states
• scientific article; zbMATH DE number 2086619
• Hardness results for intersection non-emptiness

Cites work

• scientific article; zbMATH DE number 3936519 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 17527 (Why is no real title available?)
• scientific article; zbMATH DE number 176517 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 1346517 (Why is no real title available?)
• A taxonomy of problems with fast parallel algorithms
• Hierarchies of complete problems
• On the complexity of finite, pushdown, and stack automata
• On uniform circuit complexity
• Real-time computations with restricted nondeterminism
• Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
• Relativization of questions about log space computability
• Space-bounded reducibility among combinatorial problems

Cited in

(23)

• Lamplighter groups and automata
• The complexity of intersecting finite automata having few final states
• 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
• Intersection non-emptiness and hardness within polynomial time
• Simple picture processing based on finite automata and regular grammars
• A finite state intersection approach to propositional satisfiability
• On the decidability of finding a positive ILP-instance in a regular set of ILP-instances
• The intersection problem for finite monoids
• Deciding regular intersection emptiness of complete problems for PSPACE and the polynomial hierarchy
• On computational complexity of set automata
• A parametric analysis of the state-explosion problem in model checking
• Hardness results for intersection non-emptiness
• Problems on finite automata and the exponential time hypothesis
• scientific article; zbMATH DE number 7168170 (Why is no real title available?)
• Diagnosability of repairable faults
• Decidability and shortest strings in formal languages
• A note on the emptiness of intersection problem for left Szilard languages
• Descriptional and computational complexity of finite automata -- a survey
• On the complexity of intersection non-emptiness for star-free language classes
• On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
• Decision problems for reversible and permutation automata

This page was built for publication: The emptiness problem for intersections of regular languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096847)