Optimal State Reductions of Automata with Partially Specified Behaviors

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2015

Autores

Nelma Moreira (Autor) FCUP; Giovanni Pighizzini (Autor) Outra; Rogerio Reis (Autor) FCUP

Ata de Conferência Internacional

Título: SOFSEM 2015: THEORY AND PRACTICE OF COMPUTER SCIENCE

Páginas: 339-351

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

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

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 1 Citação

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 13