Automata, Languages and Programming

Over the past fifty years, researchers in Theoretical Computer Science have sought and achieved a productive foundational understanding of the von Neumann computer and its software, employing the mathematical tools of Logic and Combinatorics. The next half century appears now much more confusing (half- centuries tend to look like that in the beginning). What computational artifact will be the object of the next great modeling adventure of our field? And what mathematical tools will be handy in this endeavor?

Classical Automata Theory (AT) is mainly about devices that operate in discrete time. Recent research stimulated the interest to, and the development of, paradigms in which continuous time is involved whether in a pure way or in cooperation with discrete time. This development is in particular evident in the area that covers the following three interrelated trends: automata, logic (arguing about automata) and interaction (composition of automata).

Verification of complex systems cannot be achieved without combining several analysis methods and techniques. A widely adopted approach consists in combining abstraction methods with algorithmic verification techniques. Typically, finite abstractions are built using automatic or semi-automatic methods and model-checking algorithms are applied on these abstractions in order to verify the desired properties. However, finding faithful finite abstractions is often hard since many aspects in the behavior of the system must be hidden or encoded in a nontrivial and ad-hoc manner. This is particularly true for software systems since their behavior depends in a very crucial manner on the manipulation of data structures and variables which are assumed to range over infinite domains (e.g., unbounded stacks, queues, arrays, counters), or over finite domains whose sizes are left as parameters. Moreover, many systems are defined as networks of parametric size, i.e., they are assumed to work for an arbitrary number of processes running in parallel.

According to the viewpoint model of software systems development abstract models of different views of the systems are constructed. This separation of concerns reduces the complexity of the development, but prompts the question for their integration, i.e., the conception of a collection of heterogeneous models as a complete specification of a system. The integration can be achieved by using a common semantic domain for the interpretation of all models, where each viewpoint model, due to its partiality, admits a set of possible interpretations. In this paper such an integrating semantic domain is sketched and an application to structure and behaviour models of the Unified Modeling Language is discussed.

Labelled partial orders in concurrency are a natural and powerful modelling formalism. Recently, there has been a renewed focus on such models arising in various areas of applications. We survey some results on interesting problems for partial order based models, focussing on decidability issues.

Randomized search heuristics like simulated annealing and evolutionary algorithms are applied successfully in many different situations. However, the theory on these algorithms is still in its infancy. Here it is discussed how and why such a theory should be developed. Afterwards, some fundamental results on evolutionary algorithms are presented in order to show how theoretical results on randomized search heuristics can be proved and how they contribute to the understanding of evolutionary algorithms.

