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

Bijective Automata: Linear Synchronization Delay and Decision Algorithms

Eugen Czeizler, Bijective Automata: Linear Synchronization Delay and Decision Algorithms. In: Pre-proceedings of CANT 2006: EMS Summer School, International School and Conference on Combinatorics, Automata and Number Theory, 2006.

Abstract:

We classify finite automata according to the number of different bi-infinite paths having the same label. Thus, we introduce ww-bijective automata as finite automata where for any bi-infinite word there exists a unique path labeled by that word. These systems are strictly included in the class of local automata, but in the same time can be viewed as a generalization of one-dimensional reversible cellular automata. Although the synchronization delay of an n-state local automaton is known to be O(n*n) in the worst case, we prove that in the case of ww-bijective finite automata the synchronization delay is at most n-1. We also provide a polynomial time algorithm (in the number of states and labels) testing whether an automaton is ww-bijective.

BibTeX entry:

@INPROCEEDINGS{inpCzeizler06b,
  title = {Bijective Automata: Linear Synchronization Delay and Decision Algorithms},
  booktitle = {Pre-proceedings of CANT 2006: EMS Summer School, International School and Conference on Combinatorics, Automata and Number Theory},
  author = {Czeizler, Eugen},
  year = {2006},
}

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

Edit publication