Optimal State Reductions of Automata with Partially Specified Behaviors

TitleOptimal State Reductions of Automata with Partially Specified Behaviors
Publication TypeArticles in international peer reviewed journals
Year of Publication2017
AuthorsMoreira N, Pighizzini G, Reis R
JournalTheoretical Computer Science
Volume658
Pagination235–245
Date PublishedJanuary
KeywordsDescriptional complexity; Don't care automata; Finite automata; Nondeterminism
Abstract

Nondeterministic finite automata with don't care states, namely states which neither accept nor reject, are considered. A characterization of deterministic automata compatible with such a device is obtained. Furthermore, an optimal state bound for the smallest compatible deterministic automata is provided. It is proved that the problem of minimizing deterministic don't care automata is NP-complete and PSPACE-hard in the nondeterministic case. The restriction to the unary case is also considered.

DOI10.1016/j.tcs.2016.05.002
[2017-3]