main-content

## Inhaltsverzeichnis

### A Core Calculus for Scala Type Checking

We present a minimal core calculus that captures interesting constructs of the Scala programming language: nested classes, abstract types, mixin composition, and path dependent types. We show that the problems of type assignment and subtyping in this calculus are decidable.

Vincent Cremet, François Garillot, Sergueï Lenglet, Martin Odersky

### Tree Exploration with an Oracle

We study the amount of knowledge about the network that is required in order to efficiently solve a task concerning this network. The impact of available information on the efficiency of solving network problems, such as communication or exploration, has been investigated before but assumptions concerned availability of

particular

items of information about the network, such as the size, the diameter, or a map of the network. In contrast, our approach is

quantitative

: we investigate the minimum number of bits of information (minimum oracle size) that has to be given to an algorithm in order to perform a task with given efficiency.

We illustrate this quantitative approach to available knowledge by the task of tree exploration. A mobile entity (robot) has to traverse all edges of an unknown tree, using as few edge traversals as possible. The quality of an exploration algorithm

${\cal A}$

is measured by its

competitive ratio

, i.e., by comparing its cost (number of edge traversals) to the length of the shortest path containing all edges of the tree. Depth-First-Search has competitive ratio 2 and, in the absence of any information about the tree, no algorithm can beat this value.

We determine the minimum number of bits of information that has to be given to an exploration algorithm in order to achieve competitive ratio strictly smaller than 2. Our main result establishes an exact threshold oracle size that turns out to be roughly loglog

D

, where

D

is the diameter of the tree. More precisely, for any constant

c

, we construct an exploration algorithm with competitive ratio smaller than 2, using an oracle of size at most loglog

D

c

, and we show that every algorithm using an oracle of size loglog

D

g

(

D

), for any function

g

unbounded from above, has competitive ratio at least 2.

Pierre Fraigniaud, David Ilcinkas, Andrzej Pelc

### Distributed Data Structures: A Survey on Informative Labeling Schemes

In this talk, we will survey the role of data structures for compactly storing and representing various types of information in a localized and distributed fashion. Traditional approaches to data representation are based on global data structures, which require access to the entire structure even if the sought information involves only a small and local set of entities. In contrast, localized data representation schemes are based on breaking the information into small local pieces, or

labels

, selected in a way that allows one to infer information regarding a small set of entities directly from their labels, without using any additional (global) information.

Cyril Gavoille

### From Deduction Graphs to Proof Nets: Boxes and Sharing in the Graphical Presentation of Deductions

Deduction graphs [3] provide a formalism for natural deduction, where the deductions have the structure of acyclic directed graphs with boxes. The boxes are used to restrict the scope of local assumptions. Proof nets for multiplicative exponential linear logic (MELL) are also graphs with boxes, but in MELL the boxes have the purpose of controlling the modal operator !. In this paper we study the apparent correspondences between deduction graphs and proof nets, both by looking at the structure of the proofs themselves and at the process of cut-elimination defined on them. We give two translations from deduction graphs for minimal proposition logic to proof nets: a direct one, and a mapping via so-called context nets. Context nets are closer to natural deduction than proof nets, as they have both premises (on top of the net) and conclusions (at the bottom). Although the two translations give basically the same results, the translation via context nets provides a more abstract view and has the advantage that it follows the same inductive construction as the deduction graphs. The translations behave nicely with respect to cut-elimination.

Herman Geuvers, Iris Loeb

### The Structure of Tractable Constraint Satisfaction Problems

We give a survey of recent results on the complexity of constraint satisfaction problems. Our main emphasis is on tractable structural restrictions.

Martin Grohe

### On the Representation of Kleene Algebras with Tests

We investigate conditions under which a given Kleene algebra with tests is isomorphic to an algebra of binary relations. Two simple separation properties are identified that, along with star-continuity, are sufficient for nonstandard relational representation. An algebraic condition is identified that is necessary and sufficient for the construction to produce a standard representation.

Dexter Kozen

### From Three Ideas in TCS to Three Applications in Bioinformatics

We will talk about three ideas from theoretical computer science that have actually been successfully used in real world applications in bioinformatics. From these ideas, we hope to inspire more theoretical research that are applicable to real world bioinformatics problems.

Ming Li

### Decompositions, Partitions, and Coverings with Convex Polygons and Pseudo-triangles

We propose a novel subdivision of the plane that consists of both convex polygons and pseudo-triangles. This

pseudo-convex

decomposition is significantly sparser than either convex decompositions or pseudo-triangulations for planar point sets and simple polygons. We also introduce pseudo-convex partitions and coverings. We establish some basic properties and give combinatorial bounds on their complexity. Our upper bounds depend on new Ramsey-type results concerning disjoint empty convex

k

-gons in point sets.

O. Aichholzer, C. Huemer, S. Kappes, B. Speckmann, C. D. Tóth

### Approximate Shortest Path Queries on Weighted Polyhedral Surfaces

We consider the classical geometric problem of determining shortest paths between pairs of points lying on a weighted polyhedral surface

P

consisting of

n

triangular faces. We present query algorithms that compute approximate distances and/or approximate (weighted) shortest paths. Our algorithm takes as input an approximation parameter

ε

∈(0,1) and a query time parameter

$\mathfrak{q}$

and builds a data structure which is then used for answering

ε

-approximate distance queries in

$O(\mathfrak{q})$

time. This algorithm is source point independent and improves significantly on the best previous solution. For the case where one of the query points is fixed we build a data structure that can answer

ε

-approximate distance queries to any query point in

P

in

$O(\log\frac{1}{\varepsilon})$

time. This is an improvement upon the previously known solution for the Euclidean fixed source query problem. Our algorithm also generalizes the setting from previously studied unweighted polyhedral to weighted polyhedral surfaces of arbitrary genus. Our solutions are based on a novel graph separator algorithm introduced here which extends and generalizes previously known separator algorithms.

Lyudmil Aleksandrov, Hristo N. Djidjev, Hua Guo, Anil Maheshwari, Doron Nussbaum, Jörg-Rüdiger Sack

### A Unified Construction of the Glushkov, Follow, and Antimirov Automata

A number of different techniques have been introduced in the last few decades to create

ε

-free automata representing regular expressions such as the

Glushkov automata

,

, or

Antimirov automata

. This paper presents a simple and unified view of all these construction methods both for unweighted and weighted regular expressions. It describes simpler algorithms with time complexities at least as favorable as that of the best previously known techniques, and provides a concise proof of their correctness. Our algorithms are all based on two standard automata operations: epsilon-removal and minimization. This contrasts with the multitude of complicated and special-purpose techniques previously described in the literature, and makes it straightforward to generalize these algorithms to the weighted case. In particular, we extend the definition and construction of follow automata to the case of weighted regular expressions over a closed semiring and present the first algorithm to compute weighted Antimirov automata.

