Theoretical Computer Science

We prove the first lower bounds for restricted read-once parity branching programs with unlimited parity nondeterminism where for each input the variables may be tested according to several orderings. Namely, sums of k graph-driven ⊕ BP1s with ...

The maximal pattern complexity of one-dimensional words has been studied in several papers [T. Kamae, L. Zamboni, Sequence entropy and the maximal pattern complexity of infinite words, Ergodic Theory Dynam. Systems 22(4) (2002) 1191-1199; T. Kamae, L. ...

For every measure µ, the integral I: f ↦ ∫ f dµ is a linear functional on the set of real measurable functions. By the Daniell-Stone theorem, for every abstract integral Λ: F → R on a stone vector lattice F of real functions f: Ω → R there is a measure ...

The edge-bandwidth of a graph G is the bandwidth of the line graph of G. We show asymptotically tight bounds on the edge-bandwidth of two-dimensional grids and tori, the product of two cliques and the n-dimensional hypercube.

We consider the CNN problem in arbitrary dimension, and over any metric space containing the integers. We prove that, in every dimension at least 2, no memoryless online algorithm can achieve a constant competitive ratio, under a weak symmetry ...

Double-loop networks have been widely studied as an architecture for local area networks. It is well known that the minimum distance diagram of a double-loop network yields an L-shape. Given a positive integer N, it is desirable to find a double-loop ...

In this paper we model (discrete) reactive systems that may interact with each other by Petri net reactive modules (modules, for short) which are classical Petri nets together with a distinguished subset of interface places. We consider then an ...

Pin showed that every p-state automaton (p a prime) containing a cyclic permutation and a non-permutation has a synchronizing word of length at most (p - 1)². In this paper, we consider permutation automata with the property that adding any ...

We present a modification of Newton's method to restore quadratic convergence for isolated singular solutions of polynomial systems. Our method is symbolic-numeric: we produce a new polynomial system which has the original multiple solution as a regular ...

The declustering problem is to allocate given data on parallel working storage devices in such a manner that typical requests find their data evenly distributed on the devices. Using deep results from discrepancy theory, we improve previous work of ...

This paper deals with a kind of aperiodic tilings associated with Pisot numeration systems, originally due to W.P. Thurston, in the formulation of S. Akiyama. We treat tilings whose generating Pisot units β are cubic and not totally real. Each such ...

In this paper, we use resource-bounded dimension theory to investigate polynomial size circuits. We show that for every i ≥0, P/poly has ith-order scaled p₃-strong dimension 0. We also show that P/poly^i.o. has p₃-dimension 1/2 and p₃-strong dimension 1. ...

We show that the l vertex disjoint paths problem between l pairs of vertices can be solved in linear time for co-graphs but is NP-complete for graphs of clique-width at most 6 and NLC-width at most 4. The NP-completeness follows from the fact that the ...

A combinatorial problem usually requires enumerating, counting or ascertaining existence of structures that satisfy a given property B in a set of structures L. This paper describes a technique based on a generalization of Birkhoff's theorem of ...

We give a linear-time algorithm to reconstruct a finite word w over a finite alphabet A of constant size starting from a finite set of factors of w verifying a suitable hypothesis. We use combinatorics techniques based on the minimal forbidden words, ...

We obtain new results on minimum lengths of words in an unavoidable set of words of cardinality n before introducing the notion of aperiodic unavoidable sets, a natural extension of unavoidable sets.

Itai and Rodeh showed that, on the average, the communication of a leader election algorithm takes no more than LN bits, where L ≃ 2.441716 and N denotes the size of the ring. We give a precise asymptotic analysis of the average number of rounds M(n) ...

We give some sufficient criteria for the existence of certain averages (mean, correlation functions) of generalized higher-dimensional automatic sequences and show how to calculate these averages. Then follows an exploration of the nature of necessary ...

We consider the zeta and Möbius functions of a partial order on integer compositions first studied by Bergeron, Bousquet-Mélou, and Dulucq. The Möbius function of this poset was determined by Sagan and Vatter. We prove rationality of various formal ...

The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known domination problem in graphs. In 2002, Haynes et al. considered the graph theoretical representation ...

In the computational-mechanics structural analysis of one-dimensional cellular automata the following automata-theoretic analogue of the change-point problem from time series analysis arises: Given a string σ and a collection {D_i} offinite automata, ...

The string matching problem, i.e. the task of finding all occurrences of one string as a substring of another one, is a fundamental problem in computer science. Recently, this problem received a great deal of attention due to numerous applications in ...

ε-Points were introduced by the authors (see [S. Pérez-Díaz, J.R. Sendra, J. Sendra, Parametrization of approximate algebraic curves by lines, Theoret. Comput. Sci. 315(2-3) (2004) 627-650 (Special issue); S. Pérez-Díaz, J.R. Sendra, J. Sendra, ...

We present a reduction that allows us to establish completeness results for several approximation classes mainly beyond APX. Using it, we extend one of the basic results of S. Khanna, R. Motwani, M. Sudan, and U. Vazirani (On syntactic versus ...

We present a model of evolution of gene trees in the context of species evolution. Its concept is similar to reconciliation models. We assume that the gene evolution is modelled by duplications and losses. Evolution of species is modelled by speciation ...

We examine the problem of assigning n independent jobs to m unrelated parallel machines, so that each job is processed without interruption on one of the machines, and at any time, every machine processes at most one job. We focus on the case where m is ...

Cellular telephony systems, where locations of mobile users are unknown at some times, are becoming more common. In such systems, mobile users are roaming in a zone and a user reports its location only if it leaves the zone entirely. The conference call ...

This paper studies online job scheduling on multiprocessors and, in particular, investigates the algorithms Shortest Remaining Processing Time First (SRPT) and Shortest Job First (SJF) for minimizing total stretch, where the stretch of a job is its flow ...

We show that Kolmogorov complexity and such its estimators as universal codes (or data compression methods) can be applied for hypotheses testing in a framework of classical mathematical statistics. The methods for identity testing and nonparametric ...