Library

Toward Determining NFA Equivalence via QBFs (Student Abstract)

Equivalence of deterministic finite automata (DFAs) has been researched for several decades, but equivalence of nondeterministic finite automata (NFAs) is not as studied. Equivalence of two NFAs is a PSPACE-complete problem. NFA equivalence is a challenging theoretical problem with practical applications such as lexical analysis. Quantified boolean formulas (QBFs) naturally encode PSPACE-complete problems, and we share our preliminary work towards determining NFA equivalence via QBFs.

Computer Science
View graphSource

Paper

Full text

PDF

Toward Determining NFA Equivalence via QBFs (Student Abstract)

Semantic Scholar · Computer Science · 2021

Abstract

Equivalence of deterministic finite automata (DFAs) has been researched for several decades, but equivalence of nondeterministic finite automata (NFAs) is not as studied. Equivalence of two NFAs is a PSPACE-complete problem. NFA equivalence is a challenging theoretical problem with practical applications such as lexical analysis. Quantified boolean formulas (QBFs) naturally encode PSPACE-complete problems, and we share our preliminary work towards determining NFA equivalence via QBFs.

Source of record · Semantic Scholar

References (8)

01Non-CNF QBF Solving with QCIRCharles Jordan, William Klieber, M. Seidl2016 · AAAI Workshop: Beyond NP · 32 citations
02Hacking nondeterminism with induction and coinductionF. Bonchi, D. Pous2015 · Communications of the ACM · 24 citations
03Checking NFA equivalence with bisimulations up to congruenceF. Bonchi, D. Pous2013 · ACM-SIGACT Symposium on Principles of Programming Languages · 183 citations
04Experimental Evaluation of Classical Automata ConstructionsD. Tabakov, Moshe Y. Vardi2005 · Logic Programming and Automated Reasoning · 128 citations
05Word problems requiring exponential time(Preliminary Report)L. Stockmeyer, A. Meyer1973 · Symposium on the Theory of Computing · 898 citations
06Compilers Principles Techniques And ToolsP. Kaufmann2016 · 1.5k citations
07Introduction to Automata Theory, Languages and ComputationJ. Hopcroft, J. Ullman1979 · 15k citations
08An n log n algorithm for minimizing states in a finite automatonJ. Hopcroft1971 · 1.0k citations

Similar papers

Solving Quantified Boolean Formulas with Few Existential VariablesLeif Eriksson, Victor Lagerkvist, George Osipov et al.2024 · International Joint Conference on Artificial Intelligence · 3 citations In Library
A Survey on Applications of Quantified Boolean FormulasAnkit Shukla, Armin Biere, Luca Pulina et al.2019 · IEEE International Conference on Tools with Artificial Intelligence · 51 citations In Library
Chapter 30. Reasoning with Quantified Boolean FormulasEnrico Giunchiglia, Paolo Marin, Massimo Narizzano2021 · Frontiers in artificial intelligence and applications In Library
VC-dimensions of nondeterministic finite automata for words of equal lengthB. Kjos-Hanssen, Clyde James Felix, Sun Young Kim et al.2020 · Annals of Mathematics and Artificial Intelligence · 3 citations In Library
QFUN: Towards Machine Learning in QBFMikoláš Janota2017 · arXiv.org · 6 citations In Library
General Boolean Formula Minimization with QBF SolversEduardo Calò, Jordi Levy2023 · International Conference of the Catalan Association for Artificial Intelligence · 3 citations In Library
A Constructive Framework for Nondeterministic Automata via Time-Shared, Depth-Unrolled Feedforward NetworksSahil Rajesh Dhayalkar2026 · IEEE Access In Library
Model Counting for Dependency Quantified Boolean FormulasLong-Hin Fung, Che Cheng, J. Jiang et al.2025 · AAAI Conference on Artificial Intelligence · 1 citation In Library
Chapter 31. Quantified Boolean FormulasOlaf Beyersdorff, Mikoláš Janota, Florian Lonsing et al.2021 · Frontiers in artificial intelligence and applications In Library
Inference of Deterministic Finite Automata via Q-LearningElaheh Hosseinkhani, Martin Leucker2025 · Brazilian Symposium on Formal Methods · 0 citations In Library
© 2026 NYSGPT2525 LLC