Systolic trellis automata: Stability, decidability and complexity
From MaRDI portal
Publication:3030260
DOI10.1016/S0019-9958(86)80011-0zbMath0626.68048OpenAlexW2094323437MaRDI QIDQ3030260
Karel II Culik, Jozef Gruska, Arto Salomaa
Publication date: 1986
Published in: Information and Control (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0019-9958(86)80011-0
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Cellular automata (computational aspects) (68Q80)
Related Items
Boolean grammars ⋮ On the equivalence of linear conjunctive grammars and trellis automata ⋮ On the number of nonterminals in linear conjunctive grammars ⋮ Recognition of poly-slender context-free languages by trellis automata ⋮ Power of interconnections and of nondeterminism in regularY-tree systolic automata ⋮ Unnamed Item ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ Synthesis, structure and power of systolic computations ⋮ Sur quelques classes d’applications de $N^2$ dans les ensembles finis ⋮ Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth ⋮ BOOLEAN GRAMMARS AND GSM MAPPINGS ⋮ On spiking neural P systems ⋮ Characterizations and computational complexity of systolic trellis automata ⋮ Systolic trellis automatata † ⋮ Languages accepted by systolic \(Y\)-tree automata: Structural characterizations ⋮ Classes of systolic \(Y\)-tree automata and a comparison with systolic trellis automata
