Wyniki wyszukiwania - BazTech

Ograniczanie wyników

3 Fundamenta Informaticae

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: tiling systems

Sortuj według:

Ogranicz wyniki do:

Deterministic and Unambiguous Families within Recognizable Two-dimensional Languages

Anselmo M., Giammarresi D., Madonia M.

Fundamenta Informaticae

2010

Vol. 98, nr 2/3

143-166

Recognizable two-dimensional languages (REC) are defined by tiling systems that generalize to two dimensions non-deterministic finite automata for strings. We introduce the notion of deterministic tiling system and the corresponding family of languages (DREC) and study its structural and closure properties. Furthermore we show that, in contrast with the one-dimensional case, there exist other classes between deterministic and non-deterministic families that we separate by means of examples and decidability properties.

The Complexity of Unary Tiling Recognizable Picture Languages: Nondeterministic and Unambiguous Cases

Bertoni A., Goldwurm M., Lonati V.

Fundamenta Informaticae

2009

Vol. 91, nr 2

231-249

In this paper we consider the classes REC1 and UREC1 of unary picture languages that are tiling recognizable and unambiguously tiling recognizable, respectively. By representing unary pictures by quasi-unary strings we characterize REC1 (resp. UREC1) as the class of quasi-unary languages recognized by nondeterministic (resp. unambiguous) linearly space-bounded one-tape Turing machines with constraint on the number of head reversals. We apply such a characterization in two directions. First we prove that the binary string languages encoding tiling recognizable unary square languages lies between NTIME(2^n) and NTIME(4^n); by separation results, this implies there exists a non-tiling recognizable unary square language whose binary representation is a language in NTIME(4^n log n). In the other direction, by means of results on picture languages, we are able to compare the power of deterministic, unambiguous and nondeterministic one-tape Turing machines that are linearly space-bounded and have constraint on the number of head reversals.

Tissue-like P Systems with Active Membranes for Picture Generation

Ceterchi R., Gramatovici R., Jonoska N., Subramanian K.G.

Fundamenta Informaticae

2003

Vol. 56, nr 4

311-328

We propose a variant of tissue-like P systems with symport rules and active membranes that generates two-dimensional picture languages. The method is unconventional in that, instead of using the membranes as regions for computation/writing, it uses them to hold elements of pictures. Thus, the picture itself, and actually the whole supporting rectangular grid, is composed of membranes, each one containing (among other symbols) a letter of the picture's alphabet. The method is illustrated by its application to the generation of local and recognizable picture languages.