Mathematical Foundations of Computer Science 2005

In the last couple of decades, network connected systems have gradually replaced centralized parallel computing machines. To provide smooth operation of network applications, the underlying system has to provide so-called

basic services

. One of the most crucial services is to provide a transparent access to data like variables, databases, memory pages, or .les, which are shared by the instances of programs running at nodes of the network.

Knot theory emerged in the nineteenth century for needs of physics and chemistry as these needs were understood those days. After that the interest of physicists and chemists was lost for about a century. Nowadays knot theory has made a comeback. Knot theory and other areas of topology are no more considered as abstract areas of classical mathematics remote from anything of practical interest. They have made deep impact on quantum field theory, quantum computation and complexity of computation.

A sequential algorithm just follows its instructions and thus cannot make a nondeterministic choice all by itself, but it can be instructed to solicit outside help to make a choice. Similarly, an object-oriented program cannot create a new object all by itself; a create-a-new-object command solicits outside help. These are but two examples of intra-step interaction of an algorithm with its environment. Here we motivate and survey recent work on interactive algorithms within the Behavioral Computation Theory project.

Membrane computing is a branch of molecular computing that aims to develop models and paradigms that are biologically motivated. It identifies an unconventional computing model, namely a P system, from natural phenomena of cell evolutions and chemical reactions. Because of the nature of maximal parallelism inherent in the model, P systems have a great potential for implementing massively concurrent systems in an efficient way that would allow us to solve currently intractable problems (in much the same way as the promise of quantum and DNA computing) once future bio-technology (or silicon-technology) gives way to a practical bio-realization (or chip realization). Here we report on recent results that answer some interesting and fundamental open questions in the field. These concern computational issues such as determinism versus nondeterminism, membrane and alphabet-size hierarchies, and various notions of parallelism.

A substantial amount of research in graph theory continues to concentrate on the existence of hamiltonian cycles and perfect matchings. A classic theorem of Dirac states that a sufficient condition for an

n

-vertex graph to be hamiltonian, and thus, for

n

even, to have a perfect matching, is that the minimum degree is at least

n

/2. Moreover, there are obvious counterexamples showing that this is best possible.

In the

k

-party simultaneous message model,

k

–1 parties holding respectively

x

1

,

x

2

, ⋯,

x

k

 − − 1

wish to compute the value of some boolean function

f

(

x

1

,

x

2

,...,

x

k

 − − 1

), by each sending a stochastically chosen message to a

k

-th party, the

referee

, who then decides on the value of

f

with probability at least 2/3 of being correct. Let

R

||

(

f

) be the minimum number of total communication bits needed to compute

f

by any such algorithm.

The (

k

,

n

)-

Co-Linearity Problem

is defined by

CL

k

,

n

(

x

1

,

x

2

,...,

x

k

 − − 1

) = 1, if and only if ⊕

1 ≤ i ≤ k− − 1

x

i

=0

n

(where

x

i

are

n

-bit strings). It is well known that, for any fixed

k

≥ 3,

$R^{||}(CL_{k,n}) = O(n^{(k-2)/(k-1)})$

, and that the bound is tight for

k

=3. It is an interesting open question whether the bound is tight for

k

>3. In this talk we present some new results on this question. Specifically, we prove that the above bound is tight in the

linear model

, in which all the transmitted message bits are linear functions of the input bits. We also discuss

CL

k

,

n

’s quantum communication complexity, which also has received considerable attention in recent years.

Parity games and their subclasses and variants pop up in various contexts:

μ

-calculus, tree automata, program verification [3,1,8]. Such games provide only binary information indicating the winning player. However, in classical games theory [12] the emphasis is rather on how much we win or lose. Can we incorporate the information about the profits and losses into parity games?

Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NP-complete, and identified all tractable cases. Schaefer’s dichotomy theorem actually shows that there are at most two constraint satisfaction problems, up to polynomial-time isomorphism (and these isomorphism types are distinct if and only if P ≠ NP). We show that if one considers AC

0

isomorphisms, then there are exactly six isomorphism types (assuming that the complexity classes NP, P, ⊕L, NL, and L are all distinct).

Semi-algebraic objects are subsets or functions that can be described by finite boolean combinations of polynomials with real coefficients. In this paper we provide sharp estimates for the the precision and the number of trials needed in the MonteCarlo integration method to achieve a given error with a fixed confidence when approximating the mean value of semi-algebraic functions. Our study extends to the functional case the results of P. Koiran ([7]) for approximating the volume of semi-algebraic sets.

We study the computational complexity of deciding the existence of a Pure Nash Equilibrium in multi-player strategic games. We address two fundamental questions: how can we represent a game? and how can we represent a game with polynomial pay-off functions? Our results show that the computational complexity of deciding the existence of a pure Nash equilibrium in a strategic game depends on two parameters: the number of players and the size of the sets of strategies. In particular we show that deciding the existence of a Nash equilibrium in a strategic game is

NP

-complete when the number of players is large and the number of strategies for each player is constant, while the problem is Σ

$^{p}_{\rm 2}$

-complete when the number of players is a constant and the size of the sets of strategies is exponential (with respect to the length of the strategies).

The paper investigates the complexity of depth-two circuits with threshold gates and consisting of two parts.

First, we develop a method for deriving a lower bound on the size of depth two circuits with a threshold gate at the top and a certain type of gates at the bottom. We apply the method for circuits with symmetric gates at the bottom that compute the “inner product mod 2”, and obtain a lower bound of 1.3638

n