Cyril Allauzen, Mehryar Mohri

### Algebraic Characterizations of Unitary Linear Quantum Cellular Automata

We provide algebraic criteria for the unitarity of linear quantum cellular automata, i.e. one dimensional quantum cellular automata. We derive these both by direct combinatorial arguments, and by adding constraints into the model which do not change the quantum cellular automata’s computational power. The configurations we consider have finite but unbounded size.

Pablo Arrighi

### A Polynomial Time Nilpotence Test for Galois Groups and Related Results

We give a deterministic polynomial-time algorithm to check whether the Galois group Gal(

f

) of an input polynomial

f

(

X

) ∈ ℚ[

X

] is nilpotent: the running time is polynomial in size(

f

). Also, we generalize the Landau-Miller solvability test to an algorithm that tests if Gal(

f

) is in Γ

d

: this algorithm runs in time polynomial in size(

f

) and

n

d

and, moreover, if Gal(

f

) ∈ Γ

d

it computes all the prime factors of # Gal(

f

).

V. Arvind, Piyush P Kurur

### The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems

Let

x

i

,...,

x

k

be

n

-bit numbers and

T

∈ ℕ. Assume that

P

1

,...,

P

k

are players such that

P

i

knows all of the numbers

exceptx

i

. They want to determine if

$\sum^{k}_{j=1}{\it x}_{j}$

=

T

by broadcasting as few bits as possible. In [7] an upper bound of

$O(\sqrt n )$

bits was obtained for the

k

=3 case, and a lower bound of

ω

(1) for

k

≥3 when

T

=Θ(2

n

). We obtain (1) for

k

≥3 an upper bound of

$k+O((n+\log k)^{1/(\lfloor{\rm lg(2k-2)}\rfloor)})$

, (2) for

k

=3,

T

=Θ(2

n

), a lower bound of Ω(loglog

n

), (3) a generalization of the protocol to abelian groups, (4) lower bounds on the multiparty communication complexity of some regular languages, and (5) empirical results for

k

= 3.

Richard Beigel, William Gasarch, James Glenn

### Crochemore Factorization of Sturmian and Other Infinite Words

The Crochemore factorization was introduced by Crochemore for the design of a linear time algorithm to detect squares in a word. We give here the explicit description of the Crochemore factorization for some classes of infinite words, namely characteristic Sturmian words, (generalized) Thue-Morse words, and the period doubling sequence.

Jean Berstel, Alessandra Savelli

### Equations on Partial Words

It is well known that some of the most basic properties of words, like the commutativity (

xy

=

yx

) and the conjugacy (

xz

=

zy

), can be expressed as solutions of word equations. An important problem is to decide whether or not a given equation on words has a solution. For instance, the equation

x

m

y

n

=

z

p

has only periodic solutions in a free monoid, that is, if

x

m

y

n

=

z

p

holds with integers

m

,

n

,

p

≥2, then there exists a word

w

such that

x

,

y

,

z

are powers of

w

. This result, which received a lot of attention, was first proved by Lyndon and Schützenberger for free groups. In this paper, we investigate equations on

partial words

. Partial words are sequences over a finite alphabet that may contain a number of “do not know” symbols. When we speak about equations on partial words, we replace the notion of equality (=) with compatibility ( ↑ ). Among other equations, we solve

xy

yx

,

xz

zy

, and special cases of

x

m

y

n

z

p

for integers

m

,

n

,

p

≥2. ...

F. Blanchet-Sadri, D. Dakota Blair, Rebeca V. Lewis

### Concrete Multiplicative Complexity of Symmetric Functions

The multiplicative complexity of a Boolean function

f

is defined as the minimum number of binary conjunction (AND) gates required to construct a circuit representing

f

, when only exclusive-or, conjunction and negation gates may be used. This article explores in detail the multiplicative complexity of symmetric Boolean functions. New techniques that allow such exploration are introduced. They are powerful enough to give exact multiplicative complexities for several classes of symmetric functions. In particular, the multiplicative complexity of computing the Hamming weight of

n

bits is shown to be exactly

n

−

H

(

n

), where

H

(

n

) is the Hamming weight of the binary representation of

n

. We also show a close relationship between the complexity of symmetric functions and fractals derived from the parity of binomial coefficients.

Joan Boyar, René Peralta

### On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures

We study the notion of limit sets of cellular automata associated with probability measures (

μ

-limit sets). This notion was introduced by P. Kůrka and A. Maass in [1]. It is a refinement of the classical notion of

ω

-limit sets dealing with the typical long term behavior of cellular automata. It focuses on the words whose probability of appearance does not tend to 0 as time tends to infinity (the persistent words). In this paper, we give a characterization of the persistent language for non sensitive cellular automata associated with Bernoulli measures. We also study the computational complexity of these languages. We show that the persistent language can be non-recursive. But our main result is that the set of quasi-nilpotent cellular automata (those with a single configuration in their

μ

-limit set) is neither recursively enumerable nor co-recursively enumerable.

Laurent Boyer, Victor Poupet, Guillaume Theyssier

### Coloring Random 3-Colorable Graphs with Non-uniform Edge Probabilities

Random 3-colorable graphs that are generated according to a

G

(

n

,

p

)-like model can be colored optimally, if

p

c

/

n

for some large constant

c

. However, these methods fail in a model where the edge-probabilities are non-uniform and not bounded away from zero. We present a spectral algorithm that succeeds in such situations.

Ulrik Brandes, Jürgen Lerner

### The Kleene Equality for Graphs

In order to generalize the Kleene theorem from the free monoid to richer algebraic structures, we consider the non deterministic acceptance by a finite automaton of subsets of vertices of a graph. The subsets accepted in such a way are the equational subsets of vertices of the graph in the sense of Mezei and Wright. We introduce the notion of deterministic acceptance by finite automaton. A graph satisfies the Kleene equality if the two acceptance modes are equivalent, and in this case, the equational subsets form a Boolean algebra. We establish that the infinite grid and the transition graphs of deterministic pushdown automata satisfy the Kleene equality and we present families of graphs in which the free product of graphs preserves the Kleene equality.

Arnaud Carayol, Didier Caucal

### On the Repetition Threshold for Large Alphabets

The (maximal) exponent of a finite non-empty word is the ratio among its length and its period. Dejean (1972) conjectured that for any

n

