MFCS 2001 26th International Symposium on Mathematical Foundations of Computer Science August 27 - 31, 2001 Marianske Lazne, Czech Republic

Contributed Talks

(in no particular order)

The problem of scheduling jobs that arrive over time on a single machine is well-studied. We study the preemptive model and the model with restarts. We provide lower bounds for deterministic and randomized algorithms for several optimality criteria: weighted and unweighted total completion time, and weighted and unweighted total flow time. By using new techniques, we provide the first lower bounds for several of these problems, and we significantly improve the bounds that were known.

In this paper we prove that, in the cot of weak machines over $\R$, there are no sparse $\NP$-hard sets.

We consider the multiplicative complexity of the inversion and division of bivariate power series modulo the ``triangular'' ideal generated by all monomials of total degree $n + 1$. For inversion, we obtain a lower bound of $\sfrac 78 n^2 - O(n)$ opposed to an upper bound of $\sfrac 73 n^2 + O(n)$. The former bound holds for all fields with characteristic distinct from two while the latter is valid over fields of characteristic zero that contain all roots of unity (like e.g. $\mathbb C$). Regarding division, we prove a lower bound of $\sfrac 54 n^2 - O(n)$ and an upper bound of $3 \sfrac 56 n^2 + O(n)$. Here, the former bound is proven for arbitrary fields whereas the latter bound holds for fields of characteristic zero that contain all roots of unity. Similar results are obtained for inversion and division modulo the ``rectangular'' ideal~$(X^{n+1},Y^{n+1})$.

Cerny's conjecture and the road coloring problem are two open problems concerning synchronizing finite automata. We prove these conjectures in the special case that the underlying digraph is Eulerian, that is, if the in- and out-degrees of all vertices are equal.

We study the computational complexity of determining whether a systems of equations over a fixed finite monoid has a solution. In \cite{GoldmannR99}, it was shown that in the restricted case of groups the problem is tractable if the group is Abelian and NP-complete otherwise. We prove that in the case of an arbitrary finite monoid, the problem is in P if the monoid divides the direct product of an Abelian group and a commutative idempotent monoid, and is NP-complete otherwise. In the restricted case where only constants appear on the right-hand side, we show that the problem is in P if the monoid is in the class $\rl$, and is NP-complete otherwise. Furthermore interesting connections to the well known {\sc Constraint Satisfiability Problem} are uncovered and exploited.

In [1], partial words were defined to be partial mappings of a set $\{1,...,n\}$ to a finite alphabet. We continue the research of periodic partial words started in that paper. The main goal is to clarify the interaction of different periods of a word. In particular, we exhibit some propeties of periodic partial words, which are quite similar to classical Theorem of Fine and Wilf.

We study the ability of discrete dynamical systems to transform/generate randomness in cellular spaces. Thus, we endow the space of bi-infinite sequences by a metric inspired by information distance (defined in the cot of Kolmogorov complexity or algorithmic information theory). We prove structural properties of this space (non-separability, completeness, perfectness and infinite topological dimension), which turn out to be useful to understand the transformation of information performed by dynamical systems evolving on it. Finally, we focus on cellular automata and prove a dichotomy theorem: continuous cellular automata are either equivalent to the identity or to a constant one. This means that they cannot produce any amount of randomness.

We investigate graph--driven free parity BDDs, which strictly generalize the two well--known models parity OBDDs and graph--driven free BDDs. The first main result of this paper is a polynomial time algorithm that minimizes the number of nodes in a graph--driven free parity BDD. The second main result is an exponential lower bound on the size of graph--driven free parity BDD for linear code functions.

\CASL, a specification formalism developed recently by the \CoFI group, offers architectural specifications as a way to describe how simpler modules can be used to construct more complex ones. The semantics for \CASL architectural specifications formulates static {\em amalgamation conditions} as a prerequisite for such constructions to be well-formed. These are non-trivial in the presence of subsorts due to the failure of the amalgamation property for the \CASL institution. We show that indeed the static amalgamation conditions for \CASL are undecidable in general. However, we identify a number of practically relevant special cases where the problem becomes decidable and analyze its complexity there. In cases where the result turns out to be $\PSPACEb$-hard, we discuss further restrictions under which polynomial algorithms become available. All this underlies the static analysis as implemented in the \CASL tool set. \vspace{1ex} {\em Keywords:} formal specification and program development; \CASL; architectural specifications; amalgamation; algorithms; decidability.

We show that, for an arbitrary function~$h(n)$ and each recursive function~$\ell(n)$, that are separated by a nondeterministically fully space constructible~$g(n)$, such that \mbox{$h(n)\!\in\!\Omega(g(n))$} but \mbox{$\ell(n)\!\not\in\!\Omega(g(n))$}, there exists a unary language~$\cal L$ in ${\rm NSPACE}(h(n))-{\rm NSPACE}(\ell(n))$. The same holds for the deterministic case. The main contribution to the well-known {\em Space Hierarchy Theorem} is that {\em (i)}~the language~$\cal L$ separating the two space classes is unary (tally), {\em (ii)}~the hierarchy is independent of whether $h(n)$ or~$\ell(n)$ are in $\Omega(\log n)$ or in $o(\log n)$, {\em (iii)}~the functions $h(n)$ or~$\ell(n)$ themselves need not be space constructible nor monotone increasing. This allows us, using diagonalization, to present unary languages in such complexity classes as, for example, ${\rm NSPACE}(\log\log n\!\cdot\!\log^{\ast}\!n) - {\rm NSPACE}(\log\log n)$.

A real number $x$ is called {\em $h$-monotonically computable} ($h$-mc), for some function $h$, if there is a computable sequence $(x_s)_{s\in\IN}$ of rational numbers such that $h(n)|x-x_n|\ge|x-x_m|$ for any $m\ge n$. $x$ is called {\em $\omega$-monotonically computable} ($\omega$-mc) if it is $h$-mc for some recursive function $h$ and, for any $c\in\IR$, $x$ is $c$-mc if it is $h$-mc for the constant function $h\equiv c$. In this paper we discuss the properties of $c$-mc and $\omega$-mc real numbers. Among others we will show a hierarchy theorem of $c$-mc real numbers that, for any constants $c_2>c_1\ge 1$, there is a $c_2$-mc real number which is not $c_1$-mc and that there is an $\omega$-mc real number which is not $c$-mc for any $c\in\IR$. Furthermore, the class of all $\omega$-mc real numbers is incomparable with the class of weakly computable real numbers which is the arithmetical closure of semi-computable real numbers.

Space-bounded one-way cellular language acceptors ($\mathrm{OCA}$) are investigated. The only inclusion known to be strict in their time hierarchy from real-time to exponential-time is between real-time and linear-time! We show the surprising result that there exists an infinite hierarchy of properly included $\mathrm{OCA}$-language families in that range. A generalization of a method in \cite{Terrier:1996:LRR} is shown that provides a tool for proving that languages are not acceptable by $\mathrm{OCA}$s with small time bounds. By such a language and a translation result the hierarchies are established.

We define a variant of the $H$-coloring problem by fixing the number of preimages of a subset $C$ of the vertices of $H$, thus allowing parameterization. We provide sufficient conditions to guarantee that the problem can be solved in $O(kn+f(k,H))$ steps where $f$ is a function depending only on the number $k$ of fixed preimages and the graph $H$, and in $O(n^{k+c})$ steps where $c$ is a constant independent of $k$. Finally, we prove that whenever the non parameterized vertices induce in $G$ a graph that is bipartite and loopless the problem is NP-complete.}

In the traveling repairman problem (\trp), a tour must be found through every one of a set of points (cities) in some metric space such that the weighted sum of completion times of the cities is minimized. Given a tour, the completion time of a city is the time traveled on the tour before the city is reached. In the online traveling repairman problem \oltrp\ requests for visits to cities arrive online while the repairman is traveling. We analyze the performance of algorithms for the online problem using competitive analysis, where the cost of an online algorithm is compared to that of an optimal offline algorithm. Feuerstein and Stougie~\cite{Feuerstein+Stougie:dial-a-ride} present a $9$-competitive algorithm for the \oltrp\ on the real line. In this paper we show how to use techniques from online-scheduling to obtain a $6$-competitive deterministic algorithm for the \oltrp\ on any metric space. We also present a randomized algorithm with competitive ratio of $\frac{3}{\ln 2}<4.3281$ against an oblivious adversary. Our results extend to the ``dial-a-ride'' generalization \loldarp\ of the \oltrp, where objects have to be picked up and delivered by a server. We supplement the deterministic lower bounds presented in~\cite{Feuerstein+Stougie:dial-a-ride} with lower bounds on the competitive ratio of any randomized algorithm against an oblivious adversary. Our lower bounds are $\frac{\ln 16 +1}{\ln 16 -1}> 2.1282$ for the \loldarp\ on the line, $\frac{4 e -5}{2 e - 3}>2.41041$ for the \loldarp\ on general metric spaces, $2$~for the \oltrp\ on the line, and $7/3$ for the \oltrp\ on general metric spaces.

We show that, on inputs of length exceeding $5n^2$, any $n$--state unary 2nfa (two--way nondeterministic finite automaton) can be simulated by a $(2n\!+\!2)$--state quasi sweeping 2nfa. Such a result, besides providing a ``normal form'' for 2nfa's, enables us to get a subexponential simulation of unary 2nfa's by 2dfa's (two--way deterministic finite automata). In fact, we prove that any $n$--state unary 2nfa can be simulated by a 2dfa with $O(n^{\log n+4})$ states.

The $k$-median problem is a classical facility location problem. We consider the $k$-median problem for \emph{directed trees}, motivated by the problem of locating proxies on the World Wide Web. The two main results of the paper are an $O(n\log n)$ time algorithm for $k=2$ and an $O(n\log^2 n)$ time algorithm for $k=3$. The previously known upper bounds for these two cases were $O(n^2)$.

We describe an explicit simulation of 2-way nondeterministic automata by 1-way alternating automata with quadratic blow-up. We first describe the construction for automata on finite words, and extend it to automata on infinite words.

In this paper we consider the question of whether ${\bf NC^0}$ circuits can generate pseudorandom distributions. While we leave the general question unanswered, we show \begin{itemize} \item[$\bullet$]{}Generators computed by ${\bf NC^0}$ circuits where each output bit depends on at most~$3$ input bits (i.e, ${\bf NC^0_3}$ circuits) and with stretch factor greater than 4 are not pseudorandom. \item[$\bullet$]{}A large class of ``non-problematic'' ${\bf NC^0}$ generators with superlinear stretch (including all ${\bf NC^0_3}$ generators with superlinear stretch) are broken by a statistical test based on a linear dependency test combined with a pairwise independence test. \item[$\bullet$]{}There is an ${\bf NC^0_4}$ generator with a super-linear stretch that passes the linear dependency test as well as $k$-wise independence tests, for any constant $k$. \end{itemize}

We investigate the computational complexity of the minimal polynomial of an integer matrix. We show that the computation of the minimal polynomial is in $\AC^0(\GapL)$, the $\AC^0$-closure of the logspace counting class $\GapL$, which is contained in $\NC^2$. Our main result is that the problem is hard for $\GapL$ (under $\AC^0$ many-one reductions). The result extends to the verification of all invariant factors of an integer matrix. Furthermore, we consider the complexity to check whether an integer matrix is diagonalizable. We show that this problem lies in $\AC^0(\GapL)$ and is hard for $\AC^0(\CL)$ (under $\AC^0$ many-one reductions).

We consider words indexed by linear orderings. These extend finite, (bi-)infinite words and words on ordinals. We introduce automata and rational expressions for words on linear orderings. We prove that for countable scattered linear orderings they are equivalent. This result extends Kleene's theorem. The proofs are effective.

We show that it is not possible to approximate the minimum Steiner tree problem within $\frac{136}{135}$ unless $co-RP = NP$. This improves the currently best known lower bound by about a factor of $3$. The reduction is from H\aa stad's nonapproximability result for maximum satisfiability of linear equation modulo $2$. The improvement on the nonapproximability ratio is mainly based on the fact that our reduction does not use variable gadgets. This idea was introduced by Papadimitriou and Vempala.

We study different computable versions of Baire's Category Theorem in computable analysis. Similarly, as in constructive analysis, different logical forms of this theorem lead to different computational interpretations. We demonstrate that, analogously to the classical theorem, one of the computable versions of the theorem can be used to construct interesting counterexamples, such as a computable but nowhere differentiable function.