. Although our lower bound is slightly weaker than the best known lower bound of Ω(2

n

/2

/

n

), which was recently proved by Forster et al. [5,6], our method has unique features: A lower bound is obtained by solving a certain linear program, and solving larger linear programs yield higher lower bounds. We also discuss the generalization of the proposed method.

Second, we develop a simplified simulation of a depth-one threshold circuit with unbounded weights by a depth-two threshold circuit with small weights. Precisely, we give an explicit construction of depth-two circuits with small weights consist of Õ

n

5

gates that compute an arbitrary threshold function. We also give the construction of such circuits with

O

(

n

3

/log

n

) gates computing the COMPARISON and CARRY functions, and that with

O

(

n

4

/log

n

) gates computing the ADDITION function. These improve the previously known constructions on its size and simplicity.

We study the isomorphic implication problem for Boolean constraints. We show that this is a natural analog of the subgraph isomorphism problem. We prove that, depending on the set of constraints, this problem is in P, NP-complete, or NP-hard, coNP-hard, and in

${\rm P^{NP}_{||}}$

. We show how to extend the NP-hardness and coNP-hardness to

${\rm P^{NP}_{||}}$

-hardness for some cases, and conjecture that this can be done in all cases.

An abstract numeration system is a triple

S

= (

L

,Σ,<) where (Σ,<) is a totally ordered alphabet and

L

a regular language over Σ; the associated numeration is defined as follows: by enumerating the words of the regular language

L

over Σ with respect to the induced genealogical ordering, one obtains a one-to-one correspondence between ℕ and

L

. Furthermore, when the language

L

is assumed to be exponential, real numbers can also be expanded. The aim of the present paper is to associate with

S

a self-replicating multiple tiling of ăthe space, under the following assumption: the adjacency matrix of the trimmed minimal automaton recognizing

L

is primitive with a dominant eigenvalue being a Pisot unit. This construction generalizes the classical constructions performed for Rauzy fractals associated with Pisot substitutions [16], and for central tiles associated with a Pisot beta-numeration [23] .

In this paper we start the study of generalizing the Adversarial Queueing Theory

aqt

model towards a continuous scenario in which the usually assumed synchronicity of the evolution is not required anymore. We consider a model, named

continuous AQT

(

caqt

), in which packets can have arbitrary lengths, and the network links may have different speeds (or bandwidths) and propagation delays. We show that, in such a general model, having bounded queues implies bounded end-to-end packet delays and vice versa. From the network point of view, we show that networks with directed acyclic topologies are universally stable, i.e., stable independently of the protocols and the traffic patterns used in it, and that this even holds for traffic patterns that make links to be fully loaded. Concerning packet scheduling protocols, we show that the well-known

lis

,

sis

,

ftg

and

nfs

protocols remain universally stable in our model. We also show that the

caqt

model is strictly stronger than the

aqt

model by presenting scheduling policies that are unstable under the former while they are universally stable under the latter.

Feige and Kilian [5] showed that finding reasonable approximative solutions to the coloring problem on graphs is hard. This motivates the quest for algorithms that either solve the problem in most but not all cases, but are of polynomial time complexity, or that give a correct solution on all input graphs while guaranteeing a polynomial running time on average only. An algorithm of the first kind was suggested by Alon and Kahale in [1] for the following type of random

k

-colorable graphs: Construct a graph

$\mathcal{G}_{n,p,k}$

on vertex set

V

of cardinality

n

by first partitioning

V

into

k

equally sized sets and then adding each edge between these sets with probability

p

independently from each other. Alon and Kahale showed that graphs from

$\mathcal{G}_{n,p,k}$

can be

k

-colored in polynomial time with high probability as long as

p

≥

c

/

n

for some sufficiently large constant

c

. In this paper, we construct an algorithm with polynomial expected running time for

k

= 3 on the same type of graphs and for the same range of

p

. To obtain this result we modify the ideas developed by Alon and Kahale and combine them with techniques from semidefinite programming. The calculations carry over to general

k

.

It is a well-known result that the set of reachable stack contents in a pushdown automaton is a regular set of words. We consider the more general case of higher-order pushdown automata and investigate, with a particular stress on effectiveness and complexity, the natural notion of regularity for higher-order stacks: a set of level

k

stacks is regular if it is obtained by a regular sequence of level

k

operations. We prove that any regular set of level

k

stacks admits a normalized representation and we use it to show that the regular sets of a given level form an effective Boolean algebra. In fact, this notion of regularity coincides with the notion of monadic second order definability over the canonical structure associated to level

k

stacks. Finally, we consider the link between regular sets of stacks and families of infinite graphs defined by higher-order pushdown systems.

Linearly bounded Turing machines have been mainly studied as acceptors for context-sensitive languages. We define a natural family of canonical infinite automata representing their observable computational behavior, called linearly bounded graphs. These automata naturally accept the same languages as the linearly bounded machines defining them. We present some of their structural properties as well as alternative characterizations in terms of rewriting systems and context-sensitive transductions. Finally, we compare these graphs to rational graphs, which are another family of automata accepting the context-sensitive languages, and prove that in the bounded-degree case, rational graphs are a strict sub-family of linearly bounded graphs.

We prove several results about the relations between injectivity and surjectivity for sand automata. Moreover, we begin the exploration of the dynamical behavior of sand automata proving that the property of ultimate periodicity is undecidable. We believe that the proof technique used for this last result might turn out to be useful for many other results in the same context.