≥5 there exists an infinite word over

n

letters with no factor of exponent larger than

n

/(

n

–1). We prove that this conjecture is true for

n

≥38.

Arturo Carpi

### Improved Parameterized Upper Bounds for Vertex Cover

This paper presents an

O

(1.2738

k

+

kn

)-time polynomial-space parameterized algorithm for

Vertex Cover

improving the previous

O

(1.286

k

+

kn

)-time polynomial-space upper bound by Chen, Kanj, and Jia. The algorithm also improves the

O

(1.2745

k

k

4

+

kn

)-time exponential-space upper bound for the problem by Chandran and Grandoni.

Jianer Chen, Iyad A. Kanj, Ge Xia

### On Comparing Sums of Square Roots of Small Integers

Let

k

and

n

be positive integers,

n

>

k

. Define

r

(

n

,

k

) to be the minimum positive value of

$|\sqrt{a_1} + \cdots + \sqrt{a_k} -- \sqrt{b_1} -- \cdots -\sqrt{b_k} |$

where

a

1

,

a

2

, ⋯,

a

k

,

b

1

,

b

2

, ⋯,

b

k

are positive integers no larger than

n

. It is an important problem in computational geometry to determine a good upper bound of –log

r

(

n

,

k

). In this paper we prove an upper bound of 2

$^{O({\it n}/log{\it n})}$

, which is better than the best known result

O

(2

2

k

log

n

) whenever

n

ck

log

k

for some constant

c

. In particular, our result implies an algorithm

subexponential

in

k

(i.e. with time complexity 2

$^{o({\it k})}$

(log

n

)

O

(1)

) to compare two sums of square roots of integers of value

o

(

k

log

k

).

Qi Cheng

### A Combinatorial Approach to Collapsing Words

Given a word

w

over a finite alphabet Σ and a finite deterministic automaton

${\mathcal A} = {\langle} Q,\Sigma,\delta {\rangle}$

, the inequality |

δ

(

Q

,

w

)| ≤|

Q

|–

n

means that under the natural action of the word

w

the image of the state set

Q

is reduced by at least

n

states. The word

w

is

n

-collapsing if this inequality holds for any deterministic finite automaton that satisfies such an inequality for at least one word. In this paper we present a new approach to the topic of collapsing words, and announce a few results we have obtained using this new approach. In particular, we present a direct proof of the fact that the language of

n

-collapsing words is recursive.

A. Cherubini, P. Gawrychowski, A. Kisielewicz, B. Piochi

### Optimal Linear Arrangement of Interval Graphs

We study the optimal linear arrangement (OLA) problem on interval graphs. Several linear layout problems that are NP-hard on general graphs are solvable in polynomial time on interval graphs. We prove that, quite surprisingly, optimal linear arrangement of interval graphs is NP-hard. The same result holds for permutation graphs. We present a lower bound and a simple and fast 2-approximation algorithm based on any interval model of the input graph.

Johanne Cohen, Fedor Fomin, Pinar Heggernes, Dieter Kratsch, Gregory Kucherov

### The Lempel-Ziv Complexity of Fixed Points of Morphisms

The Lempel–Ziv complexity is a fundamental measure of complexity for words, closely connected with the famous LZ77, LZ78 compression algorithms. We investigate this complexity measure for one of the most important families of infinite words in combinatorics, namely the fixed points of morphisms. We give a complete characterisation of the complexity classes which are Θ(1), Θ(log

n

), and Θ(

n

$^{\rm 1/{\it k}}$

),

k

∈ ℕ,

k

≥2, depending on the periodicity of the word and the growth function of the morphism. The relation with the well-known classification of Ehrenfeucht, Lee, Rozenberg, and Pansiot for factor complexity classes is also investigated. The two measures complete each other, giving an improved picture for the complexity of these infinite words.

Sorin Constantinescu, Lucian Ilie

### Partially Commutative Inverse Monoids

Free partially commutative inverse monoids are investigated. Analogously to free partially commutative monoids (trace monoids), free partially commutative inverse monoid are the quotients of free inverse monoids modulo a partially defined commutation relation on the generators. An

O

(

n

log(

n

)) algorithm on a RAM for the word problem is presented, and

NP

-completeness of the generalized word problem and the membership problem for rational sets is shown. Moreover, free partially commutative inverse monoids modulo a finite idempotent presentation are studied. For these monoids, the word problem is decidable if and only if the complement of the commutation relation is transitive.

Volker Diekert, Markus Lohrey, Alexander Miller

### Learning Bayesian Networks Does Not Have to Be NP-Hard

We propose an algorithm for learning an optimal Bayesian network from data. Our method is addressed to biological applications, where usually datasets are small but sets of random variables are large. Moreover we assume that there is no need to examine the acyclicity of the graph.

We provide polynomial bounds (with respect to the number of random variables) for time complexity of our algorithm for two generally used scoring criteria: Minimal Description Length and Bayesian-Dirichlet equivalence.

Norbert Dojer

### Lower Bounds for the Transition Complexity of NFAs

(Extended Abstract)

We construct regular languages

L

n

,

n

≥1, such that any NFA recognizing

L

n

needs

$\Omega( {\rm nsc}(L_n) \cdot \sqrt{{\rm nsc}(L_n)})$

transitions where nsc(

L

n

) is the nondeterministic state complexity of

L

n

. Also, we study trade-offs between the number of states and the number of transitions of an NFA. We show that adding one additional state can result in significant reductions in the number of transitions and that there exist regular languages

L

n

,

n

≥2, where the transition minimal NFA for

L

n

has more than

c

nsc(

L

n

) states, for some constant

c

> 1.

Michael Domaratzki, Kai Salomaa

### Smart Robot Teams Exploring Sparse Trees

We consider a tree which has to be completely explored by a group of

k

robots, initially placed at the root. The robots are mobile and can communicate using radio devices, but the communication range is bounded. They decide based on local, partial knowledge, and exchange information gathered during the exploration. There is no central authority which knows the graph and could control the movements of the robots – they have to organize themselves and jointly explore the tree.

The problem is that at every point of time the remaining unknown part of the tree may appear to be the worst case setting for the current deployment of robots. We present a deterministic distributed algorithm to explore

T

and we use a parameter of a tree called

density

. We compare the performance of our algorithm with the optimal algorithm having a-priori knowledge of the same tree. We show that the above ratio is influenced only by the density and the height of the tree. Since the competitive ratio does not depend on the number of robots, our algorithm truly emphasizes the phenomena of self-organization. The more robots are provided, the faster the exploration of the terrain is completed.

M. Dynia, J. Kutyłowski, F. Meyer auf der Heide, C. Schindelhauer

### k-Sets of Convex Inclusion Chains of Planar Point Sets

Given a set

V

of

n

points in the plane, we introduce a new number of

k

-sets that is an invariant of

V

: the number of

k

-sets of a convex inclusion chain of

V

. A convex inclusion chain of

V

is an ordering (

v

1

,

v

2

, ...,

v

n

) of the points of

V

such that no point of the ordering belongs to the convex hull of its predecessors. The

k

-sets of such a chain are then the distinct

k

-sets of all the subsets {

v

1

, ...,

v

i

}, for all

i

in {

k

+1, ...,

n

}. We show that the number of these

k

-sets depends only on

V

and not on the chosen convex inclusion chain. Moreover, this number is surprisingly equal to the number of regions of the order-

k

Voronoi diagram of

V

. As an application, we give an efficient on-line algorithm to compute the

k

-sets of the vertices of a simple polygonal line, no vertex of which belonging to the convex hull of its predecessors on the line.

Wael El Oraiby, Dominique Schmitt

### Toward the Eigenvalue Power Law

Many graphs arising in various real world networks exhibit the so called “power law” behavior, i.e., the number of vertices of degree

i

is proportional to

i

− β

, where

β

> 2 is a constant (for most real world networks

β

≤ 3). Recently, Faloutsos et al. [18] conjectured a power law distribution for the eigenvalues of power law graphs. In this paper, we show that the eigenvalues of the Laplacian of certain random power law graphs are close to a power law distribution.

First we consider the generalized random graph model

G

(

d

) =(

V

,

E

), where

d

=(

d

1

, ...,

d

n

) is a given sequence of expected degrees, and two nodes

v

i

,

v

j

V

share an edge in

G

(

d

) with probability

p

i

,

j

=

d

i

d

j

/

$\sum^{n}_{k=1}$

d

k

, independently [9]. We show that if the degree sequence

d

follows a power law distribution, then some largest Θ(

n

1/β

) eigenvalues of

L

(

d

) are distributed according to the same power law, where

L

(

d

) represents the Laplacian of

G

(

d

). Furthermore, we determine for the case

β

∈(2,3) the number of Laplacian eigenvalues being larger than

i

, for any

i

=

ω

(1), and compute how many of them are in some range (

i

,(1+

ε

)

i

), where

i

=

ω

(1) and

ε

>0 is a constant. Please note that the previously described results are guaranteed with probability 1–

o

(1/

n

).

We also analyze the eigenvalues of the Laplacian of certain dynamically constructed power law graphs defined in [2,3], and discuss the applicability of our methods in these graphs.

Robert Elsässer

### Multicast Transmissions in Non-cooperative Networks with a Limited Number of Selfish Moves

We study a multicast game in communication networks in which a source sends the same message or service to a set of destinations and the cost of the used links is divided among the receivers according to given cost sharing methods. Assuming a selfish and rational behavior, each receiving user is willing to select a strategy yielding the minimum shared cost. A Nash equilibrium is a solution in which no user can decrease its payment by adopting a different strategy, and the price of anarchy is defined as the worst case ratio between the overall communication cost yielded by an equilibrium and the minimum possible one. Nash equilibria requiring an excessive number of steps to be reached or being hard to compute or not existing at all, we are interested in the determination of the price of anarchy reached in a limited number of rounds, each of which containing at least one move per receiving user. We consider different reasonable cost sharing methods, including the well-known Shapley and egalitarian ones, and investigate their performances versus two possible global criteria: the overall cost of the used links and the maximum shared cost of users. We show that, even in case of two receivers making the best possible move at each step, the number of steps needed to reach a Nash equilibrium can be arbitrarily large. Moreover, we determine the cost sharing methods for which a single round is already sufficient to get a price of anarchy comparable to the one at equilibria, and the ones not satisfying such a property. Finally, we show that finding the sequence of moves leading to the best possible global performance after one-round is already an intractable problem, i.e., NP-hard.

Angelo Fanelli, Michele Flammini, Giovanna Melideo, Luca Moscardelli

### Very Sparse Leaf Languages

Unger studied the balanced leaf languages defined via poly-logarithmically sparse leaf pattern sets. Unger shows that NP-complete sets are not polynomial-time many-one reducible to such balanced leaf language unless the polynomial hierarchy collapses to Θ

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

and that Σ

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

-complete sets are not polynomial-time bounded-truth-table reducible (respectively), polynomial-time Turing reducible) to any such balanced leaf language unless the polynomial hierarchy collapses to Δ

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

(respectively, Σ

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

).

This paper studies the complexity of the class of such balanced leaf languages, which will be denoted by VSLL. In particular, the following tight upper and lower bounds of VSLL are shown:

1. coNP ⊆ VSLL ⊆ coNP/poly (the former inclusion is already shown by Unger).

2. coNP/1

$\not\subseteq$

VSLL unless PH = Θ

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

.

3. For all constant

c

>0, VSLL

$\not\subseteq$

coNP/

n

c

.

4. P/(loglog(

n

) +

O

(1)) ⊆ VSLL.

5. For all

h

(

n

) = loglog(

n

) +

ω

(1), P

$/h \not\subseteq$

VSLL.

Lance Fortnow, Mitsunori Ogihara

### On the Correlation Between Parity and Modular Polynomials

We consider the problem of bounding the correlation between parity and modular polynomials over ℤ

q

, for arbitrary odd integer

q

≥3. We prove exponentially small upper bounds for classes of polynomials with certain linear algebraic properties. As a corollary, we obtain exponential lower bounds on the size necessary to compute parity by depth-3 circuits of certain form. Our technique is based on a new representation of the correlation using exponential sums.

Our results include Goldmann’s result [Go] on the correlation between parity and degree one polynomials as a special case. Our general expression for representing correlation can be used to derive the bounds of Cai, Green, and Thierauf [CGT] for symmetric polynomials, using ideas of the [CGT] proof. The classes of polynomials for which we obtain exponentially small upper bounds include polynomials of large degree and with a large number of terms, that previous techniques did not apply to.

### Optimally Fast Data Gathering in Sensor Networks

Efficient data gathering in sensor network is an important challenge. In this paper we address the problem of gathering sensed data to the sink of a sensor network minimizing the time to complete the process. We present optimal time data gathering algorithms for any type of topology of a sensor network. Our results improve on existing approximation algorithms. We approach the gathering problem by obtaining optimal solutions to the collision-free paths coloring problem.

### Magic Numbers in the State Hierarchy of Finite Automata

A number

d

is magic for

n

, if there is no regular language for which an optimal nondeterministic finite state automaton (nfa) uses exactly

n

states, but for which the optimal deterministic finite state automaton (dfa) uses exactly

d

states. We show that, in the case of unary regular languages, the state hierarchy of dfa’s, for the family of languages accepted by

n

-state nfa’s, is not contiguous. There are some “holes” in the hierarchy, i.e., magic numbers in between values that are not magic. This solves, for automata with a single letter input alphabet, an open problem of existence of magic numbers [7].

As an additional bonus, we get a universal lower bound for the conversion of unary

d

-state dfa’s into equivalent nfa’s: nondeterminism does not reduce the number of states below log

2

d

, not even in the best case.

Viliam Geffert

### Online Single Machine Batch Scheduling

We are concerned with the problem of safely storing a history of actions that happen rapidly in real time, such as in “buy” and “sell” orders in stock exchange trading. This leads to a single-family scheduling problem with batching on a single machine, with a setup time and job release times, under batch availability. We investigate the objective of minimizing the total flow time in an online setting. On the positive side, we propose a 2-competitive algorithm for the case of identical job processing times, and we prove a lower bound that comes close. With general processing times, our lower bound shows that online algorithms are inevitably bad in the worst case.

Beat Gfeller, Leon Peeters, Birgitta Weber, Peter Widmayer

### Machines that Can Output Empty Words

We propose the e-model for leaf languages which generalizes the known balanced and unbalanced concepts. Inspired by the neutral behavior of rejecting paths of NP machines, we allow transducers to output empty words. The paper explains several advantages of the new model. A central aspect is that it allows us to prove strong gap theorems: For any class

${\cal C}$

that is definable in the e-model, either

$\mathrm{coUP} \subseteq {\cal C}$

or

${{\cal C} \subseteq \mathrm{NP}}$

. For the existing models, gap theorems, where they exist at all, only identify gaps for the definability by

regular

languages. We prove gaps for the general case, i.e., for the definability by

arbitrary

languages. We obtain such general gaps for NP, coNP, 1NP, and co1NP. For the regular case we prove further gap theorems for Σ

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

, Π

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

, and Δ

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

. These are the first gap theorems for Δ

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

.

Christian Glaßer, Stephen Travers

### Completeness of Global Evaluation Logic

Monads serve the abstract encapsulation of side effects in semantics and functional programming. Various monad-based specification languages have been introduced in order to express requirements on generic side-effecting programs. A basic role is played here by global evaluation logic, concerned with formulae which may be thought of as being universally quantified over the state space; this formalism is the fundament of more advanced logics such as monad-based Hoare logic or dynamic logic. We prove completeness of global evaluation logic for models in cartesian categories with a distinguished Heyting algebra object.

Sergey Goncharov, Lutz Schröder, Till Mossakowski

### NOF-Multiparty Information Complexity Bounds for Pointer Jumping

We prove a lower bound on the communication complexity of pointer jumping for multiparty one-way protocols in the number on the forehead model that satisfy a certain information theoretical restriction: We consider protocols for which the

i

th player may only reveal information about the first

i

+1 inputs. To this end we extend the information complexity approach of Chakrabarti, Shi, Wirth, and Yao (2001) and Bar-Yossef, Jayram, Kumar, and Sivakumar (2004) to our restricted version of the multiparty number on the forehead model. The best currently known multiparty protocol for pointer jumping by Damm, Jukna, and Sgall (1998) works in this model.

Andre Gronemeier

### Dimension Characterizations of Complexity Classes

We use derandomization to show that sequences of positive pspace-dimension – in fact, even positive Δ

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

-dimension for suitable

k

– have, for many purposes, the full power of random oracles. For example, we show that, if

S

is any binary sequence whose Δ

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

-dimension is positive, then BPP ⊆ P

S

and, moreover, every BPP promise problem is P

S

-separable. We prove analogous results at higher levels of the polynomial-time hierarchy.

The

dimension-almost-class

of a complexity class

$\mathcal{C}$

, denoted by dimalmost-

$\mathcal{C}$

, is the class consisting of all problems

A

such that

$A \in \mathcal{C}^S$

for all but a Hausdorff dimension 0 set of oracles

S

. Our results yield several characterizations of complexity classes, such as BPP = dimalmost-P and AM = dimalmost-NP, that refine previously known results on almost-classes. They also yield results, such as Promise-BPP = almost-P-Sep = dimalmost-P-Sep, in which even the almost-class appears to be a new characterization.

Xiaoyang Gu, Jack H. Lutz

### Approximation Algorithms and Hardness Results for Labeled Connectivity Problems

Let

G

= (

V

,

E

) be a connected multigraph, whose edges are associated with labels specified by an integer-valued function

${\mathcal{L}} : E \rightarrow \mathbb{N}$

. In addition, each label ℓ ∈ ℕ to which at least one edge is mapped has a non-negative cost

c

( ℓ). The

minimum label spanning tree

problem (MinLST) asks to find a spanning tree in

G

that minimizes the overall cost of the labels used by its edges. Equivalently, we aim at finding a minimum cost subset of labels

I

⊆ ℕ such that the edge set

$\{ e \in E : {\mathcal {L}}( e ) \in I \}$

forms a connected subgraph spanning all vertices. Similarly, in the

minimum label s

-t

path

problem (MinLP) the goal is to identify an

s

-

t

path minimizing the combined cost of its labels, where

s

and

t

are provided as part of the input.

The main contributions of this paper are improved approximation algorithms and hardness results for MinLST and MinLP. As a secondary objective, we make a concentrated effort to relate the algorithmic methods utilized in approximating these problems to a number of well-known techniques, originally studied in the context of integer covering.

Refael Hassin, Jérôme Monnot, Danny Segev

### An Expressive Temporal Logic for Real Time

We add to the standard temporal logic with the modalities ”Until” and ”Since”, a sequence of “counting modalities”: For each

n

the modality

C

n

(

X

), which says that

X

will be true at least at

n

points in the next unit of time, and its past counterpart

${\overleftarrow{C}_n}$

, which says that

X

has happened at least

n

times in the last unit of time. We prove that this temporal logic is as expressive as can be hoped for; all the modalities that can be expressed in a strong natural decidable predicate logic framework, are expressible in this temporal logic.

Yoram Hirshfeld, Alexander Rabinovich

### On Matroid Representability and Minor Problems

In this paper we look at complexity aspects of the following problem (matroid representability) which seems to play an important role in structural matroid theory: Given a rational matrix representing the matroid

M

, the question is whether

M

