Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Classes of Picture Languages D...

Classes of Picture Languages Defined by Tiling Systems, Automata and Closure Properties

Ville Salo, Classes of Picture Languages Defined by Tiling Systems, Automata and Closure Properties. TUCS Technical Reports 1007, Turku Centre for Computer Science, 2011.

Abstract:

This thesis is about classes of picture languages, relations between them and languages they do and do not contain. The theory of picture languages is a lesser-known branch of formal language theory that studies languages of finite two-dimensional matrices called pictures. Many models have been introduced for defining picture languages, and in this thesis we investigate, in depth, classes of picture languages defined by tiling systems, automata and closure properties. In addition to results about the kinds of languages contained in each class, we have aimed for a relatively complete presentation of the interesting relations between the classes. In particular, we have tried to include the most interesting proof techniques used in the field. We give detailed and complete proofs for most of the theorems we state, usually with an original proof.

The thesis contains many new results, and many answers to questions asked in the literature. The most interesting of these is the proof that (picture-walking) nondeterministic finite state automata run on pictures give the same class of languages whether or not they are allowed to exist the domain of the picture. A similar question, also asked in the literature, of whether the same is true for alternating finite state automata, is answered in the other direction. We also prove that the class defined by so-called right linear grammars is a subclass of the class of picture languages defined by north-west deterministic tiling systems, which was asked in the Handbook of Formal Languages. We also prove many other natural theorems not previously known, for instance the inclusion of the class of locally threshold testable languages to the class defined by north-west deterministic tiling systems

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tSalo11a,
  title = {Classes of Picture Languages Defined by Tiling Systems, Automata and Closure Properties},
  author = {Salo, Ville},
  number = {1007},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2011},
  keywords = {picture languages, tiling systems, automata, closure properties},
  ISBN = {978-952-12-2584-0},
}

Belongs to TUCS Research Unit(s): Other

Edit publication