A distributed system is a collection of processes that can interact. Three major process interaction models in distributed systems have principally been considered: – the message passing model, – the shared memory model, – the local computation model. In each model the processes are represented by vertices of a graph and the interactions are represented by edges. In the message passing model and the shared memory model, processes interact by communication primitives: messages can be sent along edges or atomic read/write operations can be performed on registers associated with edges. In the local computation model interactions are defined by labelled graph rewriting rules; supports of rules are edges or stars. These models (and their sub-models) reflect different system architectures, different levels of synchronization and different levels of abstraction. Understanding the power of various models, the role of structural network properties and the role of the initial knowledge enhances our understanding of basic distributed algorithms. This is done with some typical problems in distributed computing: election, naming, spanning tree construction, termination detection, network topology recognition, consensus, mutual exclusion. Furthermore, solutions to these problems constitute primitive building blocks for many other distributed algorithms. A survey may be found in [FR03], this survey presents some links with several parameters of the models including synchrony, communication media and randomization. An important goal in the study of these models is to understand some relationships between them. This paper is a contribution to this goal; more precisely we establish a bridge between tools and results presented in [YK96] for the message passing model and tools and results presented in [Ang80, BCG+96, Maz97, CM04, CMZ04, Cha05] for the local computation model.

Given a distance matrix

M

that specifies the pairwise evolutionary distances between

n

species, the phylogenetic

tree

reconstruction problem asks for an edge-weighted phylogenetic tree that satisfies

M

, if one exists. We study some extensions of this problem to rooted phylogenetic

networks

. Our main result is an

O

(

n

2

log

n

)-time algorithm for determining whether there is an ultrametric galled network that satisfies

M

, and if so, constructing one. In fact, if such an ultrametric galled network exists, our algorithm is guaranteed to construct one containing the minimum possible number of nodes with more than one parent (

hybrid

nodes). We also prove that finding a largest possible submatrix

M

′ of

M

such that there exists an ultrametric galled network that satisfies

M

′ is NP-hard. Furthermore, we show that given an incomplete distance matrix (i.e., where some matrix entries are missing), it is also NP-hard to determine whether there exists an ultrametric galled network which satisfies it.

This paper studies online job scheduling on multiprocessors and, in particular, investigates the algorithms SRPT and SJF for minimizing total stretch, where the stretch of a job is its flow time (response time) divided by its processing time. SRPT is perhaps the most well-studied algorithm for minimizing total flow time or stretch. This paper gives the first resource augmentation analysis of the total stretch of SRPT, showing that it is indeed

O

(1)-speed 1-competitive. This paper also gives a simple lower bound result that SRPT is not

s

-speed 1-competitive for any

s

< 1.5.

This paper also makes contribution to the analysis of SJF. Extending the work of [4], we are able to show that SJF is

O

(1)-speed 1-competitive for minimizing total stretch. More interestingly, we find that the competitiveness of SJF can be reduced arbitrarily by increasing the processor speed (precisely, SJF is

O

(

s

)-speed (1/

s

)-competitive for any

s

≥ 1). We conjecture that SRPT also admits a similar result.

We propose a method to approximate a polygonal object by a deformable smooth surface, namely the

t

-skin defined by Edelsbrunner for all 0<

t

< 1. We guarantee that they are homeomorphic and their Hausdorff distance is at most

ε

>0. Such construction makes it possible for fully automatic, smooth and robust deformation between two polygonal objects with different topologies. En route to our results, we also give an approximation of a polygonal object with a union of balls.

We define a basis of solutions of a system of linear inequalities and present a general algorithm for finding such a basis. Our algorithm relies on an algorithm for finding a Hilbert basis for the set of nonnegative solutions of a system of linear inequalities and can be used in conjunction with any such algorithm.

Two mobile agents (robots) having distinct labels and located in nodes of an unknown anonymous connected graph, have to meet. We consider the asynchronous version of this well-studied rendezvous problem and we seek fast deterministic algorithms for it. Since in the asynchronous setting meeting at a node, which is normally required in rendezvous, is in general impossible, we relax the demand by allowing meeting of the agents inside an edge as well. The measure of performance of a rendezvous algorithm is its

cost

: for a given initial location of agents in a graph, this is the number of edge traversals of both agents until rendezvous is achieved. If agents are initially situated at a distance

D

in an infinite line, we show a rendezvous algorithm with cost

O

(

D

|

L

min

|

2

) when

D

is known and

O

((

D

+ |

L

max

|)

3

) if

D

is unknown, where |

L

min

| and |

L

max

| are the lengths of the shorter and longer label of the agents, respectively. These results still hold for the case of the ring of unknown size but then we also give an optimal algorithm of cost

O

(

n

|

L

min

|), if the size

n

of the ring is known, and of cost

O

(

n

|

L

max

|), if it is unknown. For arbitrary graphs, we show that rendezvous is feasible if an upper bound on the size of the graph is known and we give an optimal algorithm of cost

O

(

D

|

L

min

|) if the topology of the graph and the initial positions are known to agents.

The

zeta-dimension

of a set

A

of positive integers is

Dim

ζ

(

A

) = 

inf

{

s

|

ζ

A

(

s

) < ∞ },

where

$\zeta_A(s)=\sum_{n\in A}n^{-s}.$

Zeta-dimension serves as a fractal dimension on ℤ

 + 

that extends naturally and usefully to discrete lattices such as ℤ

d

, where

d

is a positive integer.

This paper reviews the origins of zeta-dimension (which date to the eighteenth and nineteenth centuries) and develops its basic theory, with particular attention to its relationship with algorithmic information theory. New results presented include a gale characterization of zeta-dimension and a theorem on the zeta-dimensions of pointwise sums and products of sets of positive integers.

We study online interval coloring problems with bandwidth. We are interested in some variants motivated by bin packing problems. Specifically we consider open-end coloring, cardinality constrained coloring, coloring with vector constraints and finally a combination of both the cardinality and the vector constraints. We construct competitive algorithms for each of the variants. Additionally, we present a lower bound of 24/7 for interval coloring with bandwidth, which holds for all the above models, and improves the current lower bound for the standard interval coloring with bandwidth.

Recently Glaßer et al. have shown that for many classes

C

including PSPACE and NP it holds that all of its nontrivial many-one complete languages are autoreducible. This immediately raises the question of whether all many-one complete languages are Turing self-reducible for such classes

C

.

This paper considers a simpler version of this question—whether all PSPACE-complete (NP-complete) languages are length-decreasing self-reducible. We show that if all PSPACE-complete languages are length-decreasing self-reducible then PSPACE = P and that if all NP-complete languages are length-decreasing self-reducible then NP = P.

The same type of result holds for many other natural complexity classes. In particular, we show that (1) not all NL-complete sets are logspace length-decreasing self-reducible, (2) unconditionally not all PSPACE-complete languages are logpsace length-decreasing self-reducible, and (3) unconditionally not all PSPACE-complete languages are polynomial-time length-decreasing self-reducible.

In this paper we propose a probabilistic analysis of the fully asynchronous behavior (i.e., two cells are never simultaneously updated, as in a continuous time process) of elementary finite cellular automata (i.e., {0,1} states, radius 1 and unidimensional) for which both states are quiescent (i.e., (0,0,0) ↦ 0 and (1,1,1) ↦ 1). It has been experimentally shown in previous works that introducing asynchronism in the global function of a cellular automaton may perturb its behavior, but as far as we know, only few theoretical work exist on the subject. The cellular automata we consider live on a ring of size

n

and asynchronism is introduced as follows: at each time step one cell is selected uniformly at random and the transition rule is applied to this cell while the others remain unchanged. Among the sixty-four cellular automata belonging to the class we consider, we show that fifty-five other converge almost surely to a random fixed point while nine of them diverge on all non-trivial configurations. We show that the convergence time of these fifty-five automata can only take the following values: either 0, Θ(

n

ln

n

), Θ(

n

2

), Θ(

n

3

), or Θ(

n

2

n

). Furthermore, the global behavior of each of these cellular automata can be guessed by simply reading its code.

In the context of comparative analysis of protein-protein interaction graphs, we use a graph-based formalism to detect the preservation of a given protein complex

G

in the protein-protein interaction graph

H

of another species with respect to (w.r.t.) orthologous proteins. Two problems are considered: the

Exact

-(

μ

G

,

μ

H

)-

Matching

problem and the

Max

-(

μ

G

,

μ

H

) problem, where

μ

G

(resp.

μ

H

) denotes in both problems the maximum number of orthologous proteins in

H

(resp.

G

) of a protein in

G

(resp.

H

). Following [FLV04], the

Exact

-(

μ

G

,

μ

H

)-

Matching

problem asks for an injective homomorphism of

G

to

H

w.r.t. orthologous proteins. The optimization version is called the

Max

-(

μ

G

,

μ

H

)-

Matching

problem and is concerned with finding an injective mapping of a graph

G

to a graph

H

w.r.t. orthologous proteins that matches as many edges of

G

as possible. For both problems, the emphasis here is clearly on bounded degree graphs and extremal small values of parameters

μ

G

and

μ

H

.

We consider three types of locally constrained graph homomorphisms: bijective, injective and surjective. We show that the three orders imposed on graphs by existence of these three types of homomorphisms are partial orders. We extend the well-known connection between degree refinement matrices of graphs and locally bijective graph homomorphisms to locally injective and locally surjective homomorphisms by showing that the orders imposed on degree refinement matrices by our locally constrained graph homomorphisms are also partial orders. We provide several equivalent characterizations of degree (refinement) matrices, e.g. in terms of the dimension of the cycle space of a graph related to the matrix. As a consequence we can efficiently check whether a given matrix

M

is a degree matrix of some graph and also compute the size of a smallest graph for which it is a degree matrix in polynomial time.

We consider the problem of packing a set of weighted rectangles into a unit size square frame [0,1] × [0,1] so as to maximize the total weight of the packed rectangles. We present polynomial time approximation schemes (PTASs) that, for any

ε

>0, find (1 -

ε

)-approximate solutions for two special cases of the problem. In the first case we pack a set of squares whose weights are equal to their areas. In the second case we pack a set of weighted rectangles into an augmented square frame [0,1 + 3

ε

] × [0,1 + 3

ε

].

We introduce nondeterministic graph searching with a controlled amount of nondeterminism and show how this new tool can be used in algorithm design and combinatorial analysis applying to both pathwidth and treewidth. We prove equivalence between this game- theoretic approach and graph decompositions called

q-branched

tree decompositions, which can be interpreted as a parameterized version of tree decompositions. Path decomposition and (standard) tree decomposition are two extreme cases of

q

-branched tree decompositions. The equivalence between nondeterministic graph searching and

q

-branched tree decomposition enables us to design an exact (exponential time) algorithm computing

q

-branched treewidth for all

q

≥ 0, which is thus valid for both treewidth and pathwidth. This algorithm performs as fast as the best known exact algorithm for pathwidth. Conversely, this equivalence also enables us to design a lower bound on the amount of nondeterminism required to search a graph with the minimum number of searchers.

Horn

 ⊃ 

is a logic programming language which extends usual

Horn

clauses by adding intuitionistic implication in goals and clause bodies. This extension can be seen as a form of structuring programs in logic programming. Restricted to the propositional setting of this language, we prove that any goal in

Horn

 ⊃ 

can be translated into a monotone Boolean circuit which is linear in the size of the goal.

