Academic
Publications
Some properties of two-dimensional on-line tessellation acceptors

Some properties of two-dimensional on-line tessellation acceptors,10.1016/0020-0255(77)90023-8,Information Sciences,Katsushi Inoue,Akira Nakamura

Some properties of two-dimensional on-line tessellation acceptors   (Citations: 62)
BibTex | RIS | RefWorks Download
Journal: Information Sciences - ISCI , vol. 13, no. 2, pp. 95-121, 1977
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...In the literature, a variety of formal models to recognize or generate two-dimensional arrays of symbols, called pictures, have been proposed [3, 18, 20, 24, 37, 39] and various properties of string languages have been formulated for two dimensions [4–6, 22, 28, 29]...
    • ...The work of several authors can combined to an equivalence theorem for picture languages describing recognizable languages in terms of types of automata, sets of tiles, rational operations or existential monadic second-order (MSO) logic [4, 17, 19, 20, 24]...
    • ...This model extends the known notion of 2dimensional on-line tessellation automata (2OTA) [20] for picture languages...
    • ...1 We assume a picture to be non-empty for technical simplicity, as in [3, 20, 24]...
    • ...We fix an alphabet � . In the literature, there are many equivalent models defining or recognizing picture languages in terms of projections of local languages (tiling systems) and rational expressions [16–18], domino systems [24], two-dimensional on-line tessellation automata (2OTA) [20, 21], monadic second-order (MSO) logic [19] or quadrapolic picture automata (also known as Wang systems) [4, 7]. These devices characterize recognizable ...

    Ina Fichtner. Weighted Picture Automata and Weighted Logics

    • ...REC is a robust class that has various characterizations: for instance it is the class of picture languages that can be generated by online tessellation automata [13], tiling systems [11], or Wang systems [10]...
    • ...Wang automata combine features of both online tessellation acceptors [13] and 4-ways automata [14]: as in online tessellation acceptors,...
    • ...Online tessellation acceptors have a diagonal-based kind of determinism [13] and this notion is extended in [1], with the definition of a deterministic class we denote by Diag-DREC (the original name was DREC)...
    • ...Diagonal determinism [1] is inspired by the deterministic version of online tessellation acceptors [13], which are directed according to a corner-to-corner direction (namely, from top-left to bottom-right, or tl2br)...

    Violetta Lonatiet al. Picture Recognizability with Automata Based on Wang Tiles

    • ...Online tessellation automaton is a recognizing device for accepting finite arrays [4] . Online tessellation au­ tomaton reads elements diagonalwise...
    • ...Definition 2.3: [4] A two dimensional online tessel­ lation automaton A = (Q, E, Qo, 8, F) where Q -is a finite set of states E -is a input alphabet Qo � Q - is a set of initial states F � Q - is a set of final states and 8 : Q x Q x E --+ 2Q is a transition function...

    Mary Jemima Samuelet al. Watson-Crick online tessellation automaton and timed Watson-Crick ω-au...

    • ...Let us have a picture over alphabet A. First of all, we extend this picture with a special border symbol #, # � A. Let us denote the alphabet of pictures extended this way by A#, A# = A ∪{ #}. This technique is commonly used in several other methods, namely as an input for two-dimensional on-line tessellation acceptors [12,1]...

    Jan Zd'Áreket al. A Note on a Tree-Based 2D Indexing

    • ...Since then, many approaches have been presented in the literature in order to find in 2D a counterpart of what regular languages are in one dimension: finite automata, grammars, logics and regular expressions (see for example [6,10,21,14,23])...
    • ...Moreover in [15], it is proved that REC have a counterpart as machine models in the two-dimensional on-line tessellation acceptor (OTA) introduced by K. Inoue and A. Nakamura in [14]...
    • ...Deterministic machine models to recognize two-dimensional languages have been considered in the literature: they always accept classes of languages smaller than the corresponding non-deterministic ones (see for example, [5,14,22])...

    Dora Giammarresi. A Brief Excursion Inside the Class of Tiling Recognizable Two-Dimensio...

Sort by: