A survey of two-dimensional automata theory
From MaRDI portal
Publication:2638801
DOI10.1016/0020-0255(91)90008-IzbMath0717.68071MaRDI QIDQ2638801
Katsushi Inoue, Itsuo Takanami
Publication date: 1991
Published in: Information Sciences (Search for Journal in Brave)
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (22)
Concatenation operations and restricted variants of two-dimensional automata ⋮ TRANSITIVITY IN TWO-DIMENSIONAL LOCAL LANGUAGES DEFINED BY DOT SYSTEMS ⋮ Some results concerning two-dimensional turing machines and finite automata ⋮ On space functions fully constructed by two-dimensional Turing machines ⋮ Snake-Deterministic Tiling Systems ⋮ Two dimensional fuzzy regular languages ⋮ A Nivat theorem for weighted picture automata and weighted MSO logics ⋮ Regular binoid expressions and regular binoid languages. ⋮ Weighted picture automata and weighted logics ⋮ Unnamed Item ⋮ Reversibility of computations in graph-walking automata ⋮ Simple picture processing based on finite automata and regular grammars ⋮ Three-way two-dimensional alternating finite automata with rotated inputs ⋮ Decision problems and projection languages for restricted variants of two-dimensional automata ⋮ Towards More Expressive 2D Deterministic Automata ⋮ A Nivat Theorem for Weighted Picture Automata and Weighted MSO Logic ⋮ Characterizations of recognizable picture series ⋮ A Survey on Picture-Walking Automata ⋮ Plane-Walking Automata ⋮ A note on three-dimensional alternating Turing machines with space smaller than \(\log m\) ⋮ Non-closure property of space-bounded two-dimensional alternating Turing machines ⋮ Degrees of restriction for two-dimensional automata
Cites Work
- A note on bottom-up pyramid acceptors
- On real-time cellular automata and trellis automata
- Two-dimensional alternative Turing machines
- A note on time-bounded bottom-up pyramid cellular acceptors
- A finite 5-pebble-automaton can search every maze
- Two-dimensional pattern matching by two-dimensional on-line tessellation acceptors
- Three-way automata on rectangular types over a one-letter alphabet
- T-recognition of T-languages, a new approach to describe and program the parallel pattern recognition capabilities of d-dimensional tessellation structures
- A hierarchy of random-context grammars and automata
- The method of forced enumeration for nondeterministic automata
- There are no fully space constructible functions between log log n and log n
- A note on three-way two dimensional alternating Turing machines
- Lower bounds for language recognition on two-dimensional alternating multihead machines
- Halting space-bounded computations
- A note on closure properties of the classes of sets accepted by tape- bounded two-dimensional Turing machines
- Cyclic closure properties of automata on a two-dimensional tape
- Three-way tape-bounded two-dimensional Turing machines
- Closure properties of three-way and four-way tape-bounded two-dimensional Turing machines
- Three-way two-dimensional multicounter automata
- Real-time recognition of two-dimensional tapes by cellular automata
- Recognition of topological equivalence of patterns by array automata
- A note on deterministic three-way tape-bounded two-dimensional Turing machines
- Nonclosure property of nondeterministic two-dimensional finite automata under cyclic closure
- A note on decision problems for three-way two-dimensional finite automata
- Relation of one-way parallel/sequential automata to 2-D finite-state automata
- Pushdown automata on arrays
- Acceptors for isometric parallel context-free array languages
- Some properties of two-dimensional on-line tessellation acceptors
- A note on two-dimensional finite automata
- Simulation of three-dimensional one-marker automata by five-way Turing machines
- Deterministic two-dimensional on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through 180\(\circ\)-rotation
- Parallel/sequential array automata
- Relationships between nondeterministic and deterministic tape complexities
- Real-time language recognition by one-dimensional cellular automata
- Two-dimensional finite automata and unacceptable functions
- Two-dimensional alternating turing machines with only universal states
- Connected pictures are not recognizable by deterministic two-dimensional on-line tessellation acceptors
- Nondeterministic Space is Closed under Complementation
- One-way bounded cellular automata
- Parallel Image Processing by Memory-Augmented Cellular Automata
- Triangle cellular automata
- Finite-Turn Repetitive Checking Automata and Sequential/ Parallel Matrix Languages
- Alternation
- Array automata and operations on array languages
- A region crossing problem for array-bounded automata
- Some notes on finite-state picture languages
- Some results concerning automata on two-dimensional tapes
- Extended controlled table L-arrays
- Automata and Labyrinths
- Two-dimensional multipass on-line tessellation acceptors
- On Some Open Problems in the Theory of Cellular Automata
- One-Pass Complexity of Digital Picture Properties
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A survey of two-dimensional automata theory