The study of tensor calculus over semirings in terms of complexity theory was initiated by Damm tit{et~al.\/} in~\cite{dahomc00}. Here we first look at tensor circuits, a natural generalization of tensor formulas; we show that the problem of asking whether the output of such circuits is non-zero is complete for the class $\NE = tnormal{NTIME}(2^{O(n)})$ for circuits over the boolean semiring, $\PE$ for the field~$\Fq{2}$, and analogous results for other semirings. Common sense restrictions such as imposing a logarithmic upper bound on circuit depth are also discussed. Second, we analyze other natural problems concerning tensor formulas and circuits over various semirings, such as asking whether the output matrix is diagonal or a null matrix.

The primary structure of a ribonucleic acid (RNA) molecule can be represented as a sequence of nucleotides (bases) over the four-letter alphabet $\{A,C,G,U\}$. The RNA secondary and tertiary structures can be represented as a set of nested base pairs and a set of crossing base pairs, respectively. These base pairs form bonds between $A-U$, $C-G$, and $G-U$. This paper considers alignment with affine gap penalty between two RNA molecule structures. In general this problem is Max SNP-hard for tertiary structures. We present an algorithm for the case where aligned base pairs are non-crossing. Experimental results show that this algorithm can be used for practical application of RNA structure alignment.

We describe a class of simple transitive semiautomata that exhibit full exponential blow-up during deterministic simulation. For arbitrary semiautomata we show that it is \PSPACE-complete to decide whether the size of the accessible part of their power automata exceeds a given bound. We comment on the application of these results to the study of cellular automata.

We consider the movement minimization problem in a conveyor flow shop processing controlled by one worker for all machines. A machine can only execute tasks if the worker is present. Each machine can serve as a buffer for exactly one job. The worker has to cover a certain distance to move from one machine to the next or previous one. The objective is to minimize the total distance the worker has to cover for the processing of all jobs. We introduce the first polynomial time approximation algorithm for this problem with a performance bounded by some fixed factor.

This paper is concerned with the on-line problem of scheduling jobs with tight deadlines in a single-processor system. It has been known for long that in such a setting, no on-line algorithm is optimal (or 1-competitive) in the sense of matching the optimal off-line algorithm on the total value of jobs that meet the deadlines; indeed, no algorithm can be $\Omega(k)$-competitive, where $k$ is the importance ratio of the jobs. Recent work, however, reveals that the competitive ratio can be improved to $O(1)$ if the on-line scheduler is equipped with a processor $O(1)$ times faster \cite{KaP95a}; furthermore, optimality can be achieved when using a processor $O(\log k)$ times faster \cite{LaT01}. This paper presents a new on-line algorithm for scheduling jobs with tight deadlines, which can achieve optimality when using a processor that is only $O(1)$ times faster.

In this paper, we consider the help bit problem in the decision tree model proposed by Nisan, Rudich and Saks (FOCS '94). When computing $k$ instances of a Boolean function $f$, Beigel and Hirst (STOC '98) showed that $\lfloor \log_2 k \rfloor+1$ help bits are necessary to reduce the complexity of $f$, for any function $f$, and exhibit the functions for which $\lfloor \log_2 k \rfloor +1$ help bits reduce the complexity. Their functions must satisfy the condition that their complexity is greater than or equal to $k-1$. In this paper, we show new functions satisfying the above conditions whose complexity are only $2 \sqrt{k}$. We also investigate the help bit problem when we are only allowed to use decision trees of depth 1. Moreover, we exhibit the close relationship between the help bit problem and the complexity for circuits with a majority gate at the top.

We show that the known bounded-depth proofs of the Weak Pigeonhole Principle PHP$^{2n}_n$ in size $n^{O(\log(n))}$ are not optimal in terms of size. More precisely, we give a size-depth trade-off upper bound: there are proofs of size $n^{O(d(\log(n))^{2/d})}$ and depth $O(d)$. This solves an open problem of Maciel, Pitassi and Woods (2000). Our technique requires formalizing the ideas underlying Nepomnja\v{s}\v{c}ij's Theorem which might be of independent interest. Moreover, our result implies a proof of the unboundedness of primes in $I\Delta_0$ with a provably weaker `large number assumption' than previously needed.

