A property of real-time trellis automata

DOI10.1016/0166-218X(86)90025-9zbMath0597.68048OpenAlexW2019846069MaRDI QIDQ1079372

Sheng Yu

Publication date: 1986

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(86)90025-9

zbMATH Keywords

real-time acceptance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Cellular automata (computational aspects) (68Q80)

Related Items

Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ \(\mathrm{GF}(2)\)-operations on basic families of formal languages ⋮ Linear-space recognition for grammars with contexts ⋮ On hardest languages for one-dimensional cellular automata ⋮ On hardest languages for one-dimensional cellular automata ⋮ Expressive power of \(\text{LL}(k)\) Boolean grammars ⋮ Linear grammars with one-sided contexts and their automaton representation

Cites Work

• On real-time cellular automata and trellis automata
• Characterizations and computational complexity of systolic trellis automata
• Systolic trellis automatata †
• Systolic trellis automatat†

This page was built for publication: A property of real-time trellis automata