Real‐time shuffle stack automaton
Shoji Kosai, Yoshihiro Tsujino, Toshiro Araki, Nobuki Tokura · Systems and Computers in Japan · 1985
Abstract As models to describe concurrent systems, Petri net, shuffle stack automaton (SSA), flow expression, event expression, and shuffle grammar have been proposed. SSA is an automaton which is obtained by adding to the finite automaton a stack with shuffle function. Its descriptive power has already been discussed. This paper discusses the real‐time shuffle stack automaton (RSSA, which is an SSA without λ‐transition in regard to the input), which is a subclass of SSA. It is shown that RSSA has the same descriptive power, independently of the accepting mode (empty‐stack acceptance or final‐state acceptance), and of whether or not a terminating symbol is provided at the end of the input string. It is also shown that the descriptive power of RSSA is incomparable to that of the push‐down automaton, but is properly contained in that of the linear bounded automaton. If a language is bounded and if the set obtained by applying Parikh mapping to that language is semi‐linear, the language is accepted by RSSA. Another property of the language accepted by RSSA is that if it is a bounded context‐free language, it is accepted by RSSA.