Catálogo de publicaciones - libros

It is known that the satisfiability problem () can be solved with a semi-uniform family of deterministic polarizationless P systems with active membranes with non–elementary membrane division. We present a double improvement of this result by showing that the satisfiability of a Boolean formula () can be solved by a family of P systems of the same kind.

Holzer and Holzer [HH04] proved that the Tantrix rotation puzzle problem is NP-complete. They also showed that for infinite rotation puzzles, this problem becomes undecidable. We study the counting version and the unique version of this problem. We prove that the satisfiability problem parsimoniously reduces to the Tantrix rotation puzzle problem. In particular, this reduction preserves the uniqueness of the solution, which implies that the unique Tantrix rotation puzzle problem is as hard as the unique satisfiability problem, and so is DP-complete under polynomial-time randomized reductions, where DP is the second level of the boolean hierarchy over NP.

Confluent rewrite systems for giant trivalent networks have been investigated by S. Wolfram as possible models of space and spacetime, in the ambitious search for the most fundamental, computational laws of physics. We restrict here to planar trivalent nets, which are shown to support Turing-complete computations, and take an even more radical, approach: while operating on network duals, we use just elementary rewrite rule and drive its application by a simple, fully deterministic algorithm, rather than by pattern-matching. We devise effective visual indicators for exploring the complexity of computations with elementary initial conditions, consisting of thousands of graphs, and expose a rich variety of behaviors, from regular to random-like. Among their features we study, in particular, the dimensionality of the emergent space.

We discuss the power of networks of evolutionary processors where only two types of nodes are allowed. We prove that (up to an intersection with a monoid) every recursively enumerable language can be generated by a network with one deletion and two insertion nodes. Networks with an arbitrary number of deletion and substitution nodes only produce finite languages, and for each finite language one deletion node or one substitution node is sufficient. Networks with an arbitrary number of insertion and substitution nodes only generate context-sensitive languages, and (up to an intersection with a monoid) every context-sensitive language can be generated by a network with one substitution node and one insertion node.

In this paper we will give an outline of the proof of the solvability of the and for 2-symbolic tag systems with a deletion number  = 2. This result will be situated in a more general context of research on limits of solvability in tag systems.

The Skolem machine is a Turing-complete machine model where the instructions are first-order formulas of a specific form. We introduce Skolem machines and prove their logical completeness. Skolem machines compute queries for the Geolog language, a rich fragment of first-order logic. The concept of complete Geolog trees is defined, and this tree concept is used to show logical completeness for Skolem machines: If the query for a Geolog theory is a logical consequence of the axioms then the corresponding Skolem machine halts succesfully in a configuration that supports the query.

A not well-known result [9, Theorem 4.4] in formal language theory is that the Higman-Haines sets for language are regular, but it is easily seen that these sets be effectively computed in general. Here the Higman-Haines sets are the languages of all scattered subwords of a given language and the sets of all words that contain some word of a given language as a scattered subword. Recently, the exact level of unsolvability of Higman-Haines sets was studied in [10]. We focus on language families whose Higman-Haines sets are effectively constructible. In particular, we study the size of Higman-Haines sets for the lower classes of the Chomsky hierarchy, namely for the families of regular, linear context-free, and context-free languages, and prove upper and lower bounds on the size of these sets.

It was shown in (Verlan, 2005) that complexity measures for insertion-deletion systems need a revision and new complexity measures taking into account the sizes of both left and right context were proposed. In this article we investigate insertion-deletion systems having a context only on one side of insertion or deletion rules. We show that a minimal deletion (of one symbol) in one-symbol one-sided context is sufficient for the computational completeness if a cooperation of 4 symbols is used for insertion rules and not sufficient if an insertion of one symbol in one-symbol left and right context is used. We also prove the computational completeness for the case of the minimal context-free deletion (of two symbols) and insertion of two symbols in one-symbol one-sided context.

In this paper we simplify accepting networks of splicing processors considered in [8] by moving the filters from the nodes to the edges. Each edge is viewed as a two-way channel such that input and output filters coincide. Thus, the possibility of controlling the computation in such networks seems to be diminished. In spite of this and of the fact that splicing alone is not a very powerful operation these networks are still computationally complete. As a consequence, we propose characterizations of two complexity classes, namely and , in terms of accepting networks of splicing processors with filtered connections.

A nondeterministic restarting automaton is said to be , if, for each cycle , the word belongs to the complete language () accepted by , if the word  does. Here, in order to differentiate between nondeterministic restarting automata that are correctness preserving and nondeterministic restarting automata in general we introduce two gradual relaxations of the correctness preserving property. These relaxations lead to an infinite two-dimensional hierarchy of classes of languages with membership problems that are decidable in polynomial time.