PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 7

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote Enforcing Regular Languages
Genova D., Hoogeboom H. J.
Fundamenta Informaticae
|
2017
|
Vol. 154, nr 1/4
131--144
EN
We investigate regular languages in the context of the forbidding-enforcing systems introduced by Ehrenfeucht and Rozenberg in the variant where one fe-system defines a single language. In general, these systems may have infinite sets of rules, allowing one to define arbitrary languages. On the other hand when restricted to finite sets, one obtains a strict subclass of the regular languages, between the strictly locally testable and locally testable languages. We further investigate classes of enforcing systems that characterize the regular languages. These systems have infinite sets of enforcers, but can be defined using regular languages (finite state automata).
2
Content available remote Making DNA Expressions Minimal
van Vliet R., Hoogeboom H.J.
Fundamenta Informaticae
|
2013
|
Vol. 123, nr 2
199--226
EN
DNA expressions constitute a formal notation for DNA molecules that may contain nicks and gaps. Different DNA expressions may denote the same DNA molecule. We describe an algorithm to rewrite a given DNA expression into a DNA expression of minimal length denoting the same molecule.
3
Content available remote A Minimal Normal Form for DNA Expressions
van Vliet R., Hoogeboom H.J.
Fundamenta Informaticae
|
2013
|
Vol. 123, nr 2
227--243
EN
DNA expressions constitute a formal notation for DNA molecules that may contain nicks and gaps. Different DNA expressions may denote the same DNA molecule. We define a (minimal) normal form for the language of DNA expressions, and describe an algorithm to rewrite a given DNA expression into the normal form.
4
Content available remote Binary Symmetric Matrix Inversion Through Local Complementation
Brijder R., Hoogeboom H.J.
Fundamenta Informaticae
|
2012
|
Vol. 116, nr 1-4
15-23
EN
We consider the Schur complement operation for symmetric matrices over GF(2), which we identify with graphs through the adjacency matrix representation. It is known that Schur complementation for such a matrix (i.e., for a graph) can be decomposed into a sequence of two types of elementary Schur complement operations: (1) local complementation on a looped vertex followed by deletion of that vertex and (2) edge complementation on an edge without looped vertices followed by deletion of that edge. We characterize the symmetricmatrices over GF(2) that can be transformed into the empty matrix using only operations of (1). As a consequence, we find that these matrices can be inverted using local complementation. The result is applied to the theory of gene assembly in ciliates.
5
Content available remote Limited Asynchronous Spiking Neural P Systems
Pan L., Wang J., Hoogeboom H.J.
Fundamenta Informaticae
|
2011
|
Vol. 110, nr 1-4
271-293
EN
In a biological system, if a long enough time interval is given, an enabled chemical reaction will finish its reaction in the given time interval. With this motivation, it is natural to impose a bound on the time intervalwhen an enabled spiking rule in a spiking neural P system (SN P system, for short) remains unused. In this work, a new working mode of SN P systems is defined, which is called limited asynchronous mode. In an SN P system working in limited asynchronous mode, if a rule is enabled at some step, this rule is not obligatorily used. From this step on, if the unused rule may be used later, it should be used in the given time interval. If further spikes make the rule non-applicable, then the computation continues in the new circumstances. The computation result of a computation in an SN P system working in limited asynchronous mode is defined as the total number of spikes sent into the environment by the system. It is proved that limited asynchronous SN P systems with standard spiking rules are universal. If the number of spikes present in each neuron of a limited asynchronous SN P system with standard spiking rules is bounded during a computation, then the power of a limited asynchronous SN P system with standard spiking rules falls drastically, and we get a characterization of semilinear sets of numbers.
6
Content available remote Finitary Compositions of Two-way Finite-State Transductions
Engelfriet J., Hoogeboom H.J.
Fundamenta Informaticae
|
2007
|
Vol. 80, nr 1-3
111-123
EN
The hierarchy of arbitrary compositions of two-way nondeterministic finite-state transductions collapses when restricted to finitary transductions, i.e., transductions that produce a finite set of outputs for each input. The hierarchy collapses to the class of nondeterministic mso definable transductions, which is inside the second level of that hierarchy. It is decidable whether a composition of two-way nondeterministic finite-state transducers realizes a finitary transduction (i.e., is mso definable).
7
Content available remote A Direct Construction of a Universal P System
Frisco P., Hoogeboom H.J., Sant P.
Fundamenta Informaticae
|
2002
|
Vol. 49, nr 1-3
103-122
EN
We present a direct universal P system based on splicing. Our approach differs from those shown in previous papers as the P system we construct takes as input an encoding of another P system. Previous results were based on the simulation of universal type-0 grammars or Turing machines. We think that the approach we use can be applied to other variants of P systems.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.