Open AccessOn the reachability set of automaton counter machines
Author(s) -
E. V. Kuzmin,
D. Ju. Chalyy
Publication year - 2011
Publication title -
automatic control and computer sciences
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.299
H-Index - 17
eISSN - 1558-108X
pISSN - 0146-4116
DOI - 10.3103/s0146411611070091
Subject(s) - reachability , timed automaton , two way deterministic finite automaton , automaton , büchi automaton , set (abstract data type) , deterministic automaton , pushdown automaton , computer science , bounded function , reachability problem , discrete mathematics , algorithm , mathematics , theoretical computer science , automata theory , nondeterministic finite automaton , programming language , mathematical analysis
Properties of automaton counter machines are considered. The set of reachability states of any automaton one-counter machine is proved to be a semilinear set. An algorithm for constructing this set is described. In addition, the reachability sets of any reversal-bounded automaton counter machine and any flat automaton counter machine are also semilinear.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom