Optimal state reductions of automata with partially specified behaviors

• Tipo: Artigo em Revista Científica Internacional
• Data: 2017

Autores

Nelma Moreira (Autor) FCUP; Pighizzini, G (Autor) Outra; Rogério Reis (Autor) FCUP

Revista

Título: Theoretical Computer Science

Vol. 658

Páginas: 235-245

ISSN: 0304-3975

Editora: Elsevier

Indexação

ISI Web of Knowledge - 3 Citações

Scopus - 3 Citações

Outras Informações

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

Idioma: Inglês

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

Nº de páginas: 11