Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Picture Languages Generated by Assembling Tiles

Bonizzoni P., Ferretti C., Mary A. R. S., Mauri G.

Fundamenta Informaticae

2011

Vol. 110, nr 1-4

77-93

We propose a new formalism for generating picture languages based on an assembly mechanism of tiles that uses rules having a context and a replacement site. More precisely, a picture language will be generated from a finite set of initial pictures by iteratively applying rewriting rules from a given finite set of rules, called a tiling rule system (TRuS system). We prove that the TRuS systems have a greater generative capacity than the tiling systems of Giammarresi and Restivo. This is due mainly to the use of the notion of replacement site, but we further characterize the difference between these systems by comparing them to Wang systems.

On the Computational Efficiency of Polarizationless Recognizer P Systems with Strong Division and Dissolution

Zandron C., Leporati A., Ferretti C., Mauri G., Pérez-Jiménez M.J.

Fundamenta Informaticae

2008

Vol. 87, nr 1

79-91

Recognizer P systems with active membranes have proven to be very efficient computing devices, being able to solve NP-complete decision problems in a polynomial time. However such solutions usually exploit many powerful features, such as electrical charges (polarizations) associated to membranes, evolution rules, communication rules, and strong or weak forms of division rules. In this paper we contribute to the study of the computational power of polarizationless recognizer P systems with active membranes. Precisely, we show that such systems are able to solve in polynomial time the NP-complete decision problem 3-SAT by using only dissolution rules and a form of strong division for non–elementary membranes, working in the maximallly parallel way.