Now showing items 21-40 of 158

    • Icon

      On the quantifier complexity of Δ n+1 (T)– induction  [Article]

      Cordón Franco, Andrés; Fernández Margarit, Alejandro; Lara Martín, Francisco Félix (Springer, 2004)
      In this paper we continue the study of the theories IΔ n+1 (T), initiated in [7]. We focus on the quantifier complexity of these fragments and theirs (non)finite axiomatization. A characterization is obtained for the class ...
    • Icon

      Induction, minimization and collection for Δ n+1 (T)–formulas  [Article]

      Fernández Margarit, Alejandro; Lara Martín, Francisco Félix (Springer, 2004)
      For a theory T, we study relationships among IΔ n +1 (T), LΔ n+1 (T) and B * Δ n+1 (T). These theories are obtained restricting the schemes of induction, minimization and (a version of) collection to Δ n+1 (T) formulas. ...
    • Icon

      A Note on Complexity Measures for Probabilistic P Systems  [Article]

      Cordón Franco, Andrés; Sancho Caparrini, Fernando (J.UCS.org, 2004)
      In this paper we present a first approach to the definition of different entropy measures for probabilistic P systems in order to obtain some quantitative parameters showing how complex the evolution of a P system is. ...
    • Icon

      Modelos de computación celular con membranas  [Article]

      Pérez Jiménez, Mario de Jesús; Romero Jiménez, Álvaro; Sancho Caparrini, Fernando (SEMA, 2004)
    • Icon

      An Efficient Family of P Systems for Packing Items into Bins  [Article]

      Pérez Jiménez, Mario de Jesús; Romero Campero, Francisco José (Graz University of Technology, Institut für Informationssysteme und Computer Medie, 2004)
    • Icon

      A Prolog Simulator for Deterministic P Systems with Active Membranes  [Article]

      Cordón Franco, Andrés; Gutiérrez Naranjo, Miguel Ángel; Pérez Jiménez, Mario de Jesús; Sancho Caparrini, Fernando (Springer, 2004)
      In this paper we propose a new way to represent P systems with active membranes based on Logic Programming techniques. This representation allows us to express the set of rules and the configuration of the P system in ...
    • Icon

      Deductive databases and P systems  [Article]

      Rogozhin, Vladimir; Gutiérrez Naranjo, Miguel Ángel (2004)
    • Icon

      Formal verification of a generic framework to synthesize SAT-provers  [Article]

      Martín Mateos, Francisco Jesús; Alonso Jiménez, José Antonio; Hidalgo Doblado, María José; Ruiz Reina, José Luis (Springer, 2004)
      We present in this paper an application of the ACL2 system to generate and reason about propositional satis ability provers. For that purpose, we develop a framework where we de ne a generic SAT-prover based on transformation ...
    • Icon

      A fast P system for finding a balanced 2-partition  [Article]

      Gutiérrez Naranjo, Miguel Ángel; Pérez Jiménez, Mario de Jesús; Riscos Núñez, Agustín (Springer, 2005)
      Numerical problems are not very frequently addressed in the P systems literature. In this paper we present an effective solution to the 2-Partition problem via a family of deterministic P systems with active membranes ...
    • Icon

      Fragments of Arithmetic and true sentences  [Article]

      Cordón Franco, Andrés; Fernández Margarit, Alejandro; Lara Martín, Francisco Félix (Wiley, 2005)
      By a theorem of R. Kaye, J. Paris and C. Dimitracopoulos, the class of the ¦n+1–sentences true in the standard model is the only (up to deductive equivalence) consistent ¦n+1–theory which extends the scheme of induction ...
    • Icon

      Membrane computing: Brief introduction, recent results and applications  [Article]

      Paun, Gheorghe; Pérez Jiménez, Mario de Jesús (Elsevier, 2006)
      The internal organization and functioning of living cells, as well as their cooperation in tissues and higher order structures, can be a rich source of inspiration for computer science, not fully exploited at the present ...
    • Icon

      Available Membrane Computing Software  [Chapter of Book]

      Gutiérrez Naranjo, Miguel Ángel; Pérez Jiménez, Mario de Jesús; Riscos Núñez, Agustín (Springer, 2006)
      The simulation of a P system with current computers is a quite com-plex task. P systems are intrinsically nondeterministic computational devices and therefore their computation trees are di±cult to store and handle with ...
    • Icon

      Membrane division, restricted membrane creation and object complexity in P systems  [Article]

      Alhazov, Artiom; Freund, Rudolf; Riscos Núñez, Agustín (Taylor and Francis, 2006)
      We improve, by using register machines, some existing universality results for specific models of P systems. P systems with membrane creation are known to generate all recursively enumerable sets of vectors of non-negative ...
    • Icon

      Formal Correctness of a Quadratic Unification Algorithm  [Article]

      Ruiz Reina, José Luis; Martín Mateos, Francisco Jesús; Alonso Jiménez, José Antonio; Hidalgo Doblado, María José (Springer, 2006)
      We present a case study using ACL2 [5] to verify a non-trivial algorithm that uses efficient data structures. The algorithm receives as input two first-order terms and it returns a most general unifier of these terms if ...
    • Icon

      Envelopes, indicators and conservativeness  [Article]

      Cordón Franco, Andrés; Fernández Margarit, Alejandro; Lara Martín, Francisco Félix (Wiley, 2006)
      A well known theorem proved (independently) by J. Paris and H. Friedman states that BΣn +1 (the fragment of Arithmetic given by the collection scheme restricted to Σn +1‐formulas) is a Πn +2‐conservative extension of IΣn ...
    • Icon

      Bounding the Indegree of Spiking Neural P Systems  [Article]

      Paun, Gheorghe; Pérez Jiménez, Mario de Jesús; Salomaa, Arto (Turku Center for Computer Science, 2006)
      We continue the search of normal forms for spiking neural P systems, and we prove that the indegree of such systems (the maximal number of incoming synapses of neurons) can be bounded by 2 without losing the computatio ...
    • Icon

      Spike Trains in Spiking Neural P Systems  [Article]

      Paun, Gheorghe; Pérez Jiménez, Mario de Jesús; Rozenberg, Grzegorz (World Scientific, 2006)
      We continue here the study of the recently introduced spiking neural P systems, which mimic the way that neurons communicate with each other by means of short electrical impulses, identical in shape (volt- age), but ...
    • Icon

      Computational efficiency of dissolution rules in membrane systems  [Article]

      Gutiérrez Naranjo, Miguel Ángel; Pérez Jiménez, Mario de Jesús; Riscos Núñez, Agustín; Romero Campero, Francisco José (Taylor and Francis, 2006)
      Trading (in polynomial time) space for time in the framework of membrane systems is not sufficient to efficiently solve computationally hard problems. On the one hand, an exponential number of objects generated in ...
    • Icon

      Foundational Challenges in Automated Data and Ontology Cleaning in the Semantic Web  [Article]

      Alonso Jiménez, José Antonio; Borrego Díaz, Joaquín; Chávez González, Antonia María; Martín Mateos, Francisco Jesús (IEEE Computer Society, 2006)
      The application of automated reasoning systems to data cleaning in the Semantic Web raises many challenges on the foundational basis of cleaning agent design. The authors discuss some of them. They finally argue that ...
    • Icon

      Computationally Hard Problems Addressed Through P Systems  [Chapter of Book]

      Pérez Jiménez, Mario de Jesús; Romero Jiménez, Álvaro; Sancho Caparrini, Fernando (Springer, 2006)
      In this chapter we present a general framework to provide efficient solutions to decision problems through families of cell-like membrane systems constructed in a semi-uniform way (associating with each instance of the ...