Two-dimensional iterative arrays: Characterizations and applications

DOI10.1016/0304-3975(88)90163-6zbMath0644.68080OpenAlexW1982490259MaRDI QIDQ1102749

Oscar H. Ibarra, Michael A. Palis

Publication date: 1988

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(88)90163-6

zbMATH Keywords

Turing machinesnumber of processorssequential machine modelsspeeding uptwo-dimensional iterative and cellular arrays

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cellular automata (computational aspects) (68Q80) Theory of operating systems (68N25)

Related Items (10)

Two-dimensional iterative arrays: Characterizations and applications ⋮ Low complexity classes of multidimensional cellular automata ⋮ Hierarchies and undecidability results for iterative arrays with sparse communication ⋮ On some open problems concerning the complexity of cellular arrays ⋮ Synthesis, structure and power of systolic computations ⋮ Hierarchies and undecidability results for iterative arrays with sparse communication ⋮ Cellular automata with limited inter-cell bandwidth ⋮ Iterative arrays with finite inter-cell communication ⋮ Iterative arrays with finite inter-cell communication ⋮ Two-dimensional cellular automata recognizer

Cites Work

• Unnamed Item
• Unnamed Item
• Spacetime representations of computational structures
• Topological transformations as a tool in the design of systolic networks
• Two-dimensional iterative arrays: Characterizations and applications
• Deterministic one-way simulation of two-way real-time cellular automata and its related problems
• Iterative arrays with direct central control
• Real-time language recognition by one-dimensional cellular automata
• The Design of Optimal Systolic Arrays
• Partitioning and Mapping Algorithms into Fixed Size Systolic Arrays
• Parallel Parsing on a One-Way Array of Finite-State Machines
• One-way bounded cellular automata
• Speed of Recognition of Context-Free Languages by Array Automata
• On Some Open Problems in the Theory of Cellular Automata
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
• Cellular automata complexity trade-offs

This page was built for publication: Two-dimensional iterative arrays: Characterizations and applications