The subject of this chapter is the study of formal languages (mostly languages recognizable
by finite automata) in the framework of mathematical logic. The connection between …

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 …

It is well known that every algorithmic problem definable by a formula of first-order logic can
be solved in polynomial time, since all these problems are in L (see Aho and Ullman (1979) …

Graph languages are sets of labeled graphs. They can be generated by graph grammars,
and in particular by context-free graph grammars. There are several types of context-free …

In dynamical systems such as cellular automata and iterated maps, it is often useful to look
at a language or set of symbol sequences produced by the system. There are well …

We review, in a unified framework, translations from five different logics—monadic second-
order logic of one and two successors (S1S and S2S), linear-time temporal logic (LTL) …

In [2], Giammarresi and Restivo define the notion of local picture languages by giving a set
of authorized 2× 2 tiles over∑∪{#} where# is a boundary symbol which surrounds the …

Weighted automata are classical finite automata in which the transitions carry weights. 7
These weights may model quantitative properties like the amount of resources needed for …

Regular expressions and context-free grammars for picture languages Page 1 Regular
Expressions and Context-Free Grammars for Picture Languages Oliver Matz Institut fiir Informatik …

We consider the family UREC of unambiguous recognizable two-dimensional languages.
We prove that there are recognizable languages that are inherently ambiguous, that is …