Problems on finite automata and the exponential time hypothesis

DOI10.3390/a10010024zbMath1461.68101WikidataQ59864887 ScholiaQ59864887MaRDI QIDQ1662614

Henning Fernau, Andreas Krebs

Publication date: 20 August 2018

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a10010024

zbMATH Keywords

finite automata; exponential time hypothesis; equivalence problem; universality problem; emptiness of intersection

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Uses Software

• Antichains