Matrix Mortality and the Cerny-Pin Conjecture

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

Authors

Jorge Almeida (Author) FCUP; Benjamin Steinberg (Author) Other

Conference proceedings International

Title: DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS

Pages: 67-80

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

Stuttgart, GERMANY, JUN 30-JUL 03, 2009

Indexing

ISI Web of Knowledge - 16 Citations

Scopus - 17 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

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

Language: English

Type (Professor's evaluation): Scientific