Matrix Mortality and the Cerny-Pin Conjecture

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

Autores

Jorge Almeida (Autor) FCUP; Benjamin Steinberg (Autor) Outra

Ata de Conferência Internacional

Título: DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS

Páginas: 67-80

13th International Conference on Developments in Language Theory (DLT 2009)

Stuttgart, GERMANY, JUN 30-JUL 03, 2009

Indexação

ISI Web of Knowledge - 16 Citações

Scopus - 17 Citações

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-003-PNH

DOI: 10.1007/978-3-642-02737-6_5

Abstract (EN): In this paper, we establish the Cerny-Pin conjecture for automata with the property that their transition monoid cannot recognize the language {a, b}* ab{a, b}*. For the subclass of automata whose transition monoids have the property that each regular J-class is a subsemigroup, we give a tight bound on lengths of reset words for synchronizing automata thereby answering a question of Volkov.

Idioma: Inglês

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