Applied Automata Theory

Estimation for an output symbol multiplicity in invertible automata

D. A. Katerinskiy

Tomsk State University, Tomsk

Abstract: It is shown that the maximum repetition number for an output symbol in the output table of an invertible automaton with $n$ states and $m$ input symbols is $[(n+1)/2][(n+2)/2]$ if $[(n+2)/2]\leq m$, or $(n-m+1)m$ otherwise.

Keywords: finite automata, invertibility, weakly invertibility, strongly invertibility, output symbol multiplicity.

UDC: 519.7