Optimal State Reductions of Automata with Partially Specified Behaviors

Utilize este identificador para referenciar este registo: https://hdl.handle.net/10216/90791

Registo completo

Campo DC	Valor	Idioma
dc.creator	Nelma Moreira
dc.creator	Giovanni Pighizzini
dc.creator	Rogerio Reis
dc.date.accessioned	2019-02-01T04:41:51Z	-
dc.date.available	2019-02-01T04:41:51Z	-
dc.date.issued	2015
dc.identifier.other	sigarra:107483
dc.identifier.uri	https://repositorio-aberto.up.pt/handle/10216/90791	-
dc.description.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. Finally, it is proved that the problem of minimizing nondeterministic and deterministic don't care automata is NP-complete.
dc.language.iso	eng
dc.relation.ispartof	SOFSEM 2015: THEORY AND PRACTICE OF COMPUTER SCIENCE
dc.rights	openAccess
dc.subject	Ciências da computação e da informação
dc.subject	Computer and information sciences
dc.title	Optimal State Reductions of Automata with Partially Specified Behaviors
dc.type	Artigo em Livro de Atas de Conferência Internacional
dc.contributor.uporto	Faculdade de Ciências
dc.identifier.doi	10.1007/978-3-662-46078-8_28
dc.identifier.authenticus	P-00A-59X
dc.subject.fos	Ciências exactas e naturais::Ciências da computação e da informação
dc.subject.fos	Natural sciences::Computer and information sciences
Aparece nas coleções:	FCUP - Artigo em Livro de Atas de Conferência Internacional

Ficheiros deste registo:

Ficheiro	Descrição	Tamanho	Formato
107483.pdf		310.39 kB	Adobe PDF	Ver/Abrir