Real-time, pseudo real-time, and linear-time ITA (Q1089799): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q418765 |
Changed an Item |
||
Property / author | |||
Property / author: Sheng Yu / rank | |||
Normal rank |
Revision as of 19:05, 14 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Real-time, pseudo real-time, and linear-time ITA |
scientific article |
Statements
Real-time, pseudo real-time, and linear-time ITA (English)
0 references
1986
0 references
A k-ary iterative tree automaton (k-ary ITA) is a potentially infinite synchronous network of finite automata structured as k-ary tree with serial input and output at the root of the tree. The computational power of an ITA in real-time, pseudo real-time and linear-time is compared. The pseudo real-time is a new notion and means that every cell of an ITA makes a fixed number of computational steps for each input symbol. It is shown that every linear-time ITA can be simulated either by a pseudo real-time ITA of the same arity or by a real-time ITA of a higher arity. As an example, an ITA implementation of real-time infinite memory is described.
0 references
k-ary iterative tree automaton
0 references
potentially infinite synchronous network of finite automata
0 references