Toward Determining NFA Equivalence via QBFs (Student Abstract)
Keywords:SAT, QBF, QSAT, Automata
AbstractEquivalence 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.
How to Cite
Miller, H., & Narváez, D. E. (2021). Toward Determining NFA Equivalence via QBFs (Student Abstract). Proceedings of the AAAI Conference on Artificial Intelligence, 35(18), 15849-15850. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17921
AAAI Student Abstract and Poster Program