On a reachability set of automaton counter machines

Abstract

Properties of automaton counter machines are investigated. We prove that reachability sets of automaton one-counter machines are semilinear. An algorithm of construction of these semilinear reachability sets is resultexl. Besides, it is shown that reachability sets of reversal-boundexl automaton counter machines and reachability sets of hat automaton counter machines are also semilinear.

Keywords

• <i>abstract counter machines</i>
• <i>automaton counter machine</i>
• <i>communicating colouring automata</i>
• <i>reachability sets</i>
• <i>semilinear sets</i>