Publication:3926078

Publication date: 1979

digital geometry; array grammars; two-dimensional automata; language hierarchies; cellular array acceptors; recognizing devices; sequential array acceptors

Mathematics Subject Classification ID

68-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science

68Q45: Formal languages and automata

68T10: Pattern recognition, speech recognition

68Q80: Cellular automata (computational aspects)

68-02: Research exposition (monographs, survey articles) pertaining to computer science

Related Items

A NOTE ON REBOUND TURING MACHINES, LINGUISTIC GEOMETRY: METHODOLOGY AND TECHNIQUES, A note on one-pebble two-dimensional Turing machines, A note on one-pebble two-dimensional Turing machines, Probabilistic rebound Turing machines, A relationship between two-dimensional finite automata and three-way tape-bounded two-dimensional Turing machines, Semi-metrics, closure spaces and digital topology, An application of array grammars to clustering analysis for syntactic patterns, A note on array grammars, Two-dimensional alternative Turing machines, On the complexity of the recognition of parallel 2D-image languages, Multiset random context grammars, checkers, and transducers, Complexity and decidability for restricted classes of picture languages, Picture iteration and picture ambiguity, A note on time-bounded bottom-up pyramid cellular acceptors, Computer graphics and connected topologies on finite ordered sets, Slender Siromoney matrix languages, A quotient-universal digital topology, Pure 2D picture grammars and languages, On a relationship between graph L-systems and picture languages, ``Shape theory and Pattern Recognition, Complexity and decidability for chain code picture languages, The complexity of some decision problems about two-dimensional array grammars, Parallel and sequential transformations on digital images, A note on an extension of matrix grammars generating two-dimensional languages, Computation theory of cellular automata, Fast parallel language recognition by cellular automata, Three-way automata on rectangular types over a one-letter alphabet, Direction-independent application of productions on two-dimensional arrays, Context dependent table matrix L systems, On pebble automata, A hierarchy of random-context grammars and automata, On two-dimensional pattern-matching languages and their decision problems, Direction-independent grammars with contexts, Several properties of array languages, The membership and equivalence problems for picture languages, Detection of interlocking components in three-dimensional digital pictures, Predecessor states for certain cellular automata evolutions, A remark on two-dimensional finite automata, 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, A characterization of context-free string languages by directed node- label controlled graph grammars, Some remarks on one-pebble rectangular array acceptors, Acceptors for isometric parallel context-free array languages, A note on three-dimensional finite automata, A new hierarchy of two-dimensional array languages, A Jordan surface theorem for three-dimensional digital spaces, Machine characterization of (E0L-E0L) array languages, Graph grammars with path-controlled embedding, Connectedness of coherent fuzzy pictures, Three-dimensional connected pictures are not recognizable by finite-state acceptors, Digital Jordan curves---a graph-theoretical approach to a topological theorem, A note on alternative digital topologies, The topology of digital images, A note on two-dimensional probabilistic finite automata, A note on three-dimensional alternating Turing machines with space smaller than $\log m$, Simulation of three-dimensional one-marker automata by five-way Turing machines, Retreat bounded picture languages, Network languages for intelligent control, Network languages for concurrent multiagent systems, Context-sensitive string languages and recognizable picture languages, A definition of surfaces of ${\mathbb{Z}}^{3}$. A new 3D discrete Jordan theorem, Leftmove-bounded picture languages, Centers of sets of pixels, Tree-based picture generation, Two-dimensional connected pictures are not recognizable by finite-state acceptors, Closure properties of the classes of sets recognized by space-bounded two-dimensional probabilistic Turing machines, A note on two-dimensional probabilistic Turing machines, Pictures of functions and their acceptability by automata, Infinite arrays and infinite computations, Non-closure property of space-bounded two-dimensional alternating Turing machines, Complexity of perceptron recognition for a class of geometric patterns., On regular drawn symbolic picture languages, On piecewise linear approximation of planar Jordan curves, A CKY parser for picture grammars, Digital Jordan curves, Picture deformation, Picture languages: tiling systems versus tile rewriting grammars., A proof of image Euler number formula, Some properties of one-pebble Turing machines with sublogarithmic space, Salient and reentrant points of discrete sets, Random context structure grammars and automata - a formal approach, A survey of two-dimensional automata theory, A characterization of constant-time cellular automata computation, An alternative digital topology, Salient and Reentrant Points of Discrete Sets, Jordan Curve Theorems with Respect to Certain Pretopologies on $\mathbb Z^2$, Complete symmetry in d2l systems and cellular automata, Syntactic/semantic techniques in pattern recognition: A survey