ML Anthology

Toward Determining NFA Equivalence via QBFs (Student Abstract)

Hannah Miller, David E. Narváez
AAAI 2021 pp. 15849-15850
doi:10.1609/AAAI.V35I18.17921 /aaai/2021/miller2021aaai-determining/

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.

PDF AAAI Semantic Scholar

Cite

Text

Miller and Narváez. "Toward Determining NFA Equivalence via QBFs (Student Abstract)." AAAI Conference on Artificial Intelligence, 2021. doi:10.1609/AAAI.V35I18.17921

Markdown

[Miller and Narváez. "Toward Determining NFA Equivalence via QBFs (Student Abstract)." AAAI Conference on Artificial Intelligence, 2021.](https://mlanthology.org/aaai/2021/miller2021aaai-determining/) doi:10.1609/AAAI.V35I18.17921

BibTeX

@inproceedings{miller2021aaai-determining,
  title     = {{Toward Determining NFA Equivalence via QBFs (Student Abstract)}},
  author    = {Miller, Hannah and Narváez, David E.},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2021},
  pages     = {15849-15850},
  doi       = {10.1609/AAAI.V35I18.17921},
  url       = {https://mlanthology.org/aaai/2021/miller2021aaai-determining/}
}