can be represented also over another specific finite field. We prove this problem is hard, and so is the related problem of minor testing in rational matroids. The results hold even if we restrict to matroids of branch-width three.

Petr Hliněný

### Non-cooperative Tree Creation

Extended Abstract

In this paper we consider the

connection game

, a simple network design game with independent selfish agents that was introduced by Anshelevich et al [4]. In addition we present a generalization called

backbone game

to model hierarchical network and backbone link creation between existing network structures. In contrast to the connection game each player considers a number of groups of terminals and wants to connect at least one terminal from each group into a network. In both games we focus on an important subclass of

tree games

, in which every feasible network is guaranteed to be connected.

For tree connection games, in which every player holds 2 terminals, we show that there is a Nash equilibrium as cheap as the optimum network. We give a polynomial time algorithm to find a cheap (2+

ε

)-approximate Nash equilibrium, which can be generalized to a cheap (3.1+

ε

)-approximate Nash equilibrium for the case of any number of terminals per player. This improves the guarantee of the only previous algorithm for the problem [4], which returns a (4.65+

ε

)-approximate Nash equilibrium. Tightness results for the analysis of all algorithms are derived.

For single source backbone games, in which each player wants to connect one group to a common source, there is a Nash equilibrium as cheap as the optimum network and a polynomial time algorithm to find a cheap (1+

ε

)-approximate Nash equilibrium.

Martin Hoefer

### Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners

Dodgson’s election system elegantly satisfies the Condorcet criterion. However, determining the winner of a Dodgson election is known to be

${\mathrm{\Theta}^{\mathit{p}}_2}$

-complete ([1], see also [2]), which implies that unless P = NP no polynomial-time solution to this problem exists, and unless the polynomial hierarchy collapses to NP the problem is not even in NP. Nonetheless, we prove that when the number of voters is much greater than the number of candidates (although the number of voters may still be polynomial in the number of candidates), a simple greedy algorithm very frequently finds the Dodgson winners in such a way that it “knows” that it has found them, and furthermore the algorithm never incorrectly declares a nonwinner to be a winner.

Christopher M. Homan, Lane A. Hemaspaandra

### Reductions for Monotone Boolean Circuits

The large class, say

NLOG

, of Boolean functions, including 0-1 Sort and 0-1 Merge, have an upper bound of

O

(

n

log

n

) for their monotone circuit size, i.e., have circuits with

O

(

n

log

n

) AND/OR gates of fan-in two. Suppose that we can use, besides such normal AND/OR gates, any number of more powerful “

F

-gates” which realize a monotone Boolean function

F

with

r

(≥2) inputs and

r

′ (≥1) outputs. Note that the cost of each AND/OR gate is one and we assume that the cost of each

F

-gate is

r

. Now we define: A Boolean function

f

in NLOG is said to be

F

-Easy if

f

can be constructed by a circuit with AND/OR/

F

gates whose total cost is

o

(

n

log

n

). In this paper we show that 0-1 Merge is not

F

-Easy for an arbitrary monotone function

F

such that

r

′ ≤

r

/log

r

.

Kazuo Iwama, Hiroki Morizumi

### Generalised Integer Programming Based on Logically Defined Relations

Many combinatorial optimisation problems can be modelled as integer linear programs. We consider a class of generalised integer programs where the constraints are allowed to be taken from a broader set of relations (instead of just being linear inequalities). The set of allowed relations is defined using a many-valued logic and the resulting class of relations have provably strong modelling properties. We give sufficient conditions for when such problems are polynomial-time solvable and we prove that they are

APX

-hard otherwise.

Peter Jonsson, Gustav Nordh

### Probabilistic Length-Reducing Automata

Hardness of a separation of nondeterminism, randomization and determinism for polynomial time computations motivates the analysis of restricted models of computation. Following this line of research, we consider randomized length-reducing two-pushdown automata (

lrTPDA

), a natural extension of pushdown automata (

PDA

). We separate randomized

lrTPDA

s from deterministic and nondeterministic ones, and we compare different modes of randomization. Moreover, we prove that amplification is impossible for Las Vegas automata.

Tomasz Jurdziński

### Sorting Long Sequences in a Single Hop Radio Network

We propose an algorithm for merging two sorted sequences of length

k

m

stored in two sequences of

m

stations of single-hop single-channel radio network, where each station stores a block of of

k

consecutive elements. The time and energetic cost of this algorithm are 6

m

k

+8

m

–4 and 8

k

+4⌈log

2

(

m

+1)⌉+6, respectively. This algorithm can be applied for sorting a sequence of length

N

=

k

n

in a network consisting of

n

stations with memory limited by Θ(

k

) words. For

$k=\Omega(\lg n)$

, the energetic cost of such sorting is

$O(k\cdot\lg n)$

and the time is

$O(N\lg n)$

. Moreover, the constants hidden by the big “Oh” are reasonably small, to make the algorithm attractive for practical applications.

Marcin Kik

### Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture

We study the complexity of counting the number of solutions to a system of equations over a fixed finite semigroup. We show that this problem is always either in FP or #P-complete and describe the borderline precisely. We use these results to convey some intuition about the conjectured dichotomy for the complexity of counting the number of solutions in constraint satisfaction problems.

Ondřej Klíma, Benoît Larose, Pascal Tesson

### Valiant’s Model: From Exponential Sums to Exponential Products

We study the power of big products for computing multivariate polynomials in a Valiant-like framework. More precisely, we define a new class

V

ΠP

0

as the set of families of polynomials that are exponential products of easily computable polynomials. We investigate the consequences of the hypothesis that these big products are themselves easily computable. For instance, this hypothesis would imply that the nonuniform versions of P and NP coincide. Our main result relates this hypothesis to Blum, Shub and Smale’s algebraic version of P versus NP. Let

K

be a field of characteristic 0. Roughly speaking, we show that in order to separate P

K

from NP

K

using a problem from a fairly large class of “simple” problems, one should first be able to show that exponential products are not easily computable. The class of “simple” problems under consideration is the class of NP problems in the structure (

K

,+,–,=), in which multiplication is not allowed.

Pascal Koiran, Sylvain Perifel

### A Reachability Algorithm for General Petri Nets Based on Transition Invariants

A new reachability algorithm for general Petri nets is proposed. Given a Petri net with an initial and a target markings, a so called complemented Petri net is created first that consists of the given Petri net and an additional, complementary transition. Thereby, the reachability task is reduced to calculation and investigation of transition invariants (T-invariants) of the complemented Petri net. The algorithm finds all minimal-support T-invariants of the complemented Petri net and then calculates a finite set of linear combinations of minimal-support T-invariants, in which the complementary transition fires only once. Finally, for each T-invariant with a single firing of the complementary transition, the algorithm tries to create a reachability path from initial to target marking or determines that there is no such path.

