Optimal simulation of tree arrays by linear arrays

DOI10.1016/0020-0190(89)90230-5zbMath0672.68023OpenAlexW1964019173MaRDI QIDQ1120283

Oscar H. Ibarra, Tao Jiang

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90230-5

zbMATH Keywords

embeddinglinear arraystepwise simulationtree array

Mathematics Subject Classification ID

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

Related Items (1)

On some open problems concerning the complexity of cellular arrays

Cites Work

• On real-time cellular automata and trellis automata
• Iterative tree automata
• On One-Way Cellular Arrays
• Iterative tree arrays with logarithmic depth^†
• Triangle cellular automata
• Speed of Recognition of Context-Free Languages by Array Automata
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
• Cellular automata complexity trade-offs

This page was built for publication: Optimal simulation of tree arrays by linear arrays