We show the following results regarding complete sets.

NP-complete sets and PSPACE-complete sets are many-one autoreducible.

Complete sets of any level of PH, MODPH, or the Boolean hierarchy over NP are many-one autoreducible.

EXP-complete sets are many-one mitotic.

NEXP-complete sets are weakly many-one mitotic.

PSPACE-complete sets are weakly Turing-mitotic.

If one-way permutations and quick pseudo-random generators exist, then NP-complete languages are

m

-mitotic.

If there is a tally language in NP ∩ coNP - P, then, for every

ε

> 0, NP-complete sets are not 2

n

(1 + 

ε

)

-immune.

These results solve several of the open questions raised by Buhrman and Torenvliet in their 1994 survey paper on the structure of complete sets.

We prove that every disjoint NP-pair is polynomial-time, many-one equivalent to the canonical disjoint NP-pair of some propositional proof system. Therefore, the degree structure of the class of disjoint NP-pairs and of all canonical pairs is identical. Secondly, we show that this degree structure is not superficial: Assuming there exist P-inseparable disjoint pairs, there exist intermediate disjoint NP-pairs. That is, if (

A

,

B

) is a P-separable disjoint NP-pair and (

C

,

D

) is a P-inseparable disjoint NP-pair, then there exist P-inseparable, incomparable NP-pairs (

E

,

F

) and (

G

,

H

) whose degrees lie strictly between (

A

,

B

) and (

C

,

D

). Furthermore, between any two disjoint NP-pairs that are comparable and inequivalent, such a diamond exists.

We investigate the complexity of finding prime implicants and minimal equivalent DNFs for Boolean formulas, and of testing equivalence and isomorphism of monotone formulas. For DNF related problems, the complexity of the monotone case strongly differs from the arbitrary case. We show that it is

DP

-complete to check whether a monomial is a prime implicant for an arbitrary formula, but checking prime implicants for monotone formulas is in

L

. We show

PP

-completeness of checking whether the minimum size of a DNF for a monotone formula is at most

k

. For

k

in unary, we show the complexity of the problem to drop to

coNP

. In [Uma01] a similar problem for arbitrary formulas was shown to be

$\Sigma^P_2$

-complete. We show that calculating the minimal DNF for a monotone formula is possible in output-polynomial time if and only if

P = NP

. Finally, we disprove a conjecture from [Rei03] by showing that checking whether two formulas are isomorphic has the same complexity for arbitrary formulas as for monotone formulas.

The present paper gives a classification of the expressive power of two-variable least fixed-point logics. The main results are:

1

The two-variable fragment of monadic least fixed-point logic with parameters is as expressive as full monadic least fixed-point logic (on binary structures).

2

The two-variable fragment of

monadic

least fixed-point logic without parameters is as expressive as the two-variable fragment of

binary

least fixed-point logic without parameters.

3

The two-variable fragment of binary least fixed-point logic with parameters is strictly more expressive than the two-variable fragment of monadic least fixed-point logic with parameters (even on finite strings).

In this paper we study the properties of undirected vertex-labeled graphs and the limitations on the languages that they represent. As a main result of this paper we define the necessary and sufficient conditions for the languages to be representable by a class of undirected vertex-labeled graphs and its subclasses. We assume that all obtained results and techniques are transferable to the case of undirected edge-labeled graphs and might give us similar results. The simplicity of necessary conditions emphasizes the naturalness of the result. The proof of their sufficiency is quite non-trivial and it is based on a new notion of quasi-equivalence, that is significantly different from Myhill-Nerode equivalence and might not be reduced to it.

We prove that it is #

P

-hard to compute the mixed discriminant of rank 2 positive semidefinite matrices. We present poly-time algorithms to approximate the ”beast”. We also prove NP-hardness of two problems related to mixed discriminants of rank 2 positive semidefinite matrices. One of them, the so called Full Rank Avoidance problem, had been conjectured to be NP-Complete in [23] and in [25]. We also present a deterministic poly-time algorithm computing the mixed discriminant

D

(

A

1

,..,

A

N

) provided that the linear (matrix) subspace generated by {

A

1

,..,

A

N

} is small and discuss randomized algorithms approximating mixed discriminants within absolute error.

We introduce and study certain classes of optimization problems over the real numbers. The classes are defined by logical means, relying on metafinite model theory for so called ℝ-structures (see [9],[8]). More precisely, based on a real analogue of Fagin’s theorem [9] we deal with two classes MAX-

NP

ℝ

and MIN-

NP

ℝ

of maximization and minimization problems, respectively, and figure out their intrinsic logical structure. It is proven that MAX-

NP

ℝ

decomposes into four natural subclasses, whereas MIN-

NP

ℝ

decomposes into two. This gives a real number analogue of a result by Kolaitis and Thakur [10] in the Turing model. Our proofs mainly use techniques from [13]. Finally, approximation issues are briefly discussed.

We start investigating set algebras from a knowledge theoretical point of view. To this end, we suit hybrid logic to the context of knowledge. The common modal approach is extended in this way, which gives us the necessary expressive power. The main issues of the paper are a completeness and a decidability result for the arising logic of knowledge on algebras.

A partial information algorithm for a language

A

computes, for some fixed

m

, for input words

x

1

, ...,

x

m

a set of bitstrings containing

χ

A

(

x

1

,...,

x

m

). E.g., p-selective, approximable, and easily countable languages are defined by the existence of polynomial-time partial information algorithms of specific type. Self-reducible languages, for different types of self-reductions, form subclasses of PSPACE.

For a self-reducible language

A

, the existence of a partial information algorithm sometimes helps to place

A

into some subclass of PSPACE. The most prominent known result in this respect is: P-selective languages which are self-reducible are in P [9].

Closely related is the fact that the existence of a partial information algorithm for

A

simplifies the type of reductions or self-reductions to

A

. The most prominent known result in this respect is: Turing reductions to easily countable languages simplify to truth-table reductions[8].

We prove new results of this type. We show:

1

Self-reducible languages which are easily 2-countable are in P. This partially confirms a conjecture of [8].

2

Self-reducible languages which are (2

m

– 1,

m

)-verbose are truth-table self-reducible. This generalizes the result of [9] for p-selective languages, which are (

m

+ 1,

m

)-verbose.

3

Self-reducible languages, where the language and its complement are strongly 2-membership comparable, are in P. This generalizes the corresponding result for p-selective languages of [9].

4

Disjunctively truth-table self-reducible languages which are 2-membership comparable are in UP.

Topic:

Structural complexity.

We consider the complexity of infinite games played on finite graphs. We establish a framework in which the expressiveness and succinctness of different types of winning conditions can be compared. We show that the problem of deciding the winner in Muller games is PSPACE-complete. This is then used to establish PSPACE-completeness for Emerson-Lei games and for games described by Zielonka DAGs. Adaptations of the proof show PSPACE-completeness for the emptiness problem for Muller automata as well as the model-checking problem for such automata on regular trees. We also show co-NP-completeness for two classes of union-closed games: games specified by a basis and superset Muller games.

The traditional theory of

“part of”

relations (i.e.

mereology

) is enriched by adding the formal concept of

equivalent

and

exchangeable parts

. Various possible axioms and their roles are discussed. An approach is focused on application to model software structures.

The online squarefree recognition problem is to detect the first occurrence of a square in a string whose characters are provided as input one at a time. We present an efficient algorithm to solve this problem for strings over arbitrarily ordered alphabets. Its running time is

O

(

n

log

n

), where

n

is the ending position of the first square, which matches the running times of the fastest known algorithms for the analogous offline problem. We also present a very simple algorithm for a dynamic version of the problem over general alphabets in which we are initially given a squarefree string, followed by a series of updates, and the objective is to determine after each update if the resulting string contains a square and if so, report it and stop.

Restarting automata are a restricted model of computation that is motivated by the so-called

analysis by reduction

. A computation of a restarting automaton consists of a sequence of cycles such that in each cycle the automaton performs exactly one rewrite step, which replaces a small part of the tape content by another, even

shorter

word. Here we consider a natural generalization of this model, called

shrinking restarting automaton

, where we require that there exists a

weight function

such that each rewrite step decreases the weight of the tape content with respect to that function. While it is still unknown whether the two most general types of restarting automata, the

RWW

-automaton and the

RRWW

-automaton, differ in their expressive power, we will see that the classes of languages accepted by the shrinking

RWW

-automaton and the shrinking

RRWW

-automaton coincide. Further, we will relate shrinking

RRWW

-automata to finite-change automata, which leads to new insights into the relationships between the classes of languages characterized by (shrinking) restarting automata and some well-known time and space complexity classes.

We prove that every

two-way

nondeterministic finite automaton with

n

states has an equivalent

one-way

nondeterministic finite automaton with at most (

$^{2n}_{n+1}$

) states. We also show this bound is exact.

We consider monotone ∨, ∧-formulae

φ

of

m

atoms, each of which is a monotone inequality of the form

f

i

(

x

)≥

t

i

over the integers, where for

i

= 1,...,

m

,

$f_i : \mathbb{Z}^n \mapsto \mathbb{R}$

is a given monotone function and

t

i

is a given threshold. We show that if the ∨-degree of

φ

is bounded by a constant, then for linear, transversal and polymatroid monotone inequalities all minimal integer vectors satisfying

φ

can be generated in incremental quasi-polynomial time. In contrast, the enumeration problem for the disjunction of

m

inequalities is NP-hard when

m

is part of the input. We also discuss some applications of the above results in disjunctive programming, data mining, matroid and reliability theory.

For many problems, the investigation of their parameterized complexity provides an interesting and useful point of view. The most obvious natural parameterization for the maximum satisfiability problem—the number of satisfiable clauses—makes little sense, because at least half of the clauses can be satisfied in any formula. We look at two optimization variants of the exact satisfiability problem, where a clause is only said to be fulfilled iff exactly one of its literals is set to

true

. Interestingly, these variants behave quite differently. In the case of

ResMaxExactSAT

, where over-satisfied clauses are entirely forbidden, we show fixed parameter tractability. On the other hand, if we choose to ignore over-satisfied clauses, the

MaxExactSAT

problem is obtained. Surprisingly, it is W[1]-complete. Still, restricted variants of the problem turn out to be tractable.

For a string

A

=

a

1

...

a

n

, a

reversalρ

(

i

,

j

), 1≤

i

<

j

≤

n

, transforms the string

A

into a string

A

′=

a

1

...

a

i

 − − 1

a

j

a

j

 − − 1

...

a

i

a

j

 + 1

...

a

n

, that is, the reversal

ρ

(

i

,

j

) reverses the order of symbols in the substring

a

i

...

a

j

of

A

. In a case of signed strings, where each symbol is given a sign + or –, the reversal operation also flips the sign of each symbol in the reversed substring. Given two strings,

A

and

B

, signed or unsigned,

sorting by reversals

(

SBR

) is the problem of finding the minimum number of reversals that transform the string

A

into the string

B

.

Traditionally, the problem was studied for permutations, that is, for strings in which every symbol appears exactly once. We consider a generalization of the problem,

