REAL-TIME SHUFFLE STACK AUTOMATON.

被引：0

作者：

Kosai, Shoji ^{[1
]}

Tsujino, Yoshihiro ^{[1
]}

Araki, Toshiro ^{[1
]}

Tokura, Nobuki ^{[1
]}

机构：

[1] Osaka Univ, Toyonaka, Jpn, Osaka Univ, Toyonaka, Jpn

来源：

Systems and Computers in Japan | 1985年 / 16卷 / 02期

关键词：

COMPUTER SYSTEMS; DIGITAL - Parallel Processing;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

This paper discusses the real-time shuffle stack automaton (RSSA, which is an SSA without lambda -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. This automaton is of interest for modeling concurrent systems.

引用

页码：29 / 37