Some properties of two-dimensional on-line tessellation acceptors

DOI10.1016/0020-0255(77)90023-8zbMath0371.94067OpenAlexW1999455192MaRDI QIDQ1244324

Publication date: 1977

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0255(77)90023-8

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Pattern recognition, speech recognition (68T10) Automata and formal grammars in connection with logical questions (03D05)

Related Items (71)

Three-way two-dimensional finite automata with rotated inputs ⋮ EMSO-logic and automata related to homogeneous flow event structures ⋮ A hierarchy of random-context grammars and automata ⋮ A computational model for tiling recognizable two-dimensional languages ⋮ EXPLORING INSIDE TILING RECOGNIZABLE PICTURE LANGUAGES TO FIND DETERMINISTIC SUBCLASSES ⋮ Snake-Deterministic Tiling Systems ⋮ Random context structure grammars and automata - a formal approach ⋮ A survey of two-dimensional automata theory ⋮ A note on three-way two dimensional alternating Turing machines ⋮ Two-Dimensional Rational Automata: A Bridge Unifying One- and Two-Dimensional Language Theory ⋮ HYPERGRAPH AUTOMATA: A THEORETICAL MODEL FOR PATTERNED SELF-ASSEMBLY ⋮ A relationship between two-dimensional finite automata and three-way tape-bounded two-dimensional Turing machines ⋮ Context-sensitive string languages and recognizable picture languages ⋮ Three-dimensional alternating Turing machines with only universal states ⋮ Recognizable picture languages and domino tiling ⋮ TREE-BASED 2D INDEXING ⋮ 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 ⋮ Tiling Automaton: A Computational Model for Recognizable Two-Dimensional Languages ⋮ Non-recursive trade-offs between two-dimensional automata and grammars ⋮ Three-way tape-bounded two-dimensional Turing machines ⋮ Three-way two-dimensional multicounter automata ⋮ Real-time recognition of two-dimensional tapes by cellular automata ⋮ Two-dimensional cellular automata and deterministic on-line tessalation automata ⋮ A Nivat theorem for weighted picture automata and weighted MSO logics ⋮ Recognizable series on graphs and hypergraphs ⋮ A remark on two-dimensional finite automata ⋮ A note on deterministic three-way tape-bounded two-dimensional Turing machines ⋮ Two-dimensional automata with rotated inputs ⋮ Nonclosure property of nondeterministic two-dimensional finite automata under cyclic closure ⋮ Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs ⋮ Weighted picture automata and weighted logics ⋮ Complexity of Matching Sets of Two-Dimensional Patterns by Two-Dimensional On-Line Tessellation Automaton ⋮ Tiling Recognizable Two-Dimensional Languages ⋮ Recognizable vs. Regular Picture Languages ⋮ Deterministic Two-Dimensional Languages over One-Letter Alphabet ⋮ A note on rebound automata ⋮ A note on three-dimensional finite automata ⋮ A note on time-bounded bottom-up pyramid cellular acceptors ⋮ On the tiling system recognizability of various classes of convex polyominoes ⋮ A SAT-based parser and completer for pictures specified by tiling ⋮ Strategies to scan pictures with automata based on Wang tiles ⋮ Two-dimensional on-line tessellation acceptors are not closed under complement ⋮ Three-dimensional connected pictures are not recognizable by finite-state acceptors ⋮ Tile rewriting grammars and picture languages ⋮ New operations and regular expressions for two-dimensional languages over one-letter alphabet ⋮ Three-way two-dimensional alternating finite automata with rotated inputs ⋮ Picture languages: tiling systems versus tile rewriting grammars. ⋮ Two-dimensional pattern matching against local and regular-like picture languages ⋮ Towards More Expressive 2D Deterministic Automata ⋮ A note on two-dimensional finite automata ⋮ A Nivat Theorem for Weighted Picture Automata and Weighted MSO Logic ⋮ A Note on a Tree-Based 2D Indexing ⋮ Two-dimensional connected pictures are not recognizable by finite-state acceptors ⋮ Deterministic and unambiguous two-dimensional languages over one-letter alphabet ⋮ Deterministic ordered restarting automata for picture languages ⋮ A note on bottom-up pyramid acceptors ⋮ Characterizations of recognizable picture series ⋮ Complexity of Sets of Two-Dimensional Patterns ⋮ Deterministic two-dimensional on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through 180\(\circ\)-rotation ⋮ Two-dimensional models ⋮ Pictures of functions and their acceptability by automata ⋮ Two-dimensional cellular automata recognizer ⋮ Two-dimensional Sgraffito automata ⋮ Expressiveness and complexity of regular pure two-dimensional context-free languages ⋮ Two-dimensional pattern matching by two-dimensional on-line tessellation acceptors ⋮ Two-dimensional alternative Turing machines ⋮ Unambiguous recognizable two-dimensional languages ⋮ A note on three-dimensional alternating Turing machines with space smaller than \(\log m\) ⋮ Two-dimensional automata with rotated inputs (projection-type) ⋮ Some results concerning 2-D on-line tessellation acceptors and 2-D alternating finite automata

Cites Work

This page was built for publication: Some properties of two-dimensional on-line tessellation acceptors