k

-

SBR

, and allow each symbol to appear at most

k

times in each string, for some

k

≥ 1. The main result of the paper is a simple

O

(

k

2

)-approximation algorithm running in time

O

(

k

·

n

). For instances with

$3 < k \leq O(\sqrt{log n log^* n})$

, this is the best known approximation algorithm for

k

-

SBR

and, moreover, it is faster than the previous best approximation algorithm. In particular, for

k

=

O

(1) which is of interest for DNA comparisons, we have a linear time

O

(1)-approximation algorithm.

In this paper we define a model of randomly generated databases and show how one can compute the threshold functions for queries expressible in monotone non-recursive datalog

 ≠ 

. We also show that monotone non-recursive datalog

 ≠ 

cannot express any property with a sharp threshold. Finally, we show that non-recursive datalog

 ≠ 

has a 0–1 law for a large class of probability functions, defined in the paper.

An instance of a constraint satisfaction problem is

l

-consistent if any

l

constraints of it can be simultaneously satisfied. For a set Π of constraint types,

ρ

l

(Π) denotes the largest ratio of constraints which can be satisfied in any

l

-consistent instance composed by constraints from the set Π. We study the asymptotic behavior of

ρ

l

(Π) for sets Π consisting of Boolean predicates.

We study simple greedy approximation algorithms for general class of integer packing problems. We provide a novel analysis based on the duality theory of linear programming. This enables to significantly improve on the approximation ratios of these greedy methods, and gives a unified analysis of greedy for many packing problems. We show matching lower bounds on the ratios of such greedy methods. Applications to some specific problems, including mechanism design for combinatorial auctions, are also shown.

In the maximum solution equation problem a collection of equations are given over some algebraic structure. The objective is to find an assignment to the variables in the equations such that all equations are satisfied and the sum of the variables is maximised. We give tight approximability results for the maximum solution equation problem when the equations are given over groups of the form

Z

p

, where

p

is prime. We also prove that the weighted and unweighted versions of this problem have equal approximability thresholds. Furthermore, we show that the problem is equally hard to solve even if each equation is restricted to contain at most three variables and solvable in polynomial time if the equations are restricted to contain at most two variables. All of our results also hold for a generalised version of maximum solution equation where the elements of the group are mapped arbitrarily to non-negative integers in the objective function.

This paper analyzes the computational complexity of the model checking problem for Higher Order Fixpoint Logic – the modal

μ

-calculus enriched with a typed

λ

-calculus. It is hard for every level of the elementary time/space hierarchy and in elementary time/space when restricted to formulas of bounded type order.

We consider the problem of job scheduling on a variable voltage processor with

d

discrete voltage/speed levels. We give an algorithm which constructs a minimum energy schedule for

n

jobs in

O

(

dn

log

n

) time. Previous approaches solve this problem by first computing the optimal continuous solution in

O

(

n

3

) time and then adjusting the speed to discrete levels. In our approach, the optimal discrete solution is characterized and computed directly from the inputs. We also show that

O

(

n

log

n

) time is required, hence the algorithm is optimal for fixed

d

.

The word problem for inverse monoids generated by a set Γ subject to relations of the form

e

=

f

, where

e

and

f

are both idempotents in the free inverse monoid generated by Γ, is investigated. It is shown that for every fixed monoid of this form the word problem can be solved in polynomial time which solves an open problem of Margolis and Meakin. For the uniform word problem, where the presentation is part of the input, EXPTIME-completeness is shown. For the Cayley-graphs of these monoids, it is shown that the first-order theory with regular path predicates is decidable. Regular path predicates allow to state that there is a path from a node

x

to a node

y

that is labeled with a word from some regular language. As a corollary, the decidability of the generalized word problem is deduced. Finally, it is shown that the Cayley-graph of the free inverse monoid has an undecidable monadic second-order theory.

Effective fractal dimension was defined by Lutz (2003) in order to quantitatively analyze the structure of complexity classes. Interesting connections of effective dimension with information theory were also found, in fact the cases of polynomial-space and constructive dimension can be precisely characterized in terms of Kolmogorov complexity, while analogous results for polynomial-time dimension haven’t been found.

In this paper we remedy the situation by using the natural concept of reversible time-bounded compression for finite strings. We completely characterize polynomial-time dimension in terms of polynomial-time compressors.

We compare the expressive power of two automata-based finite-state models of concurrency. We show that Droste’s and Kuske’s coherent stably concurrent automata and Bednarczyk’s forward-stable asynchronous systems describe the same class of regular event structures. This connection subsumes a previous study by Schmitt which relates Stark’s trace automata to asynchronous systems. This work relies on Zielonka’s theorem and some unrecognized result due to Arnold.

This paper addresses an algebraic problem which arises from our study on the information dynamics of cellular automata (CA). The state set of a cell is assumed to be a polynomial ring

Q

[

X

] modulo

X

q

–

X

over a finite field GF(

q

), where

X

is the indeterminate called the information variable. When a CA starts with an initial configuration containing a cell with state

X

, the information of

X

is transmitted to neighboring cells by cellular computation. In such a computation, every cell of a global configuration takes a polynomial in

Q

[

X

]. Generally denote such a configuration by

c

X

and let

G

cX

be the set of polynomials appearing in

c

X

. Our problem is to ask

how much information

of

X

is contained by

G

cX

. For

G

cX

we define the

degree of completenessλ

(

G

cX

) = log

q

|〈

G

cX

〉|, where 〈

G

cX

〉 is the subring of

Q

[

X

] generated by

G

cX

and investigate its relation to the

degree of degeneracym

(

c

X

) introduced before. We note here that