Alexander E. Kostin

### Approximability of Bounded Occurrence Max Ones

We study the approximability of

Max Ones

when the number of variable occurrences is bounded by a constant. For conservative constraint languages (i.e., when the unary relations are included) we give a complete classification when the number of occurrences is three or more and a partial classification when the bound is two. For the non-conservative case we prove that it is either trivial or equivalent to the corresponding conservative problem under polynomial-time many-one reductions.

Fredrik Kuivinen

### Fast Iterative Arrays with Restricted Inter-cell Communication: Constructions and Decidability

Iterative arrays (IAs) are one-dimensional arrays of interconnected interacting finite automata with sequential input mode. We investigate IAs which work in real time and whose inter-cell communication is bounded by some constant number of bits not depending on the number of states. It is known [13] that such IAs can recognize rather complicated unary languages with a minimum amount of communication, namely one-bit communication, in real time. Some examples are the languages

$\{a^{2^n} \mid n \ge 1\}$

,

$\{a^{n^2} \mid n \ge 1\}$

, and {

a

p

|

p

is prime}. Here, we consider non-unary languages and it turns out that the non-unary case is quite different. We present several real-time constructions for certain non-unary languages. For example, the languages {

a

n

b

n

|

n

≥1}, {

a

n

(

b

n

)

m

|

n

,

m

≥1}, and {

a

n

ba

m

b

(

ba

)

n

.

m

|

n

,

m

≥1} are recognized in real time by 1-bit IAs. Moreover, it is shown that real-time 1-bit IAs can, in some sense, add and multiply integer numbers. Furthermore, closure properties and decidability questions of communication restricted IAs are investigated. Due to the constructions provided, non-closure results as well as undecidability results can be shown. It turns out that emptiness is still undecidable for 1-bit IAs despite their restricted communication. Thus, also the questions of finiteness, infiniteness, inclusion, and equivalence are undecidable.

Martin Kutrib, Andreas Malcher

### Faster Algorithm for Bisimulation Equivalence of Normed Context-Free Processes

The fastest known algorithm for checking bisimulation equivalence of normed context-free processes worked in

O

(

n

13

) time. We give an alternative algorithm working in

$O(n^8 {\sl polylog} n)$

time, As a side effect we improve the best known upper bound for testing equivalence of simple context-free grammars from

$O(n^7 {\sl polylog} n)$

to

$O(n^6 {\sl polylog} n)$

.

Sławomir Lasota, Wojciech Rytter

### Quantum Weakly Nondeterministic Communication Complexity

In this paper we study a weak version of quantum nondeterministic communication complexity, corresponding to the most natural generalization of classical nondeterminism, in which a classical proof has to be checked with probability one by a quantum protocol. We prove that, in the framework of communication complexity, even the weak version of quantum nondeterminism is strictly stronger than classical nondeterminism. More precisely, we show the first separation, for a total function, of quantum weakly nondeterministic and classical nondeterministic communication complexity. This separation is quadratic and shows that classical proofs can be checked more efficiently by quantum protocols than by classical ones.

François Le Gall

### Minimal Chordal Sense of Direction and Circulant Graphs

A sense of direction is an edge labeling on graphs that follows a globally consistent scheme and is known to considerably reduce the complexity of several distributed problems. In this paper we study a particular instance of sense of direction, called a chordal sense of direction (CSD). In special, we analyze the class of

k

-regular graphs that admit a CSD with exactly

k

labels (a minimal CSD). We prove that connected graphs in this class are Hamiltonian and that the class is equivalent to that of circulant graphs, presenting an efficient (polynomial-time) way of recognizing it when the graphs’ degree

k

is fixed.

Rodrigo S. C. Leão, Valmir C. Barbosa

### Querying and Embedding Compressed Texts

The computational complexity of two simple string problems on compressed input strings is considered: the querying problem (What is the symbol at a given position in a given input string?) and the embedding problem (Can the first input string be embedded into the second input string?). Straight-line programs are used for text compression. It is shown that the querying problem becomes P-complete for compressed strings, while the embedding problem becomes hard for the complexity class

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

.

Yury Lifshits, Markus Lohrey

### Lempel-Ziv Dimension for Lempel-Ziv Compression

This paper describes the Lempel-Ziv dimension (Hausdorff like dimension inspired in the LZ78 parsing), its fundamental properties and relation with Hausdorff dimension. It is shown that in the case of individual infinite sequences, the Lempel-Ziv dimension matches with the asymptotical Lempel-Ziv compression ratio. This fact is used to describe results on Lempel-Ziv compression in terms of dimension of complexity classes and vice versa.

Maria Lopez-Valdes

### Characterizing Valiant’s Algebraic Complexity Classes

Valiant introduced 20 years ago a theory to study the complexity of polynomial families. Using arithmetic circuits as computation model, these classes are easy to define and open to combinatorial techniques. In this paper we gather old and new results under a unifying theme, namely the restrictions imposed upon the gates, building a hierarchy from formulas to circuits. As a consequence we get simpler proofs for known results such as the equality of the classes VNP and VNP

e

or the completeness of the determinant for VQP, and new results such as a characterization of the class VP or answers to both a conjecture and a problem raised by Bürgisser [1]. We also show that for circuits of polynomial depth and unbounded size these models have the same expressive power and characterize a uniform version of VNP.

Guillaume Malod, Natacha Portier

### The Price of Defense

We consider a

strategic game

with two classes of confronting randomized players on a graph

G

(

V

,

E

):

ν

attackers

, each choosing vertices and wishing to minimize the probability of being caught, and a

defender

, who chooses edges and gains the expected number of attackers it catches. The

Price of Defense

is the worst-case ratio, over all Nash equilibria, of the

optimal

gain of the defender over its gain at a Nash equilibrium. We provide a comprehensive collection of trade-offs between the Price of Defense and the computational efficiency of Nash equilibria.

– Through reduction to a

Two-Players, Constant-Sum Game

, we prove that a Nash equilibrium can be computed in polynomial time. The reduction does not provide any apparent guarantees on the Price of Defense.

– To obtain such, we analyze several structured Nash equilibria:

– In a

Matching Nash equilibrium

, the support of the defender is an

Edge Cover

. We prove that they can be computed in polynomial time, and they incur a Price of Defense of

α

(

G

), the

Independence Number

of

G

.

– In a

Perfect Matching Nash equilibrium

, the support of the defender is a

Perfect Matching

. We prove that they can be computed in polynomial time, and they incur a Price of Defense of

