Part 3. Mathematical models

Lower estimate for max period of realtime pushdown automaton output

I. E. Ivanov


Abstract: Earlier the author proved that realtime pushdown automaton function saves the set of periodic sequences and found exponential estimate for the period of output. For realtime one-counter transducer this estimate may be reduced to quadratic. In this paper the author found lower exponential estimate for the period of output if stack alphabet contains at least two symbols.

Keywords: realtime pushdown automaton, deterministic function, periodic sequences.