On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection

DOI10.1007/978-3-030-48516-0_6MaRDI QIDQ5041250zbMATH OpenOpenAlexFDO

Authors Mateus de Oliveira Oliveira, Michael Wehar

Publication date 13 October 2022

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-48516-0_6

zbMATH Keywords

fine grained complexityfinite automataintersection non-emptinessparameterized complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Hardness results for intersection non-emptiness
• Intersection non-emptiness and hardness within polynomial time
• The emptiness problem for intersections of regular languages
• On the complexity of intersecting regular, context-free, and tree languages
• On the complexity of intersection non-emptiness for star-free language classes

Cites work

• Computing and Combinatorics
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• Gradually intractable problems and nondeterministic log-space lower bounds
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Hardness results for intersection non-emptiness
• scientific article; zbMATH DE number 440476 (Why is no real title available?)
• scientific article; zbMATH DE number 1775632 (Why is no real title available?)
• scientific article; zbMATH DE number 6783431 (Why is no real title available?)
• Improving exhaustive search implies superpolynomial lower bounds
• Intersection non-emptiness and hardness within polynomial time
• Log Space Recognition and Translation of Parenthesis Languages
• On Relating Time and Space to Size and Depth
• On the complexity of k-SAT
• On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\)
• On the possibility of faster \textsc{SAT} algorithms
• Parity, circuits, and the polynomial-time hierarchy
• Problems on finite automata and the exponential time hypothesis
• Relating refined space complexity classes
• Short PCPs with projection queries
• Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
• Strong computational lower bounds via parameterized complexity
• The complexity of satisfiability of small depth circuits
• The emptiness problem for intersections of regular languages
• Tight lower bounds for certain parameterized NP-hard problems
• Which problems have strongly exponential complexity?

Cited in

(8)

• On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\)
• On minimizing regular expressions without Kleene star
• scientific article; zbMATH DE number 7168170 (Why is no real title available?)
• On the complexity of intersection non-emptiness for star-free language classes
• Algorithms for checking intersection non-emptiness of regular expressions
• Incremental algorithms for solving regular expression intersection non-emptiness
• Membership problems in finite groups
• Self-assembly of strings and languages revisited: efficiently deciding closure under self-assembly

This page was built for publication: On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection

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