Two-Dimensional Languages
Published 1 January 1997
Dora Giammarresi, Antonio Restivo
Citations412
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The aim of this chapter is to generalize concepts and techniques of formal language theory to two dimensions.
Abstract
The aim of this chapter is to generalize concepts and techniques of formal language theory to two dimensions. Informally, a two-dimensional string is called a picture and is defined as a rectangular array of symbols taken from a finite alphabet. A two-dimensional language (or picture language) is a set of pictures.KeywordsRegular ExpressionLocal LanguageFinite AutomatonTiling SystemFinite AlphabetThese keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
Keywords
Computer ScienceBiochemistry, Genetics and Molecular Biology
Mathematics and Computers in SimulationIntroduction to automata theory, languages and computation
10,827 Citations1981
Medical Entomology and ZoologyHandbook of theoretical computer science
4,202 Citations1990Jan Van Leeuwen
Weak Second-Order Arithmetic and Finite Automata
799 Citations1990J. Richakd Büchi
Studies in logic and the foundations of mathematicsThe Algebraic Theory of Context-Free Languages
696 Citations1963Noam Chomsky, M. P. Schützenberger
This chapter discusses the several classes of sentence-generating devices that are closely related, in various ways, to the grammars of both natural languages and artificial languages of various kinds.
Birkhäuser Boston eBooksFinite Automata, Formal Logic, and Circuit Complexity
404 Citations1994Howard Straubing
Regular languages and circuit complexity: regular languages in NC1 formulas with arbitrary numerical predicates regular languages and non-regular numerical predicates special cases of the central conjecture.
Elsevier eBooksGraph Rewriting: An Algebraic and Logic Approach
356 Citations1990B. Courcelle
This chapter presents three mathematical tools that can be used to describe graph-grammars and the sets generated by them, and presents the use of category theory for specifying graph rewriting rules in a precise and concise way.
Graph Rewriting: An Algebraic and Logic Approach.
216 Citations1990Bruno Courcelle
Picture languages: Formal models for picture recognition
176 Citations1979Azriel Rosenfeld
Information and ControlPicture languages with array rewriting rules
141 Citations1973Gift Siromoney, Rani Siromoney +1 more
Generative models of picture languages with array rewriting rules are presented and each letter of the alphabet of different sizes can be generated by a context-free array grammar.
Information SciencesSome properties of two-dimensional on-line tessellation acceptors
140 Citations1977Katsushi Inoue, Akira Nakamura
The purpose of this paper is to propose a new type acceptor called the “two-dimensional on-line tessellation acceptor” (denoted by “2-ota”) and to examine several properties of the 2-ota, which might be considered as a real-time mode of rectangular array bounded cellular space.
Information and ComputationMonadic Second-Order Logic over Rectangular Pictures and Recognizability by Tiling Systems
97 Citations1996Dora Giammarresi, Antonio Restivo +2 more
It is shown that a set of pictures is recognized by a finite tiling system iff it is definable in existential monadic second-order logic, which generalizes finite-state recognizability over strings and also matches a natural logic.
Information SciencesA survey of two-dimensional automata theory
94 Citations1991Katsushi Inoue, Itsuo Takanami
The main purpose of this paper is to survey several properties of alternating, nondeterministic, and deterministic two-dimensional Turing machines (including two- dimension finite automata and marker automata), and to briefly survey cellular types of two- dimensional automata.
Lecture notes in computer scienceOn logics, tilings, and automata
83 Citations1991Wolfgang Thomas
A notion of “graph acceptor” is introduced which can specify monadic second-order properties and allows to treat known types of finite automata in a common framework.
Information and ControlOn equal matrix languages
66 Citations1969Rani Siromoney
A generative grammar called equal matrix grammar which generates a class which meets both context-sensitive and context-free languages is defined and the formal power series generated by context- Free Grammars is extended to grammars of this system.
Information Processing LettersA note on two-dimensional finite automata
49 Citations1978Katsushi Inoue, Itsuo Takanami +1 more
The space complexities necessary and sufficient for seven-way four- dimensional Turing machines to simulate four-dimensional finite automata are shown, where each sidelength of each input tape of these automata is equivalent.
International Journal of Computer MathematicsParallel/sequential rectangular arrays with tables
42 Citations1977Rani Siromoney, K. G. Subramanian +1 more
Parallel/sequential generative models with tables are introduced and properties studied which have higher generative capacity than earlier matrix models which extend the essence of restricted parallelism to two dimensional grammars.
Lecture notes in computer scienceA characterization of recognizable picture languages
41 Citations1992Katsushi Inoue, Itsuo Takanami
Information and ControlParallel context-free languages
40 Citations1974Rani Siromoney, Kamala Krithivasan
The parallel context-free languages form a proper subclass of the context-sensitive languages and are closed under union, product, Kleene closure, and homomorphism.
Fundamenta InformaticaeTWO-DIMENSIONAL FINITE STATE RECOGNIZABILITY
36 Citations1996Dora Giammarresi, Antonio Restivo
It is shown that some natural families of two-dimensional languages (finite languages, regular languages, locally testable languages) are recognizable and that the emptyness problem is undecidable for this family of languages.
On monadic NP vs. monadic co-NP
32 Citations2002Ronald Fagin, Larry Stockmeyer +1 more
It is proved that connectivity of finite graphs is not in monadic NP, even in the presence of arbitrary built-in relations of moderate degree, which results in a strong separation between monadicNP and monadic co-NP.
Lecture notes in computer scienceAdvances in array languages
25 Citations1987Rani Siromoney
The construction of the public key cryptosystems for picture languages opens up a new vista of applications for array grammars and the unambiguity requirement may be removed provided the authors use array codes for encryption.
Information SciencesThree-way automata on rectangular tapes over a one-letter alphabet
19 Citations1985Efim Kinber
Necessary conditions for the languages recognized by three-way automata on tapes over a one-letter alphabet are obtained and nondeterministic three- way automata are proved to be more powerful than deterministic automata.
Journal of CyberneticsSequential/Parallel Matrix Array Languages
19 Citations1975Patrick S. Wang
The new system of matrix grammars for two-dimensional pattern processing is introduced and provides a compromise between purely sequential methods which take too much time for large arrays and purely parallel methods which usually takes too much hardware for large array methods.
International Journal of Computer MathematicsTwo-dimensional finite automata and unacceptable functions
17 Citations1979Katsushi Inoue, Akira Nakamura
This note first introduces the concept of “functions acceptable by two-dimensional finite automata” and then gives several functions unacceptable by three-dimensional infinite automata.
Developments in Language TheoryTwo-Dimensional Languages and Recognizable Functions.
17 Citations1993Dora Giammarresi
International Journal of Pattern Recognition and Artificial IntelligencePARALLEL GENERATION OF FINITE IMAGES
15 Citations1989Maurice Nivat, A. Saoudi +1 more
A syntactic model for generating sets of images, where an image can be viewed as an array over finite alphabet is defined, called image grammar, which can be considered as a generalization of classical Chomsky grammar.
International Journal of Computer MathematicsParallel generation of infinite images
3 Citations1990Maurice Nivat, A. Saoudi +1 more
A syntactic model for generating sets of finite and infinite images where a finite image can be viewed as an array over finite alphabet and an infinite image is an array with finite number of columns and infinite number of rows is introduced.