m

(

cX

) = 

q

 − |

V

(

G

cX

)|, where |

V

(

G

cX

)| is the cardinality of the value set of

G

cX

. Then, we prove that

λ

(

G

cX

) and in turn that

λ

(

G

cX

) + 

m

(

cX

) = 

q

. This result suggests that the computation of the size of subrings is reduced to that of the value size, which is executed much easier than subring generation.

Systems of language equations of the form {

ϕ

(

X

1

, ...,

X

n

) = ∅,

ψ

(

X

1

, ...,

X

n

)≠∅} are studied, where

ϕ

,

ψ

may contain set-theoretic operations and concatenation; they can be equivalently represented as strict inequalities

ξ

(

X

1

, ...,

X

n

) ⊂

L

0

. It is proved that the problem whether such an inequality has a solution is Σ

2

-complete, the problem whether it has a unique solution is in (Σ

3

∩ Π

3

) ∖ (Σ

2

∪ Π

2

), the existence of a regular solution is a Σ

1

-complete problem, while testing whether there are finitely many solutions is Σ

3

-complete. The class of languages representable by their unique solutions is exactly the class of recursive sets, though a decision procedure cannot be algorithmically constructed out of an inequality, even if a proof of solution uniqueness is attached.

In recent years the collective tokens philosophy for Petri Nets has gained again the stage, but it is commonly set in opposition to the individual tokens philosophy. In this paper we investigate what can be an adequate event structures to capture the collective tokens philosophy of nets when inhibitor arcs are taken into account.

The three domatic number problem asks whether a given undirected graph can be partitioned into at least three dominating sets, i.e., sets whose closed neighborhood equals the vertex set of the graph. Since this problem is NP-complete, no polynomial-time algorithm is known for it. The naive deterministic algorithm for this problem runs in time 3

n

, up to polynomial factors. In this paper, we design an exact deterministic algorithm for this problem running in time 2.9416

n

. Thus, our algorithm can handle problem instances of larger size than the naive algorithm in the same amount of time. We also present another deterministic and a randomized algorithm for this problem that both have an even better performance for graphs with small maximum degree.

Due to extensive research on tree-width for undirected graphs and due to its many applications in various fields it has been a natural desire for many years to generalize the idea of tree decomposition to directed graphs, but since many parameters in tree-width behave very differently in the world of digraphs, the generalization is still in its preliminary steps.

In this paper, after surveying the main work that has been done on this topic, we propose a new simple definition for directed tree-width and prove a special case of the min-max theorem (duality theorem) relating haven order, bramble number, and tree-width on digraphs. We also compare our definition with previous definitions and study the behavior of some tree-width like parameters such as brambles and havens on digraphs.

Let

β

be a real number with 1 <

β

< 2. We prove that the language of the

β

-shift is Δ

$^{\rm 0}_{n}$

iff

β

is a Δ

n

-real. The special case where

n

is 1 is the independently interesting result that the language of the

β

-shift is decidable iff

β

is a computable real. The “if” part of the proof is non-constructive; we show that for Walters’ version of the

β

-shift, no constructive proof exists.

The logic of equality and uninterpreted functions (EUF) has been proposed for processor verification. This paper presents a new data structure called Binary Decision Diagrams for representing EUF formulas (EUF-BDDs). We define EUF-BDDs similar to BDDs, but we allow equalities between terms as labels instead of Boolean variables. We provide an approach to build a reduced ordered EUF-BDD (EUF-ROBDD) and prove that every path to a leaf is satisfiable by construction. Moreover, EUF-ROBDDs are logically equivalent representations of EUF-formulae, so they can also be used to represent state spaces in symbolic model checking with data.

This paper deals with balanced leaf language complexity classes, introduced independently in [1] and [14]. We propose the seed concept for leaf languages, which allows us to give “short” representations for leaf words. We then use seeds to show that leaf languages

A

with

NP

 ⊆ 

BLeaf

P

(

A

) cannot be polylog-sparse (i.e.

census

A

∈

O

(log

O

(1)

)), unless

PH

collapses.

We also generalize balanced ≤

$^{P,{bit}}_{m}$

-reductions, which were introduced in [6], to other bit-reductions, for example (balanced) truth-table- and Turing-bit-reductions. Then, similarly to above, we prove that

NP

and Σ

$^{P}_{\rm 2}$

cannot have polylog-sparse hard sets under those balanced truth-table- and Turing-bit-reductions, if the polynomial-time hierarchy is infinite.

Given a set of strings

S

= {

s

1

,...,

s

n

}, the

Shortest Superstring

problem asks for the shortest string

s

which contains each

s

i

as a substring. We consider two measures of success in this problem: the

length

measure, which is the length of

s

, and the

compression

measure, which is the difference between the sum of lengths of the

s

i

and the length of

s

. Both the length and the compression versions of the problem are known to be MAX-SNP-hard. The only explicit approximation ratio lower bounds are by Ott: 1.000057 for the length measure and 1.000089 for the compression measure. Using a natural construction we improve these lower bounds to 1.00082 for the length measure and 1.00093 for the compression measure. Our lower bounds hold even for instances in which the strings are over a binary alphabet and have equal lengths. In fact, we show a somewhat surprising result, that the Shortest Superstring problem (with respect to both measures) is as hard to approximate on instances over a binary alphabet, as it is over any alphabet.

We study Boolean grammars. We introduce stratified semantics for Boolean grammars. We show, how to check, if a Boolean grammar generates a language according to this semantics. We show, that stratified semantics covers a class of important and natural languages. We introduce a recognition algorithm for Boolean grammars compliant to this semantics.