Toward Determining NFA Equivalence via QBFs (Student Abstract)

Authors

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

DOI:

https://doi.org/10.1609/aaai.v35i18.17921

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.
AAAI-21 Proceedings Cover

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. https://doi.org/10.1609/aaai.v35i18.17921

Issue

Vol. 35 No. 18: AAAI-21 Student Papers and Demonstrations

Section

AAAI Student Abstract and Poster Program