A survey of two-dimensional automata theory
From MaRDI portal
Publication:2638801
DOI10.1016/0020-0255(91)90008-IzbMATH Open0717.68071MaRDI QIDQ2638801FDOQ2638801
Authors: Katsushi Inoue, Itsuo Takanami 
Publication date: 1991
Published in: Information Sciences (Search for Journal in Brave)
Recommendations
- Some remarks on two-dimensional finite automata
- Some results concerning two-dimensional turing machines and finite automata
- Developments in Language Theory
- Two-dimensional rational automata: a bridge unifying one- and two-dimensional language theory
- Degrees of restriction for two-dimensional automata
- Two-dimensional sgraffito automata
- Two-dimensional Sgraffito automata
- A note on two-dimensional probabilistic finite automata
- Towards more expressive 2D deterministic automata
- Equivalence of two-dimensional multitape automata
Cites Work
- Relationships between nondeterministic and deterministic tape complexities
- Title not available (Why is that?)
- Nondeterministic Space is Closed under Complementation
- Alternation
- Title not available (Why is that?)
- The method of forced enumeration for nondeterministic automata
- Halting space-bounded computations
- Title not available (Why is that?)
- One-way bounded cellular automata
- Automata and Labyrinths
- Real-time language recognition by one-dimensional cellular automata
- On real-time cellular automata and trellis automata
- Three-way tape-bounded two-dimensional Turing machines
- A note on deterministic three-way tape-bounded two-dimensional Turing machines
- Some properties of two-dimensional on-line tessellation acceptors
- Lower bounds for language recognition on two-dimensional alternating multihead machines
- Two-dimensional alternating turing machines with only universal states
- Title not available (Why is that?)
- A note on time-bounded bottom-up pyramid cellular acceptors
- Deterministic two-dimensional on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through 180\(\circ\)-rotation
- Title not available (Why is that?)
- Two-dimensional alternative Turing machines
- Parallel Image Processing by Memory-Augmented Cellular Automata
- A note on two-dimensional finite automata
- A note on bottom-up pyramid acceptors
- A note on closure properties of the classes of sets accepted by tape- bounded two-dimensional Turing machines
- Closure properties of three-way and four-way tape-bounded two-dimensional Turing machines
- Real-time recognition of two-dimensional tapes by cellular automata
- Triangle cellular automata
- Extended controlled table L-arrays
- One-Pass Complexity of Digital Picture Properties
- Three-way automata on rectangular types over a one-letter alphabet
- A note on three-way two dimensional alternating Turing machines
- Title not available (Why is that?)
- Two-dimensional finite automata and unacceptable functions
- A finite 5-pebble-automaton can search every maze
- Two-dimensional pattern matching by two-dimensional on-line tessellation acceptors
- Title not available (Why is that?)
- Recognition of topological equivalence of patterns by array automata
- Parallel/sequential array automata
- Finite-Turn Repetitive Checking Automata and Sequential/ Parallel Matrix Languages
- Array automata and operations on array languages
- Two-dimensional multipass on-line tessellation acceptors
- Title not available (Why is that?)
- T-recognition of T-languages, a new approach to describe and program the parallel pattern recognition capabilities of d-dimensional tessellation structures
- A note on decision problems for three-way two-dimensional finite automata
- A hierarchy of random-context grammars and automata
- There are no fully space constructible functions between log log n and log n
- On Some Open Problems in the Theory of Cellular Automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- Cyclic closure properties of automata on a two-dimensional tape
- Three-way two-dimensional multicounter automata
- Nonclosure property of nondeterministic two-dimensional finite automata under cyclic closure
- Relation of one-way parallel/sequential automata to 2-D finite-state automata
- Some notes on finite-state picture languages
- Pushdown automata on arrays
- Acceptors for isometric parallel context-free array languages
- Some results concerning automata on two-dimensional tapes
- Connected pictures are not recognizable by deterministic two-dimensional on-line tessellation acceptors
- Simulation of three-dimensional one-marker automata by five-way Turing machines
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A region crossing problem for array-bounded automata
Cited In (29)
- Reversibility of computations in graph-walking automata
- Relative approximate bisimulations for fuzzy picture automata
- TRANSITIVITY IN TWO-DIMENSIONAL LOCAL LANGUAGES DEFINED BY DOT SYSTEMS
- Decision problems and projection languages for restricted variants of two-dimensional automata
- Concatenation operations and restricted variants of two-dimensional automata
- Three-way two-dimensional alternating finite automata with rotated inputs
- Towards more expressive 2D deterministic automata
- Simple picture processing based on finite automata and regular grammars
- Two-way Automata and Regular Languages of Overlapping Tiles
- Regular binoid expressions and regular binoid languages.
- Degrees of restriction for two-dimensional automata
- Title not available (Why is that?)
- A note on three-dimensional alternating Turing machines with space smaller than \(\log m\)
- Plane-walking automata
- Weighted picture automata and weighted logics
- Snake-Deterministic Tiling Systems
- Two dimensional fuzzy regular languages
- Title not available (Why is that?)
- Non-closure property of space-bounded two-dimensional alternating Turing machines
- A Nivat theorem for weighted picture automata and weighted MSO logic
- On space functions fully constructed by two-dimensional Turing machines
- Title not available (Why is that?)
- Two-dimensional automata with rotated inputs (projection-type)
- Characterizations of recognizable picture series
- A Nivat theorem for weighted picture automata and weighted MSO logics
- Some results concerning two-dimensional turing machines and finite automata
- Two-Dimensional Limited Context Restarting Automata
- Finite state automata representing two-dimensional subshifts
- A survey on picture-walking automata
This page was built for publication: A survey of two-dimensional automata theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2638801)
