Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 5

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 Morphic Characterizations of Language Families Based on Local and Star Languages
EN
New morphic characterizations in the form of a noted Chomsky-Schützenberger theorem are established for the classes of regular languages, of context-free languages and of languages accepted by chemical reaction automata. Our results include the following: (i) Each λ-free regular language R can be expressed as R = h(Tk ∩ FR) for some 2-star language FR, an extended 2-star language Tk and a weak coding h. (ii) Each λ-free context-free language L can be expressed as L = h(Dn ∩ FL) for some 2-local language FL and a projection h. (iii) A language L is accepted by a chemical reaction automaton iff there exist a 2-local language FL and a weak coding h such that L = h(Bn ∩ FL), where Dn and Bn are a Dyck set and a partially balanced language defined over the n-letter alphabet, respectively. These characterizations improve or shed new light on the previous results.
2
Content available remote Finite Automata with Multiset Memory : A New Characterization of Chomsky Hierarchy
EN
This paper concerns new characterizations of language classes in the Chomsky hierarchy in terms of a new type of computing device called FAMM (Finite Automaton with Multiset Memory) in which a multiset of symbol objects is available for the storage of working space. Unlike the stack or the tape for a storage, the multiset might seem to be less powerful in computing task, due to the lack of positional (structural) information of stored data. We introduce the class of FAMMs of degree d (for non-negative integer d) in general form, and investigate the computing powers of some subclasses of those FAMMs. We show that the classes of languages accepted by FAMMs of degree 0, by FAMMs of degree 1, by exponentially-boundedFAMMs of degree 2, and by FAMMs of degree 2 are exactly the four classes of languages REG, CF, CS and RE in the Chomsky hierarchy, respectively. Thus, this unified view from multiset-based computing provides new insight into the computational aspects of the Chomsky hierarchy.
3
Content available remote Spiking Neural dP Systems
EN
We bring together two topics recently introduced in membrane computing, the much investigated spiking neural P systems (in short, SN P systems), inspired from the way the neurons communicate through spikes, and the dP systems (distributed P systems, with components which “read” strings from the environment and then cooperate in accepting their concatenation). The goal is to introduce SN dP systems, and to this aim we first introduce SN P systems with the possibility to input, at their request, spikes from the environment; this is done by so-called request rules. A preliminary investigation of the obtained SN dP systems (they can also be called automata) is carried out. As expected, request rules are useful, while the distribution in terms of dP systems can handle languages which cannot be generated by usual SN P systems. We always work with extended SN P systems; the non-extended case, as well as several other natural questions remain open.
4
Content available remote On the Hairpin Incompletion
EN
Hairpin completion and its variant called bounded hairpin completion are operations on formal languages, inspired by a hairpin formation in molecular biology. Another variant called hairpin lengthening has been recently introduced, and the related closure properties and algorithmic problems concerning several families of languages have been studied. In this paper, we introduce a new operation of this kind, called hairpin incompletion which is not only an extension of bounded hairpin completion, but also a restricted (bounded) variant of hairpin lengthening. Further, the hairpin incompletion operation provides a formal language theoretic framework that models a bio-molecular technique nowadays known asWhiplash PCR. We study the closure properties of language families under both the operation and its iterated version. We show that a family of languages closed under intersection with regular sets, concatenation with regular sets, and finite union is closed under one-sided iterated hairpin incompletion, and that a family of languages containing all linear languages and closed under circular permutation, left derivative and substitution is also closed under iterated hairpin incompletion.
5
Content available remote Spiking Neural P Systems
EN
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.
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ć.