We show that for all $n$ and $\alpha$ such that $1\le n \le \alpha \le 2^n$ there is a minimal $n$-state nondeterministic finite automaton whose equivalent minimal deterministic automaton has exactly $\alpha$ states.

This paper shows that the traces of rational graphs coincide with the cot-sensitive languages.

\noindent Cot-free processes (BPA) have been used for dataflow-analysis in recursive procedures with applications in optimizing compilers \cite{EK:BPA-dataflow-analysis}. We introduce a more refined model called BPA($\Z$) that can model not only recursive dependencies, but also the passing of integer parameters to subroutines. Moreover, these parameters can be tested against conditions expressible in Presburger-arithmetic. This new and more expressive model can still be analyzed automatically. We define $\Z$-input 1-CM, a new class of one-counter machines that take integer numbers as input, to describe sets of configurations of BPA($\Z$). We show that the ${\it Post}^*$ (the set of successors) of a set of BPA($\Z$)-configurations described by a $\Z$-input 1-CM can be effectively constructed. The ${\it Pre}^*$ (set of predecessors) of a regular set can be effectively constructed as well. However, the ${\it Pre}^*$ of a set described by a $\Z$-input 1-CM cannot be represented by a $\Z$-input 1-CM in general and has an undecidable membership problem. Then we develop a new temporal logic based on reversal-bounded counter machines that can be used to describe properties of BPA($\Z$) and show that the model-checking problem is decidable.

We are interested in the quantifier rank necessary to express the parity of an embedded set of cardinal smaller than a given bound. We consider several embedding structures like the reals with addition and order, or the field of the complex numbers. We provide both lower and upper bounds. We obtain from these results some bounds on the quantifier rank needed to express the connectivity of an embedded graph, when a bound on its number of vertices is given.

We prove that the word problem for every monoid presented by a fixed 2-homogeneous semi-Thue system can be solved in log-space, which generalizes a result of Lipton and Zalcstein for free groups. The uniform word problem for the class of all 2-homogeneous semi-Thue systems is shown to be complete for symmetric log-space.

This paper contains answers to several problems in the theory of the computational complexity of infinite words. We show that the problem whether all infinite words generated by iterating dgsm's have logarithmic space complexity is equivalent to the open problem asking whether the unary classes of languages in $\P$ and in $\DLOG$ are equivalent. Similarly, the problem to find a concrete infinite word which cannot be generated in logarithmic space is equivalent to the problem to find a concrete language which does not belong to $\DSPACE(n)$. Finally, we separate classes of infinite words generated by double and triple D0L TAG systems.

A mixed hypergraph $H$ is a~triple $(V,\CC,\DD)$ where $V$ is its ve set and $\CC$ and $\DD$ are families of~subsets of~$V$, $\CC$--edges and $\DD$--edges. The~degree of~a~ve is the~number of~edges in~which it is contained. A~ve coloring of~$H$ is proper if each $\CC$--edge contains two vertices with the~same color and each $\DD$--edge contains two vertices with different colors. The~feasible set of~$H$ is the~set of~all $k$'s such that there exists a~proper coloring using exactly $k$ colors. The~lower (upper) chromatic number of~$H$ is the~minimum (maximum) number in~the~feasible set. We prove that it is NP--complete to~decide whether the~upper chromatic number of~mixed hypergraphs with maximum degree two is at least a~given $k$. We present polynomial time algorithms for mixed hypergraphs with maximum degree two to~decide their colorability, to~find a~coloring using the~number of~colors equal to~the~lower chromatic number and we present a~$5/3$--aproximation algorithm for the~upper chromatic number. We further prove that it is coNP-hard to~decide whether the~feasible set of a~given general mixed hypergraph is an interval of~integers.

We consider some problems about pairs of disjoint $NP$ sets. The theory of these sets with a natural concept of reducibility is, on the one hand, closely related to the theory of proof systems for propositional calculus, and, on the other, it resembles the theory of $NP$ completeness. Furthermore, such pairs are important in cryptography. Among others, we prove that the Broken Mosquito Screen pair of disjoint $NP$-sets can be polynomially reduced to Clique-Coloring pair and thus is polynomially separable and we show that the pair of disjoint NP-sets canonically associated with the Resolution proof system is symmetric.

