Toward Determining NFA Equivalence via QBFs (Student Abstract)

Authors

  • Hannah Miller Rochester Institute of Technology
  • David E. Narváez Rochester Institute of Technology

Keywords:

SAT, QBF, QSAT, Automata

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.

Downloads

Published

2021-05-18

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

Issue

Section

AAAI Student Abstract and Poster Program