Real-time, pseudo real-time, and linear-time ITA (Q1089799): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(86)90130-1 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2079921753 / rank | |||
Normal rank |
Revision as of 22:34, 19 March 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