Contribution to two-dimensional languages

             Daniel Prusa

          Daniel.Prusa@Sun.COM

The thesis "Two-dimensional Languages" studies generalizations of the
theory of formal languages to two dimensions. The basic structure the
theory works with is a two-dimensional array of symbols in a finite
alphabet. This structure is called a picture and it is the
generalization of the one-dimensional word.

The goal of the thesis was to study two-dimensional
computational/generative models (their properties, time complexity,
comparison of the computational/generative power, etc.) and also to
contribute to the question whether the Chomsky hierarchy can be
generalized to two dimensions.

The studied models are as follows: two-dimensional Turing machine
(2TM), two-dimensional finite-state automaton (2FSA), two-dimensional
forgetting automaton (2FA), two-dimensional on-line tessellation
automaton (2OTA) and grammars with productions in context-free form
(CFGP).

This selection was influented by the question of possibilities how to
generalize the Chomsky hierarchy. The class of languages recognizable
by 2FSA is the natural candidate for the generalization of the regular
languages, however, there are many properties of the class that do not
conform requirements on such a generalization. This is the reason why
some authors prefer the class of languages recognizable by 2OTA.
Grammars with productions in context-free form are the natural
generalization of the one-dimensional context-free grammars.

Many of the results presented in the thesis are related to CFPG
(closure properties of L(CFPG), undecidability of the emptiness
problem, non-existence of the analogy of the Chomsky normal form of
productions, uncomparability of L(CFPG) to L(2OTA) and L(2FSA)). The
next results cover the properties of the remaining models and they
include several results related to time complexity (time effective
simulation of 2FSA by deterministic 2TM, recognition of NP-complete
problems by 2OTA and 2FSA).