On dynamics of automata with a stack

Abstract

In this paper we introduce a new dynamical system of a pushdown automaton, called automaton with a stack (AS). We prove that every AS has a periodic configuration by construction of it. Next, we define a special case of an AS, called AS with finite memory and we prove that the AS has a finite memory if and only if it is positively expansive. Furthermore, we prove that every AS with finite memory has shadowing property. Having these two properties, we set a finite-to-one map between an AS with finite memory and some vertex subshift, which gives us a semi-conjugacy between these two systems. Additionally, we define an algorithm to decide if a given graph G describes some AS with finite memory and to calculate maximal depth of a stack.

Keywords:

• dynamical system
• pushdown automaton
• periodic configuration
• positive expansivity
• shadowing
• semi-conjugacy

JEL Classification:

• 03C

2010 AMS Subject Classifications:

• 03D10
• 68Q05
• 68Q10
• 68Q45