Wyniki wyszukiwania - BazTech

Ograniczanie wyników

3 Fundamenta Informaticae

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: semilinear set

Sortuj według:

Ogranicz wyniki do:

Semilinear Sets and Counter Machines : a Brief Survey

Ibarra O. H., Seki S.

Fundamenta Informaticae

2015

Vol. 138, nr 1/2

61--76

Semilinear sets are one of the most important concepts in theoretical computer science, as illustrated by the fact that the set of nonnegative integer solutions to any system of Diophantine equations is semilinear. Parikh’s theorem enables us to represent any semilinear set as a pushdown automaton (PDA).We summarize recent results on the descriptional complexity of conversions among different representations of a semilinear set: as a vector set (conventional), a finite automaton (FA), a PDA, etc.. We also discuss semilinearity-preserving operations like union, intersection, and complement. We use Parikh’s theorem to enlarge the class of finite-state machines that can represent semilinear sets. In particular, we give a simpler proof of a known result that characterizes semilinear sets in terms of machines with reversal-bounded counters. We then investigate the power of such a machine with only one counter in the context of a long-standing conjecture about repetition on words.

Bridging Membrane and Reaction Systems : Further Results and Research Topics

Păun G., Pérez-Jiménez M.J., Rozenberg G.

Fundamenta Informaticae

2013

Vol. 127, nr 1-4

99--114

This paper continues an investigation into bridging two research areas concerned with natural computing: membrane computing and reaction systems. More specifically, the paper considers a transfer of two assumptions/axioms of reaction systems, non-permanency and the threshold assumption, into the framework of membrane computing. It is proved that: (1) spiking neural P systems with non-permanency of spikes assumption characterize the semilinear sets of numbers, and (2) symport/antiport P systems with threshold assumption (translated as ω multiplicity of objects) can solve SAT in polynomial time. Also, several open research problems are stated.

Spiking Neural P Systems

Ionescu M., Paun G., Yokomori T.

Fundamenta Informaticae

2006

Vol. 71, nr 2,3

279-308

This paper proposes a way to incorporate the idea of spiking neurons into the area of membrane computing, and to this aim we introduce a class of neural-like P systems which we call spiking neural P systems (in short, SN P systems). In these devices, the time (when the neurons fire and/or spike) plays an essential role. For instance, the result of a computation is the time between the moments when a specified neuron spikes. Seen as number computing devices, SN P systems are shown to be computationally complete (both in the generating and accepting modes, in the latter case also when restricting to deterministic systems). If the number of spikes present in the system is bounded, then the power of SN P systems falls drastically, and we get a characterization of semilinear sets. A series of research topics and open problems are formulated.