Systolic trellis automatat†
In the first part the notion of a systolic trellis automaton (sta) is introduced, and several of its modifications are considered. Informally, an sta is given by a triangularly shaped hexagonally structured network where each node is occupied by a processor (indeed by a combinational circuit). The data flow goes rhythmically in the direction from the bottom level (where the input is fed in a parallel way) to the top processor. So full pipelining is possible. sta are used as language acceptors. It is shown that homogeneous sta (each node is occupied by the same type of processor) are strictly less powerful than unrestricted ones. In the second part different design techniques for sta are presented and illustrated by interesting examples. Furthermore, several general results are proved: sta are more powerful than systolic tree automata (introduced in the article reviewed below), the class of homogeneous sta languages is closed under Boolean operations, and it contains all linear languages not having the empty word as an element.
- Topological transformations as a tool in the design of systolic networks
- A property of real-time trellis automata
- C-tree systolic automata
- Variations of the firing squad problem and applications
- Parallel parsing on a one-way linear array of finite-state machines
- The impact of the number of cooperating grammars on the generative power
- Some decision problems for parallel communicating grammar systems
- Some computational limits of trellis automata
- Language equations
- Computational completeness of equations over sets of natural numbers
- Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
- Recognition of poly-slender context-free languages by trellis automata
- Input-driven languages are linear conjunctive
- Systolic automata and P systems
- Systolic trellis automata: Stability, decidability and complexity
- Comparing linear conjunctive languages to subfamilies of the context-free languages
- SIMULATION OF SYSTOLIC TREE AUTOMATA ON TRELLIS AUTOMATA
- scientific article; zbMATH DE number 3898246 (Why is no real title available?)
- scientific article; zbMATH DE number 3911718 (Why is no real title available?)
- Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
- scientific article; zbMATH DE number 3940733 (Why is no real title available?)
- scientific article; zbMATH DE number 4030987 (Why is no real title available?)
- scientific article; zbMATH DE number 4047120 (Why is no real title available?)
- Fault-tolerant schemes for some systolic systems
- scientific article; zbMATH DE number 17546 (Why is no real title available?)
- SYSTOLIC TREE WITH BASE AUTOMATA
- scientific article; zbMATH DE number 166925 (Why is no real title available?)
- scientific article; zbMATH DE number 1154159 (Why is no real title available?)
- On the equivalence of linear conjunctive grammars and trellis automata
- Linear grammars with one-sided contexts and their automaton representation
- On the number of nonterminals in linear conjunctive grammars
- A simple P-complete problem and its language-theoretic representations
- \(\mathrm{GF}(2)\)-operations on basic families of formal languages
- Nondeterministic, probabilistic and alternating computations on cellular array models
- Characterizations and computational complexity of systolic trellis automata
- On a family of L languages resulting from systolic tree automata
- Synthesis, structure and power of systolic computations
This page was built for publication: Systolic trellis automatat†
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3687723)