Optimal State Reductions of Automata with Partially Specified Behaviors

• Type: Article in International Conference Proceedings Book
• Date: 2015

Authors

Nelma Moreira (Author) FCUP; Giovanni Pighizzini (Author) Other; Rogerio Reis (Author) FCUP

Conference proceedings International

Title: SOFSEM 2015: THEORY AND PRACTICE OF COMPUTER SCIENCE

Pages: 339-351

41st International Conference on Current Trends in Theory and Practice of Computer Science ((SOFSEM)

Pecpod Snezkou, CZECH REPUBLIC, JAN 24-29, 2015

Indexing

ISI Web of Knowledge - 0 Citations

Scopus - 1 Citation

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-00A-59X

DOI: 10.1007/978-3-662-46078-8_28

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. Finally, it is proved that the problem of minimizing nondeterministic and deterministic don't care automata is NP-complete.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 13