Optimal state reductions of automata with partially specified behaviors

• Type: Article in International Scientific Journal
• Date: 2017

Authors

Nelma Moreira (Author) FCUP; Pighizzini, G (Author) Other; Rogério Reis (Author) FCUP

Journal

Title: Theoretical Computer Science

Vol. 658

Pages: 235-245

ISSN: 0304-3975

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 3 Citations

Scopus - 3 Citations

Other information

Authenticus ID: P-00M-9E3

DOI: 10.1016/j.tcs.2016.05.002

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 11