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

On Deterministic Two-Way Finite Automata Over a Unary Alphabet

Michal Kunc, Alexander Okhotin, On Deterministic Two-Way Finite Automata Over a Unary Alphabet. TUCS Technical Reports 950, Turku Centre for Computer Science, 2011.

Abstract:

A framework for the study of two-way deterministic finite automata (2DFA) over a one-letter alphabet is developed, generalizing the concept of transformation semigroups to the case of bi-directional motion. It allows analyzing the behaviour of automata globally, on all inputs at once, rather than locally, following a particular computation, as per the mainstream approach to two-way computations. The method is used to show that transforming an $n$-state unary 2DFA to an equivalent sweeping 2DFA requires exactly $n+1$ states, and that exactly $\max_{0 \le l \le n} g(n-l)+l+1$ states, where $g(k)$ is the maximum order of a permutation of $k$ elements, are needed for a similar transformation of a unary 2DFA to a one-way automaton.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tKunc09a,
  title = {On Deterministic Two-Way Finite Automata Over a Unary Alphabet},
  author = {Kunc, Michal and Okhotin, Alexander},
  number = {950},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2011},
  keywords = {Finite automata, two-way automata, transformation semigroups, unary languages, descriptional complexity},
}

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

Edit publication