$\frac{|V|}{2}$

.

– In a

Defender Uniform Nash equilibrium

, the defender chooses uniformly each edge in its support. We prove that they incur a Price of Defense falling between those for Matching and Perfect Matching Nash Equilibria; however, it is

${\cal NP}$

-complete to decide their existence.

– In an

Attacker Symmetric

and

Uniform Nash equilibrium

, all attackers have a common support on which each uses a uniform distribution. We prove that they can be computed in polynomial time and incur a Price of Defense of either

$\frac{|V|}{2}$

or

α

(

G

).

Marios Mavronicolas, Loizos Michael, Vicky Papadopoulou, Anna Philippou, Paul Spirakis

We study the data complexity of the modal query language MDatalog and its extension eMDatalog in basic modal logics. MDatalog is a modal extension of Datalog, while eMDatalog is the general modal Horn fragment with the allowedness condition. As the main results, we prove that the data complexity of MDatalog and eMDatalog in

K

4,

KD

4, and

S

4 is PSPACE-complete, in

K

is coNP-complete, and in

KD

,

T

,

KB

,

KDB

, and

B

is PTIME-complete.

Linh Anh Nguyen

### The Complexity of Counting Functions with Easy Decision Version

We investigate the complexity of counting problems that belong to the complexity class

#P

and have an easy decision version. These problems constitute the class

#PE

which has some well-known representatives such as #

Perfect Matchings

, #

DNF-Sat

, and

NonNegative Permanent

. An important property of these problems is that they are all

#P

-complete, in the Cook sense, while they cannot be

#P

-complete in the Karp sense unless

P = NP

.

We study these problems in respect to the complexity class

TotP

, which contains functions that count the number of

all

paths of a PNTM. We first compare

TotP

to

#P

and

#PE

and show that

FP

TotP

#PE

#P

and that the inclusions are proper unless

P = NP

.

We then show that several natural

#PE

problems — including the ones mentioned above — belong to

TotP

. Moreover, we prove that

TotP

is exactly the Karp closure of self-reducible functions of

#PE

. Therefore, all these problems share a remarkable structural property: for each of them there exists a polynomial-time nondeterministic Turing machine which has as many computation paths as the output value.

Aris Pagourtzis, Stathis Zachos

### On Non-Interactive Zero-Knowledge Proofs of Knowledge in the Shared Random String Model

In this paper we study the notion of a

Double-Round

NIZ- KPK in the SRS model. In a Double-Round NIZKPK prover and verifier have access to the same random string Σ and, in addition, the prover is allowed to send one message to the verifier before Σ is made available. The verifier needs not to reply to this message. The random string and initial prover message can then be used in any polynomial number of proofs each consisting of a single message.

We show how to construct Double-Round

non-malleable

NIZKPKs in the SRS model by only requiring the existence of

one-way trapdoor permutations

. In contrast, regular NIZKPKs require the existence of cryptosystems with an extra density property, called dense secure cryptosystems. We then show that Double-Round NIZKPKs can replace one-round NIZKPKs in the design of secure protocols. The replacement has no significant effect on the round complexity of the larger protocol but it removes the need of the existence of dense secure cryptosystems. We give examples of cryptographic constructions that use one-round NIZKPKs and that are improved when using Double-Round NIZKPKs: 1) the construction of 3-round resettable zero-knowledge arguments in the UPK model [EUROCRYPT 2001]; 2) the construction of a constant-round (

n

– 1)-secure simulatable coin-flipping protocol [EUROCRYPT 2003].

Giuseppe Persiano, Ivan Visconti

### Constrained Minimum Enclosing Circle with Center on a Query Line Segment

In this paper, we will study the problem of locating the center of smallest enclosing circle of a set

P

of

n

points, where the center is constrained to lie on a query line segment. The preprocessing time and space complexities of our proposed algorithm are

O

(

n

log

n

) and

O

(

n

) respectively; the query time complexity is

O

(log

2

n

). We will use this method for solving the following problem proposed by Bose and Wang [3] – given

r

simple polygons with a total of

m

vertices along with the point set

P

, compute the smallest enclosing circle of

P

whose center lies in one of the

r

polygons. This can be solved in

O

(

n

log

n

+

m

log

2

n

) time using our method in a much simpler way than [3]; the time complexity of the problem is also being improved.

Sasanka Roy, Arindam Karmakar, Sandip Das, Subhas C. Nandy

### Hierarchical Unambiguity

We develop techniques to investigate relativized hierarchical unambiguous computation. We apply our techniques to push forward some known constructs involving relativized unambiguity based complexity classes (UP and Promise- UP) to new constructs involving arbitrary levels of the relativized unambiguous polynomial hierarchy (UPH). Our techniques are developed on constraints imposed by hierarchical assembly of

unambiguous

nondeterministic polynomial-time Turing machines, and so our techniques differ substantially, in applicability and in nature, from standard techniques (such as the switching lemma [Hås87]), which are known to play roles in carrying out similar generalizations.

Holger Spakowski, Rahul Tripathi

### An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Černy Conjecture

A word

w

is called synchronizing (recurrent, reset, directed) word of a deterministic finite automaton (DFA) if

w

sends all states of the automaton on a unique state. Jan Černy had found in 1964 a sequence of

n

-state complete DFA with shortest synchronizing word of length (

n

–1)

2

. He had conjectured that it is an upper bound for the length of the shortest synchronizing word for any

n

-state complete DFA.

The examples of DFA with shortest synchronizing word of length (

n

–1)

2

are relatively rare. To the Černy sequence were added in all examples of Černy, Piricka and Rosenauerova (1971), of Kari (2001) and of Roman (2004).

By help of a program based on some effective algorithms, a wide class of automata of size less than 11 was checked. The order of the algorithm finding synchronizing word is quadratic for overwhelming majority of known to date automata. Some new examples of

n

-state DFA with minimal synchronizing word of length (

n

–1)

2

were discovered. The program recognized some remarkable trends concerning the length of the minimal synchronizing word.

A. N. Trahtman

### On Genome Evolution with Innovation

We introduce and analyse a simple probabilistic model of genome evolution. It is based on three fundamental evolutionary events: gene

d

uplication,

l

oss and

i

nnovation, and it is called

DLI model

. The focus of the paper is around the size distribution of gene families. The formulas for equilibrium gene family sizes are derived showing that they follow a logarithmic distribution. We consider also a disjoint union of DLI models and we present the result of this study. Some empirical results for microbial genomes are presented.

Damian Wójtowicz, Jerzy Tiuryn

### Backmatter

Weitere Informationen