Characterizations and computational complexity of systolic trellis automata

DOI10.1016/0304-3975(84)90015-XzbMath0536.68048MaRDI 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 machines; networks of finite processors; systolic trellis automata

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

Related Items

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