Fundamenta Informaticae - Volume 110, issue 1-4

Authors: Pan, Linqiang | Wang, Jun | Hoogeboom, Hendrik Jan

Article Type: Research Article

Abstract: 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 interval when 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. Show more

Keywords: Membrane computing, Spiking neural P system, Asynchronous mode, Turing Computability

DOI: 10.3233/FI-2011-543

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 271-293, 2011

Authors: Pérez-Jiménez, Mario J. | Riscos-Núñez, Agustín | Rius-Font, Miquel | Romero-Campero, Francisco J.

Article Type: Research Article

Abstract: In 1936 A. Turing showed the existence of a universal machine able to simulate any Turing machine given its description. In 1956, C. Shannon formulated for the first time the problem of finding the smallest possible universal Turing machine according to some critera to measure its size such as the number of states and symbols. Within the framework of Membrane Computing different studies have addressed this problem: small universal symport/antiport P systems (by considering the number of membranes, the weight of the rules and the number of objects as a measure of the size of the system), small universal splicing …P systems (by considering the number of rules as a measure of the size of the system), and small universal spiking neural P systems (by considering the number of neurons as a measure of the size of the system). In this paper the problem of determining the smallest possible efficient P system is explicitly formulated. Efficiency within the framework of Membrane Computing refers to the capability of solving computationally hard problems (i.e. problems such that classical electronic computer cannot solve instances of medium/large size in any reasonable amount of time) in polynomial time. A descriptive measure to define precisely the notion of small P system is presented in this paper. Show more

Keywords: Membrane Computing, Small universal P Systems, Small effcient P systems, SAT problem

DOI: 10.3233/FI-2011-544

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 295-308, 2011

Authors: Raghavan, Rama | Ramesh, H. | Gheorghe, Marian | Krishna, Shankara Narayanan

Article Type: Research Article

Abstract: Here we continue the study of bio-Turing machines introduced in [2] and further investigated in [17]. We introduce a restricted model of bio-Turing machine and we investigate its computational power, a hierarchy of languages accepted, and deterministic and nondeterministic variants. A comprehensive example illustrating the modelling power of the introduced machine ends the paper.

DOI: 10.3233/FI-2011-545

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 309-320, 2011

Authors: Tran, Nicholas

Article Type: Research Article

Abstract: This paper introduces and studies two notions of easy sets without hard subsets: i) 𝒞-hollow sets are defined to be sets in P that have no 𝒞 – P subsets for (presumably) superclasses 𝒞 of P such as NP, PSPACE, E, NE, RE, etc.; and ii) 𝒞-scant sets are defined to be sets in P that have no many-one 𝒞-complete subsets. These sets complement well-studied objects in complexity such as P-printable sets, immune sets and complexity cores. First, characterizations of 𝒞-hollow sets and 𝒞-scant sets are obtained in terms of universally easy sets, introduced and studied in [7] as an …automatic method for generating easy instances of intractable problems. Second, the following results regarding existence of 𝒞-hollow sets are obtained: infinite NP-hollow tally (equivalently, P-printable) sets exist iff some nondeterministic time complexity class equals its deterministic counterpart; in contrast, infinite E/NE/RE-hollow sets do not exist. Finally, it is shown that P-printable-immune sets in P are 𝒞-scant for E and NE. Show more

DOI: 10.3233/FI-2011-546

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 321-328, 2011

Authors: Verlan, Sergey | Margenstern, Maurice

Article Type: Research Article

Abstract: Splicing test tube systems are one of the first distributed computing models based on splicing. The model introduces (test) tubes where the splicing operation is applied, which are arranged in a communication network with filters that permits to redistribute the words between the tubes at each step. We show that the computational completeness can be achieved with two tubes when the communication graph does not have self-loops. We also construct a universal splicing test tube system with 2 tubes having 23 rules.

Keywords: Splicing, test tube systems, universality

DOI: 10.3233/FI-2011-547

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 329-342, 2011

Authors: Yen, Hsu-Chun

Article Type: Research Article

Abstract: Although randomization often increases the degree of flexibility in system design, analyzing system properties in the probabilistic framework introduces additional difficulties and challenges in comparison with their nonprobabilistic counterparts. In this paper, we focus on probabilistic versions of two problems frequently encountered in discrete event systems, namely, the reachability and forbidden-state problems. Our main concern is to see whether there exists a (or for every) non-blocking or fair control policy under which a given finite- or infinite-state system can be guided to reach (or avoid) a set of goal states with probability one. For finite-state systems, we devise algorithmic approaches …which result in polynomial time solutions to the two problems. For infinite-state systems modelled as Petri nets, the problems are undecidable in general. For the class of persistent Petri nets, we establish a valuation approach through which the convergence behavior of a system is characterized, which in turn yields solutions to the reachability and forbidden-state problems. Show more

Keywords: Forbidden-state avoidance, Petri net, probabilistic controlled transition system, reachability

DOI: 10.3233/FI-2011-548

Citation: Fundamenta Informaticae, vol. 110, no. 1-4, pp. 343-359, 2011