Let C(A) denote the multiplicative complexity of a finite dimensional associative k-algebra A.For algebras A with nonzero radical radA, we exhibit several lower bound techniques for C(A) that yield bounds significantly above the Alder- Strassen bound. In particular, we prove that the multiplicative complexity of the multiplication in the algebras k[X₁,..., X_n/Id+1 (X₁,..., X_n) is bounded from below by $$ 3. \left( \begin{gathered} n + d \hfill \\ n \hfill \\ \end{gathered} \right) - \left( \begin{gathered} n + \left[ {d/2} \right] \hfill \\ n \hfill \\ \end{gathered} \right) - \left( \begin{gathered} n + \left[ {d/2} \right] \hfill \\ n \hfill \\ \end{gathered} \right), $$ where I _d (X₁,..., X_n) denotes the ideal generated by all monomials of degree d in X₁,...,X_n. Furthermore, we show the lower bound C(T _n (k) ≥ (2 1/8 - o(1)) dim Tn(k) for the multiplication of upper triangular matrices.

We consider the problem of enumerating all minimal integer solutions of a monotone system of linear inequalities. We first show that for any monotone system of r linear inequalities in n variables, the number of maximal infeasible integer vectors is at most rn times the number of minimal integer solutions to the system. This bound is accurate up to a polylog(r) factor and leads to a polynomial-time reduction of the enumeration problem to a natural generalization of the well-known dualization problem for hypergraphs, in which dual pairs of hypergraphs are replaced by dual collections of integer vectors in a box. We provide a quasi-polynomial algorithm for the latter dualization problem. These results imply, in particular, that the problem of incrementally generating minimal integer solutions of a monotone system of linear inequalities can be done in quasi-polynomial time.

Integer division has been known since 1986 [41312] to be in slightly non-uniform TC0, i.e., computable by polynomial-size, constant depth threshold circuits. This has been perhaps the outstanding natural problem known to be in a standard circuit complexity class, but not known to be in its uniform version. We show that indeed division is in uniform TC0. A key step of our proof is the discovery of a first-order formula expressing exponentiation modulo any number of polynomial size.

In this paper we investigate automated methods for externalizing internal memory data structures.We consider a class of balanced trees that we call weight-balanced partitioning trees (or wp-trees) for indexing a set of points in ℝd.Well-known examples of wp-trees include kd- trees, BBD-trees, pseudo-quad-trees, and BAR-trees. Given an efficient external wp-tree construction algorithm, we present a general framework for automatically obtaining a dynamic external data structure. Using this framework together with a new general construction (bulk loading) technique of independent interest, we obtain data structures with guaranteed good update performance in terms of I/O transfers. Our approach gives considerably improved construction and update I/O bounds for e.g. external kd-trees and BBD-trees.

This paper formulates and investigates the question of whether a given algorithm can be coded in a way efficiently portable across machines with different hierarchical memory systems, modeled as a(x)-HRAMs (Hierarchical RAMs), where the time to access a location x is a(x).The width decomposition framework is proposed to provide a machine- independent characterization of temporal locality of a computation by a suitable set of space reuse parameters. Using this framework, it is shown that, when the schedule, i.e. the order by which operations are executed, is fixed, efficient portability is achievable. We propose (a) the decomposition-tree memory manager, which achieves time within a logarithmic factor of optimal on all HRAMs, and (b) the reoccurrence-width memory manager, which achieves time within a constant factor of optimal for the important class of uniform HRAMs.We also show that, when the schedule is considered as a degree of freedom of the implementation, there are computations whose optimal schedule does vary with the access function. In particular, we exhibit some computations for which any schedule is bound to be a polynomial factor slower than optimal on at least one of two sufficiently different machines. On the positive side, we show that relatively few schedules are sufficient to provide a near optimal solution on a wide class of HRAMs.

We present tight upper and lower bounds for the problem of constructing evolutionary trees in the experiment model. We describe an algorithm which constructs an evolutionary tree of n species in time O(nd log_dn) using at most n⌈d/2⌉(log_2⌈d/2⌉-1n+O(1)) experiments for d > 2, and at most n(log n+O(1)) experiments for d = 2, where d is the degree of the tree. This improves the previous best upper bound by a factor θ(log d). For d = 2 the previously best algorithm with running time O(n log n) had a bound of 4n log n on the number of experiments. By an explicit adversary argument, we show an Ω(nd log_dn) lower bound, matching our upper bounds and improving the previous best lower bound by a factor θ(log_dn). Central to our algorithm is the construction and maintenance of separator trees of small height, which may be of independent interest.

We consider the sequence comparison problem, also known as “hidden pattern” problem, where one searches for a given subsequence in a text (rather than a string understood as a sequence of consecutive symbols). A characteristic parameter is the number of occurrences of a given pattern w of length m as a subsequence in a random text of length n generated by a memoryless source. Spacings between letters of the pattern may either be constrained or not in order to define valid occurrences. We determine the mean and the variance of the number of occurrences, and establish a Gaussian limit law. These results are obtained via combinatorics on words, formal language techniques, and methods of analytic combinatorics based on generating functions and convergence of moments. The motivation to study this problem comes from an attempt at finding a reliable threshold for intrusion detections, from textual data processing applications, and from molecular biology.

In this paper, we discuss the problem of computing all the integral sequences obtained by rounding an input real valued sequence such that the discrepancy between the input sequence and each output integral sequence is less than one. We show that the number of such roundings is n + 1 if we consider the discrepancy with respect to the set of all subintervals, and give an efficient algorithm to report all of them. Then, we give an optimal method to construct a compact graph to represent the set of global roundings satisfying a weaker discrepancy condition.

The model of bulk-synchronous parallel (BSP) computation is an emerging paradigm of general-purpose parallel computing. We propose a new p-processor BSP algorithm for the all-pairs shortest paths problem in a weighted directed dense graph. In contrast with the general algebraic path algorithm, which performs O(p1/2) to O(p2/3) global synchronisation steps, our new algorithm only requires O(log p) synchronisation steps.

We present a probabilistic algorithm that, given a connected graph G (represented by adjacency lists) of maximum degree d, with edge weights in the set 1,..., w, and given a parameter 0 < ε < 1/2, estimates in time O(dw∈-2 log w/∈ ) the weight of the minimum spanning tree of G with a relative error of at most ε. Note that the running time does not depend on the number of vertices in G. We also prove a nearly matching lower bound of Ω(dw∈-2) on the probe and time complexity of any approximation algorithm for MST weight.The essential component of our algorithm is a procedure for estimating in time O(dε-2 log ε-1) the number of connected components of an unweighted graph to within an additive error of εn. The time bound is shown to be tight up to within the log ε-1 factor. Our connected- components algorithm picks O(1/∈2) vertices in the graph and then grows “local spanning trees” whose sizes are specified by a stochastic process. From the local information collected in this way, the algorithm is able to infer, with high confidence, an estimate of the number of connected components. We then show how estimates on the number of components in various subgraphs of G can be used to estimate the weight of its MST.

The general asymmetric (and metric) TSP is known to be approximable only to within an O(log n) factor, and is also known to be approximable within a constant factor as soon as the metric is bounded. In this paper we study the asymmetric and symmetric TSP problems with bounded metrics and prove approximation lower bounds of 101/100 and 203/202, respectively, for these problems. We prove also approximation lower bounds of 321/320 and 743/742 for the asymmetric and symmetric TSP with distances one and two.

Several combinatorial optimization problems can be approximated using algorithms based on semidefinite programming. In many of these algorithms a semidefinite relaxation of the underlying problem is solved yielding an optimal vector configuration v₁...v_n. This vector configuration is then rounded into a 0,1 solution. We present a procedure called RPR2 (Random Projection followed by Randomized Rounding) for rounding the solution of such semidefinite programs. We show that the random hyperplane rounding technique introduced by Goemans and Williamson, and its variant that involves outward rotation are both special cases of RPR2. We illustrate the use of RPR2 by presenting two applications. For Max-Bisection we improve the approximation ratio. For Max-Cut, we improve the tradeoff curve (presented by Zwick) that relates the approximation ratio to the size of the maximum cut in a graph.

We study the generalization of covering problems to partial covering. Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems. For example, in k-set cover, we wish to choose a minimum number of sets to cover at least k elements. For k-set cover, if each element occurs in at most f sets, then we derive a primal-dual f-approximation algorithm (thus implying a 2-approximation for k-vertex cover) in polynomial time. In addition to its simplicity, this algorithm has the advantage of being parallelizable. For instances where each set has cardinality at most three, we obtain an approximation of 4/3. We also present better-than-2-approximation algorithms for k-vertex cover on bounded degree graphs, and for vertex cover on expanders of bounded average degree. We obtain a polynomial-time approximation scheme for k-vertex cover on planar graphs, and for covering points in Rd by disks.

A new framework for analyzing online bin packing algorithms is presented. This framework presents a unified way of explaining the performance of algorithms based on the Harmonic approach [358101112]. Within this framework, it is shown that a new algorithm, Harmonic++, has asymptotic performance ratio at most 1.58889. It is also shown that the analysis of Harmonic+1 presented in [11] is incorrect; this is a fundamental logical flaw, not an error in calculation or an omitted case. The asymptotic performance ratio of Harmonic+1 is at least 1.59217. Thus Harmonic++ provides the best upper bound for the online bin packing problem to date.

Solving an open problem of Jain and Vazirani [FOCS’99], we present Õ(n+m) time constant factor approximation algorithms for the k-median, k-center, and facility location problems with assignment costs being shortest path distances in a weighted undirected graph with n nodes and m edges.For all of these location problems, Õ(n2) algorithms were already known, but here we are addressing large sparse graphs. An application could be placement of content distributing servers on the Internet. The Internet is large and changes so frequently that an Õ(n2) time solution would likely be outdated long before completion.

A parameterized problem is fixed parameter tractable if it admits a solving algorithm whose running time on input instance (I,k) is f(k) · |I|;α, where f is an arbitrary function depending only on k. Typically, f is some exponential function, e.g., f(k) = ck for constant c. We describe general techniques to obtain growth of the form f(k) = c√k for a large variety of planar graph problems. The key to this type of algorithm is what we call the “Layerwise Separation Property” of a planar graph problem. Problems having this property include PLANAR VERTEX COVER, PLANAR INDEPENDENT SET, and PLANAR DOMINATING SET.

It is shown that for essentially all MAX SNP-hard optimization problems finding exact solutions in subexponential time is not possible unless W[1] = FPT. In particular, we show that O(2°(k)p(n)) parameterized algorithms do not exist for VERTEXCOVER, MAXCUT, MAX C-SAT, and a number of problems on bounded degree graphs such as DOMINATINGSET and INDEPENDENTSET, unless W[1] = FPT. Our results are derived via an approach that uses an extended parameterization of optimization problems and associated techniques to relate the parameterized complexity of problems in FPT to the parameterized complexity of extended versions that are W[1]-hard.

We prove a lower bound of Ω(n4/3 log1/3n) on the randomized decision tree complexity of any nontrivial monotone n-vertex bipartite graph property, thereby improving the previous bound of Ω(n4/3) due to Hajnal [H91]. Our proof works by improving a probabilistic argument in that paper, which also improves a graph packing lemma proved there. By a result of Gröger [G92] our complexity lower bound carries over from bipartite to general monotone n-vertex graph properties. Graph packing being a well-studied subject in its own right, our improved packing lemma and the probabilistic technique used to prove it, may be of independent interest.

We introduce a new imperfect random source that realistically generalizes the SV-source of Sántha and Vazirani [SV86] and the bit-fixing source of Lichtenstein, Linial and Saks [LLS89]. Our source is expected to generate a known sequence of (possibly dependent) random variables (for example, a stream of unbiased random bits). However, the realizations/observations of these variables could be imperfect in the following two ways: (1) inevitably, each of the observations could be slightly biased (due to noise, small measurements errors, imperfections of the source, etc.), which is characterized by the “statistical noise” parameter δ ∈ [0, 1/2 ], and (2) few of the observations could be completely incorrect (due to very poor measurement, improper setup, unlikely but certain internal correlations, etc.), which is characterized by the “number of errors” parameter b ≥ 0. While the SV-source considered only scenario (1), and the bit-fixing source — only scenario (2), we believe that our combined source is more realistic in modeling the problem of extracting quasi-random bits from physical sources. Unfortunately, we show that dealing with the combination of scenarios (1) and (2) is dramatically more difficult (at least from the point of randomness extraction) than dealing with each scenario individually. For example, if bδ = ω(1), the adversary controlling our source can force the outcome of any bit extraction procedure to a constant with probability 1-o(1), irrespective of the random variables, their correlation and the number of observations. We also apply our source to the question of producing n-player collective coin-flipping protocols secure against adaptive adversaries. While the optimal non-adaptive adversarial threshold for such protocols is known to be n/2 [BN00], the optimal adaptive threshold is conjectured by Ben-Or and Linial [BL90] to be only $$ o(\sqrt n ) $$ . We give some evidence towards this conjecture by showing that there exists no black-box transformation from a non-adaptively secure coin-flipping protocol (with arbitrary conceivable parameters) resulting in an adaptively secure protocol tolerating $$ \omega (\sqrt n ) $$ faulty players.

It is known that random k-SAT instances with at least dn clauses where d = d _k is a suitable constant are unsatisfiable (with high probability). This paper deals with the question to certify the unsatisfiability of a random 3-SAT instance in polynomial time. A backtracking based algorithm of Beame et al. works for random 3-SAT instances with at least n2/ log n clauses. This is the best result known by now.We improve the n2/ log n bound attained by Beame et al. to n3/2+ε for any ε > 0. Our approach extends the spectral approach introduced to the study of random k-SAT instances for k ≥ 4 in previous work of the second author.

Let L _k , _m be the set of formulas of first order logic containing only variables from x₁, x₂, . . . , x _K and having quantifier depth at most m. Let C_k,_m be the extension of L _k,m obtained by allowing counting quantifiers ∃ix _j , meaning that there are at least i distinct x _j ’s.It is shown that for constants h ≥ 1, there are pairs of graphs such that h-dimensional Weisfeiler-Lehman refinement (h-dim W-L) can distinguish the two graphs, but requires at least a linear number of iterations. Despite of this slow progress, 2h-dim W-L only requires O(√n) iterations, and 3h—1-dim W-L only requires O(log n) iterations. In terms of logic, this means that there is a c > 0 AND A CLASS OF NON-ISOMORPHIC PAIRS $$ (\mathop G\nolimits_{n,}^h \mathop H\nolimits_n^h ) $$ of graphs with $$ \mathop G\nolimits_n^h and \mathop H\nolimits_n^h $$ having O(n) vertices such that the same sentences of L_h+1,cn and C_h+1,cn hold (h + 1 variables, depth cn), even though $$ \mathop G\nolimits_n^h and \mathop H\nolimits_n^h $$ can already be distinguished by a sentence of L _k,m and thus C _k,m for some k > h and m = O(log n).

We continue the investigation of interactive proofs with bounded communication, as initiated by Goldreich and Håstad (IPL 1998). Let L be a language that has an interactive proof in which the prover sends few (say b) bits to the verifier. We prove that the complement L has a constant-round interactive proof of complexity that depends only exponentially on b. This provides the first evidence that for NP- complete languages, we cannot expect interactive provers to be much more “laconic” than the standard NP proof.When the proof system is further restricted (e.g., when b = 1, or when we have perfect completeness), we get significantly better upper bounds on the complexity of L.

We consider the quantum complexities of the following three problems: searching an ordered list, sorting an un-ordered list, and deciding whether the numbers in a list are all distinct. Letting N be the number of elements in the input list, we prove a lower bound of 1/π(ln(N) - 1) accesses to the list elements for ordered searching, a lower bound of Ω(N logN) binary comparisons for sorting, and a lower bound of Ω(√N logN) binary comparisons for element distinctness. The previously best known lower bounds are 1/12 log₂(N) - O(1) due to Ambainis, Ω(N), and Ω(√N), respectively. Our proofs are based on a weighted all-pairs inner product argument.In addition to our lower bound results, we give a quantum algorithm for ordered searching using roughly 0:631 log₂(N) oracle accesses. Our algorithm uses a quantum routine for traversing through a binary search tree faster than classically, and it is of a nature very different from a faster algorithm due to Farhi, Goldstone, Gutmann, and Sipser.

We introduce a new model for studying quantum data structure problems — the quantum cell probe model. We prove a lower bound for the static predecessor problem in the address-only version of this model where, essentially, we allow quantum parallelism only over the ‘address lines’ of the queries. This model subsumes the classical cell probe model, and many quantum query algorithms like Grover’s algorithm fall into this framework. We prove our lower bound by obtaining a round elimination lemma for quantum communication complexity. A similar lemma was proved by Miltersen, Nisan, Safra and Wigderson [9] for classical communication complexity, but their proof does not generalise to the quantum setting.We also study the static membership problem in the quantum cell probe model. Generalising a result of Yao [16], we show that if the storage scheme is implicit, that is it can only store members of the subset and ‘pointers’, then any quantum query scheme must make Ω(log n) probes. We also consider the one-round quantum communication complexity of set membership and show tight bounds.

We study complete axiomatizations for different notions of probabilistic bisimulation on a recursion free process algebra with probability and nondeterminism under alternating and non-alternating semantics. The axioms that do not involve probability coincide with the original axioms of Milner. The axioms that involve probability differ depending on the bisimulation under examination and on the semantics that is used, thus revealing the implications of the different choices.

We propose a type system to ensure the property of noninterference in a system of concurrent programs, described in a standard imperative language extended with parallelism. Our proposal is in the line of some recent work by Irvine, Volpano and Smith. Our type system, as well as our semantics for concurrent programs, seem more natural and less restrictive than those originally presented by these authors. Moreover, we show how to adapt the type system in order to preserve the noninterference results in the presence of scheduling policies, while remaining in a nonprobabilistic setting.

We consider the problem of synthesizing distributed controllers for reactive systems against local specifications. We show that a larger class of architectures become decidable in comparison to the analogous problem for global specifications. We identify the exact class of architectures for which the problem is decidable. Our results also show the decidability of a related realizability problem for local specifications.

The Ambient calculus [4] is a model for mobile distributed computing. An ambient is the unit of movement. Processes within the same ambient may exchange messages; ambients may be nested, so to form a hierarchical structure. The three primitives for movement allow: an ambient to enter another ambient, n[ inm. P | Q] | m[R] → m[ n[ P | Q] | R]; an ambient to exit another ambient, m[ n[ outm. P | Q] | R] → n[ P | Q] ~ m[R]; a process to dissolve an ambient boundary thus obtaining access to its content, open n. P ~ n[Q] → P | Q.

It has been argued that Boolean-valued logics and associated discrete notions of behavioural equivalence sit uneasily with semantic models featuring quantitative data, like probabilistic transition systems. In this paper we present a pseudometric on a class of reactive probabilistic transition systems yielding a quantitative notion of behavioural equivalence. The pseudometric is defined via the terminal coalgebra of a functor based on the Hutchinson metric on the space of Borel probability measures on a metric space. We also characterize the distance between systems in terms of a real-valued modal logic.

A “based” plane triangulation is a plane triangulation with one designated edge on the outer face. In this paper we give a simple algorithm to generate all biconnected based plane triangulations with at most n vertices. The algorithm uses O(n) space and generates such triangulations in O(1) time per triangulation without duplications. The algorithm does not output entire triangulations but the difference from the previous triangulation. By modifying the algorithm we can generate all biconnected based plane triangulation having exactly n vertices including exactly r vertices on the outer face in O(1) time per triangulation without duplications, while the previous best algorithm generates such triangulations in O(n2) time per triangulation. Also we can generate without duplications all biconnected (non-based) plane triangulations having exactly n vertices including exactly r vertices on the outer face in O(r2n) time per triangulation, and all maximal planar graphs having exactly n vertices in O(n3) time per graph.

Arc-annotated sequences are useful in representing the structural information of RNA and protein sequences. The LONGEST ARC- PRESERVING COMMON SUBSEQUENCE (LAPCS) Problem has been introduced in [11] as a framework for studying the similarity of arc-annotated sequences. Several algorithmic and complexity results on the LAPCS problem have been presented in [1117]. In this paper, we continue this line of research and present new algorithmic and complexity results on the LAPCS problem restricted to two nested arc-annotated sequences, denoted as LAPCS(NESTED, NESTED). The restricted problem is perhaps the most interesting variant of the LAPCS problem and has important applications in the comparison of RNA secondary and tertiary structures. Particularly, we prove that LAPCS(NESTED, NESTED) is NP-hard, which answers an open question in [11]. We then present a polynomial-time approximation scheme for LAPCS(NESTED, NESTED) with an additional c- diagonal restriction. An interesting special case, upunary LAPCS(NESTED, NESTED), is also investigated.

We consider the most basic visibility-based pursuit-evasion problem defined as follows: Given a polygonal region, a searcher with 360° vision, and an unpredictable intruder that is arbitrarily faster than the searcher, plan the motion of the searcher so as to see the intruder. In this paper, we present simple necessary and sufficient conditions for a polygon to be searchable, which settles a decade-old open problem raised in [13]. We also show that every searchable polygon is also searchable by a searcher with two flashlights (that is, two ray visions). This implies, combined with the previous work [7], that there is an O(n2)-time algorithm for constructing a search path for an n-sided polygon.

A new balancing method for binary search trees is presented, which achieves logarithmic worst-case cost on searches and updates. The method uses the sizes of the subtrees as balancing information; therefore operations by rank are efficiently performed without any changes in the data structure. Compared to weighted binary search trees [7], which also achieve logarithmic worst-case cost by making use of the sizes of the subtrees, the operations involved with our method are likely to be less costly in most real situations.

If the genetic maps of two species are modelled as permutations of (homologous) genes, the number of chromosomal rearrangements in the form of deletions, block moves, inversions etc. to transform one such permutation to another can be used as a measure of their evolutionary distance. Motivated by such scenarios, we study problems of computing distances between permutations as well as matching permutations in sequences, and finding most similar permutation from a collection (“nearest neighbor”).We adopt a general approach: embed permutation distances of relevance into well-known vector spaces in an approximately distance-preserving manner, and solve the resulting problems on the well-known spaces. Our results are as follows: —We present the first known approximately distance preserving embeddings of these permutation distances into well-known spaces.—Using these embeddings, we obtain several results, including the first known efficient solution for approximately solving nearest neighbor problems with permutations and the first known algorithms for finding permutation distances in the “data stream” model.—We consider a novel class of problems called permutation matching problems which are similar to string matching problems, except that the pattern is a permutation (rather than a string) and present linear or near-linear time algorithms for approximately solving permutation matching problems; in contrast, the corresponding string problems take significantly longer.

In this paper we initiate the study of testing properties of hypergraphs. The goal of property testing is to distinguish between the case whether a given object has a certain property or is “far away” from the property. We prove that the fundamental problem of ℓ-colorability of k-uniform hypergraphs can be tested in time independent of the size of the hypergraph. We present a testing algorithm that examines only (k l/∈o(k) entries of the adjacency matrix of the input hypergraph, where ∈ is a distance parameter independent of the size of the hypergraph. Notice that this algorithm tests only a constant number of entries in the adjacency matrix provided that ℓ, k, and ∈ are constant.

A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, in such a way that no two adjacent or incident elements receive the same color. A graph G is s-degenerated for a positive integer s if G can be reduced to a trivial graph by successive removal of vertices with degree ≤ s. We prove that an s-degenerated graph G has a total coloring with Δ + 1 colors if the maximum degree Δ of G is sufficiently large, say Δ ≥ 4s+3. Our proof yields an efficient algorithm to find such a total coloring. We also give a linear-time algorithm to find a total coloring of a graph G with the minimum number of colors if G is a partial k-tree, i.e. the tree-width of G is bounded by a fixed integer k.

We examine several decidability questions suggested by questions about all-optical networks, related to the gap between maximal load and number of colors (wavelengths) needed for a legal routing on a fixed graph. We prove the multiple fiber conjecture: for every fixed graph G there is a number LG such that in the communication network with LG parallel fibers for each edge of G, there is no gap (for any load). We prove that for a fixed graph G the existence of a gap is computable, and give an algorithm to compute it. We develop a decomposition theory for paths, defining the notion of prime sets of paths that are finite building blocks for all loads on a fixed graph. Properties of such decompositions yield our theorems.

We study a rather generic communication/coordination/ computation problem: in a finite network of agents, each initially having one of the two possible states, can the majority initial state be computed and agreed upon by means of local computation only? We describe the architecture of networks that are always capable of reaching the consensus on the majority initial state of its agents. In particular, we show that, for any truly local network of agents, there are instances in which the network is not capable of reaching such consensus. Thus, every truly local computation approach that requires reaching consensus is not failure- free.

Trace monoids are well-studied objects in computer science where they serve as a basic algebraic tool for analyzing concurrent systems. The question whether the existential theory of trace equations is decidable has been solved positively in 1996. Free partially commutative groups (graph groups) generalize trace monoids in the sense that every element has an inverse. In this paper we show that the existential theory of equations over graph groups is decidable, too. Our decision procedure is non-elementary, but if a certain graph theoretical parameter is viewed as a constant, then we obtain a PSPACE-completeness result. Restricting ourselves to trace monoids we still obtain a better complexity result, as it was known previously.

Formal power series are an extension of formal languages. Recognizable formal power series can be captured by the so-called weighted finite automata, generalizing finite state machines. In this paper, motivated by codings of formal languages, we introduce and investigate two types of transformations for formal power series. We characterize when these transformations preserve rationality, generalizing the recent results of Zhang [15] to the formal power series setting. We show, for example, that the “square-root” operation, while preserving regularity for formal languages, preserves rationality for formal power series when the underlying semiring is commutative or locally finite, but not in general.

We generalize the interaction between Sturmian infinite words and rotations of the 1-dimensional torus by giving a set of necessary and sufficient conditions for a language to be a natural coding of a three-interval exchange. This solves an old question of Rauzy, and allows us to give a complete combinatorial description of such languages through an algorithm of simultaneous approximation.

Let ℭ be a class of automata (in a precise sense to be defined) and ℭc the class obtained by augmenting each automaton in ℭ with finitely many reversal-bounded counters. We first show that if the languages defined by ℭ are effectively semilinear, then so are the languages defined by ℭc, and, hence, their emptiness problem is decidable. This result is then used to show the decidability of various problems concerning morphisms and commutation of languages. We also prove a surprising undecidability result: given a fixed two element code K, it is undecidable whether a given context-free language L commutes with K, i.e., LK = KL.

We deal with the star problem in trace monoids which means to decide whether the iteration of a recognizable trace language is recognizable. We consider trace monoids K_n={a₁b₁}* × … ×{a _n b _n }*. Our main theorem asserts that the star problem is decidable in a trace monoid M iff it is decidable in the biggest Kn submonoid in M. Thus, future research on the star problem can focus on the trace monoids Kn. The recently shown decidability equivalence between the star problem and the finite power problem [14] plays a crucial role in the paper.

We introduce the notion of weak morphisms of trace monoids and use it to deal with the problem of deciding the existence of codings between trace monoids. We prove that this problem is not recursively enumerable, which answers the question raised by Ochmański in 1988. We also show its decidability when restricted to instances with domain monoids defined by acyclic dependence graphs.

We consider the set Γ(n) of all period sets of strings of length n over a finite alphabet. We show that there is redundancy in period sets and introduce the notion of an irreducible period set. We prove that Γ(n) is a lattice under set inclusion and does not satisfy the Jordan- Dedekind condition.We propose the first enumeration algorithm for Γ(n) and improve upon the previously known asymptotic lower bounds on the cardinality of Γ(n). Finally, we provide a new recurrence to compute the number of strings sharing a given period set.

We give simple algorithms for the construction of generator matrices for minimal tail-biting trellises for a powerful and practical subclass of the linear cyclic codes, from which the combinatorial representation in the form of a graph can be obtained by standard procedures.

Although the set of reachable states of a lossy channel system (LCS) is regular, it is well-known that this set cannot be constructed effectively. In this paper, we characterize significant classes of LCS for which the set of reachable states can be computed. Furthermore, we show that, for slight generatlizations of these classes, computability can no longer be achieved.To carry out our study, we define rewriting systems which capture the behaviour of LCS, in the sense that (i) they have a FIFO-like semantics and (ii) their languages are downward closed with respect to the substring relation. The main result of the paper shows that, for context-free rewriting systems, the corresponding language can be computed. An interesting consequence of our results is that we get a characterization of classes of meta-transitions whose post-images can be effectively constructed. These meta-transitions consist of sets of nested loops in the control graph of the system, in contrast to previous works on meta-transitions in which only single loops are considered.Essentially the same proof technique we use to show the result mentioned above allows also to establish a result in the theory of 0L-systems, i.e., context-free parallel rewriting systems. We prove that the downward closure of the language generated by any 0L-system is effectively regular.

Hierarchical State Machines (HSMs) are a natural model for representing the behavior of software systems. In this paper, we investigate a variety of model-checking problems for an extension of HSMs in which state machines are allowed to call each other recursively.

A cryptographic protocol can be described as a system of concurrent processes, and analysis of the traces generated by this system can be used to verify authentication and secrecy properties of the protocol. However, this approach suffers from a state-explosion problem that causes the set of states and traces to be typically infinite or very large. In this paper, starting from a process language inspired by the spi-calculus, we propose a symbolic operational semantics that relies on unification and leads to compact models of protocols. We prove that the symbolic and the conventional semantics are in full agreement, and then give a method by which trace analysis can be carried out directly on the symbolic model. The method is proven to be complete for the considered class of properties and is amenable to automatic checking.

We introduce a class of tree automata that perform tests on a memory that is updated using function symbol application and projection. The language emptiness problem for this class of tree automata is shown to be in DEXPTIME. We also introduce a class of set constraints with equality tests and prove its decidability by completion techniques and a reduction to tree automata with one memory. Set constraints with equality tests may be used to decide secrecy for a class of cryptographic protocols that properly contains a class of memoryless “ping-pong protocols” introduced by Dolev and Yao.

We give efficient algorithms, beating or matching optimal known bounds, for computing a variety of simulation relations on the state space of a Büchi automaton. Our algorithms are derived via a unified and simple parity-game framework. This framework incorporates previously studied notions like fair and direct simulation, but our main motivation is state space reduction, and for this purpose we introduce a new natural notion of simulation, called delayed simulation. We show that, unlike fair simulation, delayed simulation preserves the automaton language upon quotienting, and that it allows substantially better state reduction than direct simulation.We use the parity-game approach, based on a recent algorithm by Jurdzinski, to efficiently compute all the above simulation relations. In particular, we obtain an O(mn3)-time and O(mn)-space algorithm for computing both the delayed and fair simulation relations. The best prior algorithm for fair simulation requires time O(n6) ([HKR97]).Our framework also allows one to compute bisimulations efficiently: we compute the fair bisimulation relation in O(mn3) time and O(mn) space, whereas the best prior algorithm for fair bisimulation requires time O(n10) ([HR00]).

The principal aim of model checking is to provide efficient decision procedures for the evaluation of certain logical formulae over finite relational structures. Graphs and hypergraphs are important examples of such structures. If no restrictions are imposed on the logical formulae and on the structures under consideration, then this problem of model checking has a very high computational complexity. Hence, several restrictions have been proposed in the literature on the logical formulae and/or on the structures under consideration, in order to guarantee the tractability of this decision problem, e.g.: acyclicity, bounded tree-width, query-width and hypertree-width in case of queries as well as bounded tree-width and clique-width in case of structures. In this paper, we provide a detailed comparison of the expressive power of these restrictions.

The ITU standard for MSCs provides a useful framework for visualizing communication protocols. HMSCs can describe a collection of MSC scenarios in early stages of system design. They extend finite state systems by partial order semantics and asynchronous, unbounded message exchange.Usually we ask whether an HMSC can be implemented, for instance by a finite state protocol. This question has been shown to be undecidable [5]. Motivated by the paradigm of reverse engineering we study in this paper the converse translation, specifically the question whether a finite state communication protocol can be transformed into an equivalent HMSC. This kind of translation is needed when e.g. different forms of specification (HMSC, finite automata, temporal logic) must be integrated into a single one, for instance into an HMSC.We show in this paper that translating finite state automata into HMSCs is feasible under certain natural assumptions. Specifically, we show that we can test in polynomial time whether a finite state protocol given by a Büchi automaton is equivalent to an HMSC, provided that the automaton satisfies the diamond property (the precise bound is NLOGSPACE-complete). The diamond property is a natural property induced by concurrency. Under the weaker assumption of bounded Büchi automata we show that the test is co-NP-complete. Finally, without any buffer restriction the problem is shown to be undecidable.

This paper addresses the natural relaxation of the path coloring problem, in which one needs to color directed paths on a symmetric directed graph with a minimum number of colors, in such a way that paths using the same arc of the graph have different colors. This classic combinatorial problem finds applications in the minimization of the number of wavelengths in wavelength division multiplexing (wdm) all-optical networks.

Web objects are stored and can be requested from numerous servers, including authoritative “origin” servers and caches. Objects can be modified only by their origin servers and weak consistency with cached copies is maintained by limiting their lifetime durations. Copies fetched from origin servers are received with maximum time-to-live (TTL) that equals their lifetime duration whereas copies obtained through a cache have shorter TTLs since their age (elapsed time since fetched from the origin) is deducted from their lifetime duration.A request served by a cache constitutes a hit if the cache has a fresh copy of the object. Otherwise, the request is considered a miss and is propagated to another server. Performance is measured by the number of requests constituting cache misses. It is evident that the number of cache misses depends on the age of the copies the cache receives. Thus, a cache that sends requests to another cache would suffer more misses than a cache that sends requests directly to an authoritative server. More subtly, the number of misses depends on the particular configuration of higher-level caches, e.g., whether one or more higher-level caches are used. Guided by practices for Web caching, we model and compare different configurations. We also analyze the effect of pre-term refreshes at high-level caches and extended lifetimes at low-level caches and reveal patterns that may seem counter-intuitive at first. Even though TTL- based consistency is very widely used, our work seems to be the first to formally analyze it. Our analysis yields insights and guidelines for improving the performance of Web caches.

This article focuses on routing messages along shortest paths in tree networks, using compact distributed data structures. We mainly prove that n-node trees support routing schemes with message headers, node addresses, and local memory space of size O(log n) bits, and such that every local routing decision is taken in constant time. This improves the best known routing scheme by a factor of O(log n) in term of both memory requirements and routing time. Our routing scheme requires headers and addresses of size slightly larger than log n, motivated by an inherent trade-off between address-size and memory space, i.e., any routing scheme with addresses on log n bits requires Ω(√n) bits of local memory-space. This shows that a little variation of the address size, e.g., by an additive O(log n) bits factor, has a significant impact on the local memory space.

In contrast to classical offline k-k routing, the online packet routing problem allows for an arbitrary number of packets with arbitrary end points and release times. We study this problem on linear array and ring networks. We generalize an earlier result for the offline problem by showing that Farthest First (FF) scheduling is optimal with respect to makespan on linear arrays. We also show that two other algorithms (Longest in System (LIS) and Moving Priority (MP)) have competitive ratio 2 with respect to makespan on linear arrays. For bidirectional rings, we show that, the competitive ratio of shortest path routing combined with LIS or MP scheduling is in [2:5; 3) and the competitive ratio of shortest path routing combined with FF scheduling is 2. The latter algorithm is optimal among deterministic memoryless algorithms and all algorithms of which we are aware in the literature.

Gossiping has been considered intensively for butterflies and “regular” butterflies (which have no wrap-around connections). In the telephone communication model, for a butterfly of order k, the best previous gossiping algorithms require 2 1/2 • k and 3 • k communication rounds, respectively. By new asymptotic methods we break through these bounds, proving new bounds of 2 1/4 • k + o(k) and 2 1/2 • k + o(k).

Scenario-based specifications such as message sequence charts (MSC) offer an intuitive and visual way of describing design requirements. MSC-graphs allow convenient expression of multiple scenarios, and can be viewed as an early model of the system that can be subjected to a variety of analyses. Problems such as LTL model checking are known to be decidable for the class of bounded MSC-graphs.Our first set of results concerns checking realizability of bounded MSC- graphs. An MSC-graph is realizable if there is a distributed implementation that generates precisely the behaviors in the graph. There are two notions of realizability, weak and safe, depending on whether or not we require the implementation to be deadlock-free. It is known that for a set of MSCs, weak realizability is coNP-complete while safe realizability has a polynomial-time solution. We establish that for bounded MSC-graphs, weak realizability is, surprisingly, undecidable, while safe is in E upxpspace. Our second set of results concerns verification of MSC-graphs. While checking properties of a graph G, besides verifying all the scenarios in the set L(G) of MSCs specified by G, it is desirable to verify all the scenarios in the set Lw(G)—the closure of G, that contains the implied scenarios that any distributed implementation of G must include. For checking whether a given MSC M is a possible behavior, checking M ∈ L(G) is NP-complete, but checking M ∈ Lw(G) has a quadratic solution. For temporal logic specifications, considering the closure makes the verification problem harder: while checking LTL properties of L(G) is P upspace-complete and checking local properties has polynomial-time solutions, even for boolean combinations of local properties of Lw(G), verifying acyclic graphs is coNP-complete and verifying bounded graphs is undecidable. .

We study the model-checking problem of message-sequence graphs (MSGs). In the sequential setting, we consider the set of message- sequence charts (MSCs) represented by an MSG and tackle specifications given in monadic second-order logic. We show that this problem, without any restrictions on the MSGs, is decidable. We then turn to branching behaviours of MSGs, define a notion of an unfolding of an MSG, and show that the model-checking problem on unfoldings is also decidable. Our results are stronger and imply that, over an appropriate universe, satisfiability and synthesis of MSCs and MSGs, respectively, are decidable.

We present a circular assume-guarantee rule in an abstract setting (of sets over a partially-ordered domain). The rule has a mathematically concise side condition. Now, in order to prove an assume- guarantee rule in a concrete setting, all we need to do is to is to instantiate the abstract setting and check the side condition; i.e., we need not redo the notorious circularity argument again. We use this frame- work to prove a new assume-guarantee rule for Kripke structures. That rule generalizes existing assume-guarantee rules for other settings such as Reactive Modules or Mealy machines.

Compositional proofs about systems of many components require circular reasoning principles in which properties of other components need to be assumed in proving the properties of each individual component. A number of such circular assume-guarantee rules have been proposed for different concurrency models and different forms of property specifications. In this paper, we provide a framework that unifies and extends these results. We define an assume-guarantee semantics for properties expressible as least or greatest fixed points, and a circular compositional rule that is sound with respect to this semantics. We demonstrate the utility of this general rule by applying it to trace semantics with linear temporal logic specifications, and trace tree semantics with automata refinement specifications. For traces, we derive a new assume-guarantee rule for the “weakly until” operator of linear temporal logic and show that previously proposed assume-guarantee rules can be seen as special instances of our rule. For trace trees, we derive a rule for parallel composition of Moore machines, and show that the rule of [7] is a special instance thus yielding an alternate proof of the results in [7].

We consider the well known problem of scheduling jobs with release dates to minimize their average weighted completion time. When multiple machines are available, the machine environment may range from identical machines (the processing time required by a job is invariant across the machines) at one end of the spectrum to unrelated machines (the processing time required by a job on each machine is specified by an arbitrary vector) at the other end. While the problem is strongly NP-hard even in the case of a single machine, constant factor approximation algorithms are known for even the most general machine environment of unrelated machines. Recently a PTAS was discovered for the case of identical parallel machines [1]. In contrast, the problem is MAX SNP-hard for unrelated machines [11]. An important open problem was to determine the approximability of the intermediate case of uniformly related machines where each machine has a speed and it takes p=s time to process a job of size p on a machine with speed s. We resolve the complexity of this problem by obtaining a PTAS. This improves the earlier known approximation ratio of (2 + ∈).

We consider the problem of scheduling a sequence of tasks in a multi-processor system with conflicts. Conflicting processors cannot process tasks at the same time. At certain times new tasks arrive in the system, where each task specifies the amount of work (processing time) added to each processor’s workload. Each processor stores this workload in its input buffer. Our objective is to schedule task execution, obeying the conflict constraints, and minimizing the maximum buffer size of all processors. In the off-line case, we prove that, unless P = NP, the problem does not have a polynomial-time algorithm with a polynomial approximation ratio. In the on-line case, we provide the following results: (i) a competitive algorithm for general graphs, (ii) tight bounds on the competitive ratios for cliques and complete k-partite graphs, and (iii) a (Δ/2 + 1)-competitive algorithm for trees, where Δ is the diameter. We also provide some results for small graphs with up to 4 vertices.

We consider the problem of scheduling n independent multi- processor tasks with release dates on a fixed number of processors, where the objective is to compute a non-preemptive schedule minimizing the average weighted completion time. For each task, in addition to its processing time and release date, there is given a prespecified, dedicated subset of processors which are required to process the task simultaneously. We propose here a polynomial-time approximation scheme for the problem, making substantial improvement on previous results and following the recent developments [1215] on approximation schemes for scheduling problems with the average weighted completion time objective.

We consider the scheduling problem of minimizing the average weighted job completion time on a single machine under precedence constraints. We show that this problem with arbitrary job weights, the special case of the problem where all job weights are one, and several other special cases of the problem all have the same approximability threshold with respect to polynomial time approximation algorithms. Moreover, for the special case of interval order precedence constraints and for the special case of convex bipartite precedence constraints, we give a polynomial time approximation algorithm with worst case performance guarantee arbitrarily close to the golden ratio $$ \frac{1} {2}(1 + \sqrt 5 ) \approx 1.61803 $$ .

Optimistic asynchronous multi-party contract signing protocols have received attention in recent years as a compromise between efficient protocols and protocols avoiding a third party as a bottleneck of security. “Optimistic“ roughly means: in case all participants are honest and receive the messages from the other participants as expected, the third party is not involved at all. The best solutions known so far terminate within t + 2 rounds in the optimistic case, for any fixed set of n signatories and allowing up to t < n dishonest signatories. The protocols presented here achieve a major improvement compared to the state of the art: The number of rounds R is reduced from O(t) to O(1) for all n ≤ 2t + 1, and for n < 2t + 1, R grows remarkably slowly compared with numbers of rounds in $$ o(t):If t \approx \frac{k} {{k + 1}}n then R \approx 2k $$ .

A Private Information Retrieval (PIR) protocol enables a user to retrieve a data item from a database while hiding the identity of the item being retrieved. In a t-private, k-server PIR protocol the database is replicated among k servers, and the user’s privacy is protected from any collusion of up to t servers. The main cost-measure of such protocols is the communication complexity of retrieving a single bit of data.This work addresses the information-theoretic setting for PIR, in which the user’s privacy should be unconditionally protected from collusions of servers. We present a unified general construction, whose abstract components can be instantiated to yield both old and new families of PIR protocols. A main ingredient in the new protocols is a generalization of a solution by Babai, Kimmel, and Lokam to a communication complexity problem in the so-called simultaneous messages model.Our construction strictly improves upon previous constructions and resolves some previous anomalies. In particular, we obtain: (1) t-private k-server PIR protocols with O(n1/⌊(2k-1)/tc⌋) communication bits, where n is the database size. For t > 1, this is a substantial asymptotic improvement over the previous state of the art; (2) a constant-factor improvement in the communication complexity of 1-private PIR, providing the first improvement to the 2-server case since PIR protocols were introduced; (3) efficient PIR protocols with logarithmic query length. The latter protocols have applications to the construction of efficient families of locally decodable codes over large alphabets and to PIR protocols with reduced work by the servers.

Approximation algorithms can sometimes provide effcient solutions when no efficient exact computation is known. In particular, approximations are often useful in a distributed setting where the inputs are held by different parties and are extremely large. Furthermore, for some applications, the parties want to cooperate to compute a function of their inputs without revealing more information than necessary.If f is an approximation to f, secure multiparty computation of f allows the parties to compute f without revealing unnecessary information. However, secure computation of f may not be as private as secure computation of f, because the output of f may itself reveal more information than the output of f. In this paper, we present definitions of secure multiparty approximate computations that retain the privacy of a secure computation of f. We present an efficient, sublinear-communication, private approximate computation for the Hamming distance and an efficient private approximation of the permanent.

We present the first private information retrieval (PIR) scheme which is both, deterministically correct and has poly-logarithmic communication complexity. Our PIR protocol is symmetrically secure, and improves by a few orders of magnitude the known probabilistically correct poly-logarithmic scheme. This result is achieved as an application of our methodology which introduces a broad family of games, called Secure Games with Polynomial Expressions (SGPEs), that involve two interacting players: Alice and Bob. The objective of these games is the secure “interactive computation” of the value of a polynomial expression which is made up of polynomials and field elements that both players distributedly contribute to the game. The players wish to keep some or all the data (field elements and polynomials) they contribute to the game, secret and independently secure. We show that any SGPE can be played much more efficiently than by using generic methods, and so that no party reveals more than what it intends to. Besides the above mentioned PIR application, we present additional applications such as the “lists’ intersection predicate” which is useful for secure conduct of e-commerce procedures, such as negotiation methods known as “settlement escrows” in the legal/ economics/ business literature.

A crucial way for reducing the search space in automated deduction are the so-called selection strategies: in each clause, the subset of selected literals are the only ones involved in inferences.For first-order Horn clauses without equality, resolution is complete with an arbitrary selection of one single literal in each clause [dN96].For Horn clauses with built-in equality, i.e., paramodulation-based inference systems, the situation is far more complex. Here we show that if a paramodulation-based inference system is complete with eager selection of negative equations and, moreover, it is compatible with equality constraint inheritance, then it is complete with arbitrary selection strategies. A first important application of this result is the one for paramodulation wrt. non-monotonic orderings, which was left open in [BGNR99].

We present a logical framework ϒ for reasoning on a very general class of languages featuring binding operators, called nominal algebras, presented in higher-order abstract syntax (HOAS). ϒ is based on an axiomatic syntactic standpoint and it consists of a simple types theory à la Church extended with a set of axioms called the Theory of Contexts, recursion operators and induction principles. This framework is rather expressive and, most notably, the axioms of the Theory of Contexts allow for a smooth reasoning of schemata in HOAS. An advantage of this framework is that it requires a very low mathematical and logical overhead. Some case studies and comparison with related work are briefly discussed.

We show the NP-completeness of the existential theory of term algebras with the Knuth-Bendix order by giving a nondeterministic polynomial-time algorithm for solving Knuth-Bendix ordering constraints.

We construct a representation of the institution of the algebraic specification language Casl in an institution called enriched Casl. Enriched Casl satisfies the amalgamation property, which fails in the Casl institution, as well as its converse. Thus, the previously suggested institution-independent semantics of architectural specifications is actually applicable to Casl. Moreover, a variety of results for institutions with amalgamation, such as computation of normal forms and theorem proving for structured specifications, can now be used for Casl.

We work with an extension of Resolution, called Res(2), that allows clauses with conjunctions of two literals. In this system there are rules to introduce and eliminate such conjunctions. We prove that the weak pigeonhole principle PHP _cn n and random unsatisfiable CNF formulas require exponential-size proofs in this system. This is the strongest system beyond Resolution for which such lower bounds are known. As a consequence to the result about the weak pigeonhole principle, Res(log) is exponentially more powerful than Res(2). Also we prove that Resolution cannot polynomially simulate Res(2), and that Res(2) does not have feasible monotone interpolation solving an open problem posed by Krajìček.

We prove a general upper bound on the tradeoff between time and space that suffices for the reversible simulation of irreversible computation. Previously, only simulations using exponential time or quadratic space were known. The tradeoff shows for the first time that we can simultaneously achieve subexponential time and subquadratic space. The boundary values are the exponential time with hardly any extra space required by the Lange-McKenzie-Tapp method and the (log 3)th power time with square space required by the Bennett method. We also give the first general lower bound on the extra storage space required by general reversible simulation. This lower bound is optimal in that it is achieved by some reversible simulations.

Classical Hausdorff dimension was recently effectivized using gales (betting strategies that generalize martingales), thereby endowing various complexity classes with dimension structure and also defining the constructive dimensions of individual binary (infinite) sequences. In this paper we use gales computed by multi-account finite-state gamblers to develop the finite-state dimensions of sets of binary sequences and individual binary sequences. Every rational sequence (binary expansion of a rational number) has finite-state dimension 0, but every rational number in [0; 1] is the finite-state dimension of a sequence in the low-level complexity class AC₀. Our main theorem shows that the finite-state dimension of a sequence is precisely the infimum of all compression ratios achievable on the sequence by information-lossless finite-state compressors.

We study the complexity of counting the number of elements in intervals of feasible partial orders. Depending on the properties that partial orders may have, such counting functions have different complexities. If we consider total, polynomial-time decidable orders then we obtain exactly the #P functions. We show that the interval size functions for polynomial-time adjacency checkable orders are tightly related to the class FPSPACE(poly): Every FPSPACE(poly) function equals a polynomial-time function subtracted from such an interval size function. We study the function #DIV that counts the nontrivial divisors of natural numbers, and we show that #DIV is the interval size function of a polynomial-time decidable partial order with polynomial-time adjacency checks if and only if primality is in polynomial time.

So far, not much is known on communication issues for computations on distributed systems, where the components are weak and simultaneously the communication bandwidth is severely limited. We consider synchronous systems consisting of finite automata which communicate by sending messages while working on a shared read-only data. We consider the number of messages necessary to recognize a language as a its complexity measure.We present an interesting phenomenon that the systems described require either a constant number of messages or at least Ω((log log log n)c) of them (in the worst case) for input data of length n and some constant c. Thus, in the hierarchy of message complexity classes there is a gap between the languages requiring only O(1) messages and those that need a non-constant number of messages. We show a similar result for systems of one-way automata. In this case, there is no language that requires ω(1) and o(log n) messages (in the worst case). These results hold for any fixed number of automata in the system.The lower bound arguments presented in this paper depend very much on results concerning solving systems of diophantine equations and in- equalities.

We consider a model of learning Boolean functions from quantum membership queries. This model was studied in [26], where it was shown that any class of Boolean functions which is information- theoretically learnable from polynomially many quantum membership queries is also information-theoretically learnable from polynomially many classical membership queries.In this paper we establish a strong computational separation between quantum and classical learning. We prove that if any cryptographic one- way function exists, then there is a class of Boolean functions which is polynomial-time learnable from quantum membership queries but not polynomial-time learnable from classical membership queries. A novel consequence of our result is a quantum algorithm that breaks a general cryptographic construction which is secure in the classical setting.