Toward Determining NFA Equivalence via QBFs
收藏数据链接：
官方服务：
资源简介：
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 quivalence 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.
提供机构：
Zenodo创建时间：
2020-11-18