Motivated by formal models recently proposed in the cot of XML, we study automata and logics on strings over infinite alphabets. These are conservative extensions of classical automata and logics defining the regular languages on finite alphabets. Specifically, we consider register and pebble automata, and extensions of first-order logic and monadic second-order logic. For each type of automaton we consider one-way and two-way variants, as well as deterministic, non-deterministic, and alternating control. We investigate the expressiveness and complexity of the automata, their connection to the logics, as well as standard decision problems. \ignore{ Some of our results answer open questions of Kaminski and Francez on register automata. }

We show how to axiomatize by equations the least prefixed point of an order preserving function and discuss the domain of application of the proposed method. Thus, we generalize the well known equational axiomatization of Propositional Dynamic Logic to a complete equational axiomatization of the Boolean Modal $\mu$-Calculus. We show on the other hand that the existence of a term which does not preserve the order is an essential condition for the least prefixed point to be definable by equations.

A classical construction assigns to any language its (ordered) syntactic monoid. Recently the author defined the so-called syntactic semiring of a language. We discuss here the relationships between those two structures. Pin's refinement of Eilenberg theorem gives a one-to-one correspondence between positive varieties of rational languages and pseudovarieties of ordered monoids. The author's modification uses so-called conjunctive varieties of rational languages and pseudovarieties of idempotent semirings. We present here also several examples of our varieties of languages.\\ {\bf Keywords:} syntactic semiring, rational languages

We derive new upper bounds on the bisection width of graphs which have a regular ve degree. We show that the bisection width of large 3-regular graphs with $|V|$ vertices is at most $\frac{1}{6}|V|$. For the bisection width of large 4-regular graphs we show an upper bound of $\frac{2}{5}|V|$. \\[1mm] Keywords: {\em graph partitioning; bisection width; regular graphs; local improvement; }

In 1965, Fine \& Wilf proved the following theorem: if $(f_n)_{n \geq 0}$ and $(g_n)_{n \geq 0}$ are periodic sequences of real numbers, of periods $h$ and $k$ respectively, and $f_n = g_n$ for $0 \leq n < h + k - \gcd(h,k)$, then $f_n = g_n$ for all $n \geq 0$. Furthermore, the constant $h + k - \gcd(h,k)$ is best possible. In this paper we consider some variations on this theorem. In particular, we study the case where $f_n \leq g_n$ instead of $f_n = g_n$. We also obtain a generalization to more than two periods.

A secret sharing scheme is a method for distributing a secret among several parties in such a way that only qualified subsets of the parties can reconstruct it and unqualified subsets receive no information about the secret. A multi secret sharing scheme is the natural extension of a secret sharing scheme to the case in which many secrets need to be shared, each with respect to possibly different subsets of qualified parties. A multi secret sharing scheme can be trivially realized by realizing a secret sharing scheme for each of the secrets. A natural question in the area is whether this simple construction is the most efficient as well, and, if not, how much improvement is possible over it. In this paper we address and answer this question, with respect to the most widely used efficiency measure, that is, the {\em maximum} piece of information distributed among all the parties. Although no improvement is possible for several instances of multi secret sharing, we present the first instance for which some improvement is possible, and, in fact, we show that for this instance an improvement factor equal to the number of secrets over the above simple construction is possible. The given improvement is also proved to be the best possible, thus showing that the achieved bound is tight.

We establish refined search tree techniques for the parameterized {\sc dominating set} problem on planar graphs. We derive a fixed parameter algorithm with running time $O(8^k n)$, where $k$ is the size of the dominating set and $n$ is the number of vertices in the graph. For our search tree, we firstly provide a set of reduction rules. Secondly, we prove an intricate branching theorem based on the Euler formula. In addition, we give an example graph showing that the bound of the branching theorem is optimal with respect to our reduction rules. Our final algorithm is very easy (to implement); its analysis, however, is involved.

