Hardness Results for Intersection Non-Emptiness

DOI10.1007/978-3-662-43951-7_30zbMath1410.68212OpenAlexW2147611860MaRDI QIDQ5167851

Michael Wehar

Publication date: 1 July 2014

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-43951-7_30

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 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, On minimizing regular expressions without Kleene star, A theoretical framework for cardinality-based feature models: the semantics and computational aspects, Problems on finite automata and the exponential time hypothesis, On the Complexity of String Matching for Graphs, Synchronizing Automata over Nested Words