Catálogo de publicaciones - libros

This paper proposes a new model of P systems where the rules are activated by the presence/absence of certain objects in the neighboring regions. We obtain the computational completeness considering only two membranes, external inhibitors, and carriers. Leaving the carriers apart we obtain equivalence with ET0L systems in terms of number sets.

We show that it is undecidable whether two finite substitutions agree on the binary language . This in particular means that equivalence of nondeterministic finite transducers is undecidable even for two-state transducers with unary input alphabet and whose all transitions start from the initial state.

Iterative arrays are one-dimensional arrays of interconnected interacting finite automata. The cell at the origin is equipped with a one-way read-only input tape. We investigate iterative arrays as acceptors for formal languages. In particular, we consider real-time devices which are reversible on the core of computation, i.e., from initial configuration to the configuration given by the time complexity. This property is called real-time reversibility. It is shown that real-time reversible iterative arrays can simulate restricted variants of stacks and queues. It turns out that real-time reversible iterative arrays are strictly weaker than real-time reversible cellular automata. On the other hand, a non-semilinear language is accepted. We show that real-time reversibility itself is not even semidecidable, which extends the undecidability for cellular automata and contrasts the general case, where reversibility is decidable for one-dimensional devices. Moreover, we prove the non-semidecidability of several other properties. The closure under Boolean operations is also derived.

Many computational problems related to probabilistic networks are complete for complexity classes that have few ‘real world’ complete problems. For example, the decision variant of the inference problem () is PP-complete, the -problem is -complete and deciding whether a network is monotone in mode or distribution is co--complete. We take a closer look at monotonicity; more specific, the computational complexity of determining whether the values of the variables in a probabilistic network can be ordered, such that the network is monotone. We prove that this problem – which is trivially co--hard – is complete for the class co- in networks which allow implicit representation.

We study the task of hardness amplification which transforms a hard function into a harder one. It is known that in a high complexity class such as exponential time, one can convert worst-case hardness into average-case hardness. However, in a lower complexity class such as NP or sub-exponential time, the existence of such an amplification procedure remains unclear.

We consider a class of hardness amplifications called weakly black-box hardness amplification, in which the initial hard function is only used as a black box to construct the harder function. We show that if an amplification procedure in TIME() can amplify hardness beyond an () factor, then it must basically embed in itself a hard function computable in TIME(). As a result, it is impossible to have such a hardness amplification with hardness measured against TIME(). Furthermore, we show that, for any  ∈ ℕ, if an amplification procedure in ΣP can amplify hardness beyond a polynomial factor, then it must basically embed a hard function in ΣP. This in turn implies the impossibility of having such hardness amplification with hardness measured against ΣP/poly.

As their name suggest, during a , a scattered context grammar rewrites the maximal number of nonterminals while during a , rewrites the minimal number of nonterminals. This paper demonstrates that if the propagating scattered context grammars derive their sentences by making either of these two derivation steps, then they characterize the family of context sensitive languages.

A CD-system of restarting automata is called if all its component systems are deterministic, and if there is a unique successor system for each component. Here we show that the strictly deterministic CD-systems of restarting automata are strictly more powerful than the corresponding deterministic types of restarting automata, but that they are strictly less powerful than the corresponding deterministic types of nonforgetting restarting automata. In fact, we present an infinite hierarchy of language classes based on the number of components of strictly deterministic CD-systems of restarting automata.

In recent years we witness the proliferation of semidefinite programming bounds in combinatorial optimization [1,5,8], quantum computing [9,2,3,6,4] and even in complexity theory [7]. Examples to such bounds include the semidefinite relaxation for the maximal cut problem [5], and the quantum value of multi-prover interactive games [3,4]. The first semidefinite programming bound, which gained fame, arose in the late seventies and was due to László Lovász [11], who used his theta number to compute the Shannon capacity of the five cycle graph. As in Lovász’s upper bound proof for the Shannon capacity and in other situations the key observation is often the fact that the new parameter in question is multiplicative with respect to the product of the problem instances. In a recent result R. Cleve, W. Slofstra, F. Unger and S. Upadhyay show that the quantum value of XOR games multiply under parallel composition [4]. This result together with [3] strengthens the parallel repetition theorem of Ran Raz [12] for XOR games. Our goal is to classify those semidefinite programming instances for which the optimum is multiplicative under a naturally defined product operation. The product operation we define generalizes the ones used in [11] and [4]. We find conditions under which the product rule always holds and give examples for cases when the product rule does not hold.

The family of languages generated by Boolean grammars and usable with recursive descent parsing is studied. It is demonstrated that Boolean LL languages over a unary alphabet are regular, while Boolean LL subsets of obey a certain periodicity property, which, in particular, makes the language nonrepresentable. It is also shown that ,  ∈ {, }} is not generated by any linear conjunctive LL grammar, while linear Boolean LL grammars cannot generate .

We consider tree-walking automata using pebbles. The pebbles are either (can be lifted from anywhere) or (can be lifted only when the automaton is on it). For each , we give the precise complexities of the problems of emptiness and inclusion of tree-walking automata using pebbles.