On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
From MaRDI portal
Publication:5041250
DOI10.1007/978-3-030-48516-0_6OpenAlexW3032490305MaRDI QIDQ5041250
Michael Wehar, Mateus de Oliveira Oliveira
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
Related Items (1)
Cites Work
- Strong computational lower bounds via parameterized complexity
- Relating refined space complexity classes
- On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\)
- Which problems have strongly exponential complexity?
- Intersection non-emptiness and hardness within polynomial time
- Problems on finite automata and the exponential time hypothesis
- Tight lower bounds for certain parameterized NP-hard problems
- Improving Exhaustive Search Implies Superpolynomial Lower Bounds
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
- Parity, circuits, and the polynomial-time hierarchy
- The Complexity of Satisfiability of Small Depth Circuits
- Gradually intractable problems and nondeterministic log-space lower bounds
- On Relating Time and Space to Size and Depth
- Log Space Recognition and Translation of Parenthesis Languages
- Exponential Time Complexity of the Permanent and the Tutte Polynomial
- The emptiness problem for intersections of regular languages
- Short PCPs with Projection Queries
- Hardness Results for Intersection Non-Emptiness
- Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- Computing and Combinatorics
- On the complexity of \(k\)-SAT
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
