A property of real-time trellis automata

DOI10.1016/0166-218X(86)90025-9MaRDI QIDQ1079372zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• scientific article; zbMATH DE number 4047120
• scientific article; zbMATH DE number 17546
• scientific article; zbMATH DE number 769370
• Some computational limits of trellis automata
• Systolic trellis automata: Stability, decidability and complexity

Cites work

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

Cited in

(10)

• Some computational limits of trellis automata
• Expressive power of \(\text{LL}(k)\) Boolean grammars
• scientific article; zbMATH DE number 1836421 (Why is no real title available?)
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• On hardest languages for one-dimensional cellular automata
• \(\mathrm{GF}(2)\)-operations on basic families of formal languages
• scientific article; zbMATH DE number 17546 (Why is no real title available?)
• On hardest languages for one-dimensional cellular automata
• Linear-space recognition for grammars with contexts
• Linear grammars with one-sided contexts and their automaton representation

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1079372)