Characterizations and computational complexity of systolic trellis automata
From MaRDI portal
Publication:792091
DOI10.1016/0304-3975(84)90015-XzbMATH Open0536.68048OpenAlexW2085862166MaRDI QIDQ792091FDOQ792091
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
Recommendations
- Systolic trellis automata: Stability, decidability and complexity
- scientific article; zbMATH DE number 4030987
- Systolic trellis automatat†
- SIMULATION OF SYSTOLIC TREE AUTOMATA ON TRELLIS AUTOMATA
- scientific article; zbMATH DE number 4126708
- Systolic trellis automatata †
- Some computational limits of trellis automata
- scientific article; zbMATH DE number 17546
- scientific article; zbMATH DE number 3898246
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Relationships between nondeterministic and deterministic tape complexities
- An observation on time-storage trade off
- Systolic trellis automata: Stability, decidability and complexity
- An Approach to a Unified Theory of Automata
- Systolic trellis automatat†
- Systolic automata for VLSI on balanced trees
- Title not available (Why is that?)
- Storage requirements for deterministic polynomial time recognizable languages
- Abstract families of deterministic languages
Cited In (40)
- Synthesis, structure and power of systolic computations
- On the number of nonterminals in linear conjunctive grammars
- A simple P-complete problem and its language-theoretic representations
- Expressive power of \(\text{LL}(k)\) Boolean grammars
- Unambiguous Boolean grammars
- A property of real-time trellis automata
- On spiking neural P systems
- On the equivalence of linear conjunctive grammars and trellis automata
- A CHARACTERIZATION OF THE ARITHMETICAL HIERARCHY BY LANGUAGE EQUATIONS
- Power of interconnections and of nondeterminism in regularY-tree systolic automata
- On iterative and cellular tree arrays
- Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
- Title not available (Why is that?)
- Conjunctive and Boolean grammars: the true general case of the context-free grammars
- On hardest languages for one-dimensional cellular automata
- On some open problems concerning the complexity of cellular arrays
- The Boolean closure of linear context-free languages
- Title not available (Why is that?)
- Systolic trellis automata: Stability, decidability and complexity
- BOOLEAN GRAMMARS AND GSM MAPPINGS
- Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages
- \(\mathrm{GF}(2)\)-operations on basic families of formal languages
- Boolean grammars
- Fast parallel language recognition by cellular automata
- The complexity of systolic dissemination of information in interconnection networks
- Title not available (Why is that?)
- Title not available (Why is that?)
- Language equations
- Input-driven languages are linear conjunctive
- On the computational power of totalistic cellular automata
- On hardest languages for one-dimensional cellular automata
- Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
- Title not available (Why is that?)
- Linear grammars with one-sided contexts and their automaton representation
- Parallel parsing on a one-way linear array of finite-state machines
- Unambiguous conjunctive grammars over a one-symbol alphabet
- Title not available (Why is that?)
- Linear-space recognition for grammars with contexts
- Non-deterministic cellular automata and languages
- Nondeterministic, probabilistic and alternating computations on cellular array models
This page was built for publication: Characterizations and computational complexity of systolic trellis automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q792091)