A tree of rings is a network that is obtained by interconnecting rings in a tree structure such that any two rings share at most one node. A connection request (call) in a tree of rings is given by its two endpoints and, in the case of prespecified paths, a path connecting these two endpoints. We study undirected trees of rings as well as bidirected trees of rings. In both cases, we show that the path packing problem (assigning paths to calls so as to minimize the maximum load) can be solved in polynomial time, that the path coloring problem with prespecified paths can be approximated within a constant factor, and that the maximum (weight) edge-disjoint paths problem is $\mathcal{NP}$-hard and can be approximated within a constant factor (no matter whether the paths are prespecified or can be determined by the algorithm). We also consider fault-tolerance in trees of rings: If a set of calls has been established along edge-disjoint paths and if an arbitrary link fails in every ring of the tree of rings, we show that at least one third of the calls can be recovered if rerouting is allowed. Furthermore, computing the optimal number of calls that can be recovered is shown to be polynomial in undirected trees of rings and $\mathcal{NP}$-hard in bidirected trees of rings.

The connection is investigated between two well known notions which deal with languages that show polynomial time behaviour weaker than membership decidability. One notion is polynomial time bi-immunity (p-bi-immunity). The other one is polynomial time $\D$-verbose\-ness which captures p-selectivity, p-cheatability, p-verboseness and similar notions, where partial information about the characteristic function is computed. The type of partial information is determined by a family of sets of bitstrings $\D$. A full characterization of those $\D$ for which there are p-bi-immune polynomially $\D$-verbose languages is given. Results of the same type for special cases of polynomial $\D$-verboseness were already given by Goldsmith, Joseph, Young \cite{GJY93}, Beigel \cite{Bei90}, and Amir, Gasarch \cite{AG88}.

Informally, a sequential dynamical system (SDS) consists of an undirected graph where each node $v$ is associated with a state $s_v$ and a transition function $f_v$. Given the state value $s_v$ and those of the neighbors of $v$, the function $f_v$ computes the next value of $s_v$. The node transition functions are evaluated according to a specified total order. Such a computing device is a mathematical abstraction of a simulation system. We address the complexity of some state reachability problems for SDSs. Our main result is a dichotomy between classes of SDSs for which the state reachability problems are computationally intractable and those for which the problems are efficiently solvable. These results also allow us to obtain stronger lower bounds on the complexity of reachability problems for cellular automata and communicating state machines.

\thispagestyle{empty} We prove that the class of cot-free languages with polynomially bounded ambiguity ({\it PCFL}) is the closure of the class of unambiguous languages ({\it UCFL}) under projections which deletes Parikh bounded symbols only. A symbol $a$ is Parikh bounded in a language $L$ if there is a constant $c$ such that no word of $L$ contains more than $c$ occurrences of $a$. Furthermore {\it PCFL} is closed under the formally stronger operation of Parikh bounded substitution, i.e., a substitution which is the identity for non Parikh bounded symbols. Finally we prove that the closure of {\it UCFL} under union and concatenation is a proper subset of {\it PCFL}.

Valiant ({\it SIAM Journal on Computing\/} 8, pages 410--421) showed that the problem of counting the number of $s$-$t$ paths in graphs (both in the case of directed graphs and in the case of undirected graphs) is complete for $\sharpp$ under polynomial-time one-Turing reductions (namely, some post-computation is needed to recover the value of a $\sharpp$-function). Valiant then asked whether the problem of counting the number of self-avoiding walks of length $n$ in the two-dimensional grid is complete for $\sharpp_1$, i.e., the tally-version of $\sharpp$. This paper offers a partial answer to the question. It is shown that a number of versions of the problem of computing the number of self-avoiding walks in two-dimensional grid graphs (graphs embedded in the two-dimensional grid) is polynomial-time one-Turing complete for $\sharpp$. This paper also studies the problem of counting the number of self-avoiding walks in graphs embedded in a hypercube. It is shown that a number of versions of the problem is polynomial-time one-Turing complete for $\sharpp$, where a hypercube graph is specified by its dimension, a list of its nodes, and a list of its edges. By scaling up the completeness result for $\sharpp$, it is shown that the same variety of problems is polynomial-time one-Turing complete for $\sharpexp$, where the post-computation required is right bit-shift by exponentially many bits and a hypercube graph is specified by: its dimension, a boolean circuit that accept its nodes, and one that accepts its edges.

One of the properties of Kondacs-Watrous model of quantum finite automata (QFA) is that the probability of the correct answer for a QFA cannot be amplified arbitrarily. In this paper, we determine the maximum probabilities achieved by QFAs for several languages. In particular, we show that any language that is not recognized by an RFA (reversible finite automaton) can be recognized by a QFA with probability at most $0.7726...$.