Characterizations and computational complexity of systolic trellis automata

DOI10.1016/0304-3975(84)90015-XzbMath0536.68048OpenAlexW2085862166MaRDI QIDQ792091

Oscar H. Ibarra, Sam M. Kim

Publication date: 1984

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(84)90015-x

zbMATH Keywords

Turing machinesnetworks of finite processorssystolic trellis automata

Mathematics Subject Classification ID

Related Items (32)

A property of real-time trellis automata ⋮ Boolean grammars ⋮ Input-driven languages are linear conjunctive ⋮ On the equivalence of linear conjunctive grammars and trellis automata ⋮ On the number of nonterminals in linear conjunctive grammars ⋮ Power of interconnections and of nondeterminism in regularY-tree systolic automata ⋮ On iterative and cellular tree arrays ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ On the computational power of totalistic cellular automata ⋮ A simple P-complete problem and its language-theoretic representations ⋮ On some open problems concerning the complexity of cellular arrays ⋮ \(\mathrm{GF}(2)\)-operations on basic families of formal languages ⋮ Linear-space recognition for grammars with contexts ⋮ Synthesis, structure and power of systolic computations ⋮ The Boolean closure of linear context-free languages ⋮ The complexity of systolic dissemination of information in interconnection networks ⋮ On hardest languages for one-dimensional cellular automata ⋮ Parallel parsing on a one-way linear array of finite-state machines ⋮ A CHARACTERIZATION OF THE ARITHMETICAL HIERARCHY BY LANGUAGE EQUATIONS ⋮ Nondeterministic, probabilistic and alternating computations on cellular array models ⋮ Unambiguous Boolean grammars ⋮ Unambiguous conjunctive grammars over a one-symbol alphabet ⋮ Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth ⋮ On hardest languages for one-dimensional cellular automata ⋮ Expressive power of \(\text{LL}(k)\) Boolean grammars ⋮ BOOLEAN GRAMMARS AND GSM MAPPINGS ⋮ On spiking neural P systems ⋮ Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages ⋮ Language equations ⋮ Linear grammars with one-sided contexts and their automaton representation ⋮ Non-deterministic cellular automata and languages ⋮ Fast parallel language recognition by cellular automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Systolic automata for VLSI on balanced trees
• An observation on time-storage trade off
• Storage requirements for deterministic polynomial time recognizable languages
• Relationships between nondeterministic and deterministic tape complexities
• Systolic trellis automata: Stability, decidability and complexity
• Systolic trellis automatat†
• Abstract families of deterministic languages
• An Approach to a Unified Theory of Automata

This page was built for publication: Characterizations and computational complexity of systolic trellis automata