Systolic trellis automata: Stability, decidability and complexity

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

zbMATH Keywords

closure propertiessuperstabilitycomplexity classessystolic trellis automata

Mathematics Subject Classification ID

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