• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

On the Synchronization Delay of Complete Local Automata

Marie-Pierre Beal, Eugen Czeizler, Dominique Perrin, Jarkko Kari, On the Synchronization Delay of Complete Local Automata. In: Proceedings of London Algorithmic Workshop, 2007.

Abstract:

A (non-deterministic) local automaton is an automaton for which there is an integer d such that any label of a path of length d is a synchronizing word. The smallest integer d such that the property holds is called the synchronization delay of the automaton. Czeizler and Kari proved that an n-state local complete automaton has a synchronization delay at most n-1. We give an alternative proof of this result that makes it a consequence of previous work from Cesari on monoids of unambiguous relations.

BibTeX entry:

@INPROCEEDINGS{inpBeCzPeKa07a,
  title = {On the Synchronization Delay of Complete Local Automata},
  booktitle = {Proceedings of London Algorithmic Workshop},
  author = {Beal, Marie-Pierre and Czeizler, Eugen and Perrin, Dominique and Kari, Jarkko},
  year = {2007},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication