
Abstract:
We recently introduced an extensional model of the pure lambdacalculus
living in a cartesian closed category of sets and relations.
In this paper, we provide sufficient conditions for categorical models
living in arbitrary cpoenriched cartesian closed categories to have H, the
maximal consistent sensible lambdatheory, as equational theory. Finally, we
prove that our relational model fulfils these conditions.
Abstract:
Our goal is to start the investigation of the dynamic content of game
determinacy when games are played on finite graphs. We are interested in the
dynamic game determinacy problem formulated as follows. Find an algorithm
for maintaining the graph of the game that undergoes a sequence of update
and query operations in such a way that the algorithm facilitates an
efficient solution of the current game. We provide an algorithm that solves
the dynamic game determinacy problem when games are played on trees. We show
that the amortized time complexity of our algorithm is of order O(log(n)),
where n is the number of nodes on the current tree.
Abstract:
In a data word or a data tree each position carries a label from a finite
alphabet and a data value from an infinite domain. These models have been
considered in the realm of semistructured data, timed automata and
extended temporal logics.
Over data words we consider the logic 1regLTL(F), that extends LTL(F)
with one register for storing data values for later comparisons. We show
that satisfiability over data words of 1regLTL(F) is already not
primitive recursive. We also show that the extension of 1regLTL(F) with either
the reverse modality F^{1} or with one extra register is undecidable.
All those lower bounds were already known for 1regLTL(X,F) and our
results essentially show that the X modality was not necessary.
Moreover we show that over data trees similar lower bounds hold for
certain fragments of XPATH.
Abstract:
We consider a problem of hyperminimisation of an automaton
\cite{Badr,BadrRAIRO}:
given a DFA we want to compute a smallest automaton N
such that the language L(M) \simdiff L(N) is finite,
where \simdiff denotes the symmetric difference.
We improve the previously known O (Σn^{2}) solution
by giving an expected O (δlog n) time algorithm for this
problem,
where δ is the size of the (potentially partial) transition
function.
We also give a slightly slower deterministic O(δlog^{2} n)
version
of the algorithm.
Then we introduce a similar problem of kminimisation:
for an automaton M we want to find a smallest automaton N
such that L(M) \simdiff L(N) \subseteq Σ^{< k}, i.e.
the languages they recognize differ only on words of length less than k.
We characterise such minimal automata and give algorithm with a similar
complexity for this problem.
Abstract:
Straightline programs (SLPs) offer powerful text compression by
representing a text T[1,u] in terms of a restricted contextfree
grammar of n rules, so that T can be
recovered in O(u) time. However, the problem of operating the grammar in
compressed form has not been studied much. We present a grammar
representation whose size is of the same order of that of a
plain SLP representation, and can answer other queries apart from expanding
nonterminals. This can be of independent interest.
We then extend it to achieve the first grammar representation
able of extracting text substrings, and of searching the text
for patterns, in time o(n). We also give byproducts on representing binary
relations.
Abstract:
A graph is kchoosable if it admits a proper coloring of its vertices for
every assignment of k (possibly different) allowed colors to choose from
for each vertex. It is NPhard to decide whether a given graph is
kchoosable for k ≥ 3, and this problem is considered strictly harder
than the kcoloring problem. Only few positive results are known on input
graphs with a given structure. Here, we prove that the problem is fixed
parameter tractable on P_{5}free graphs when parameterized by k. This
graph class contains the well known and widely studied class of cographs.
Our result is surprising since the parameterized complexity of kcoloring
is still open on P_{5}free graphs. To give a complete picture, we show that
the problem remains NPhard on P_{5}free graphs when k is a part of the
input.
Abstract:
In this paper we formulate and study the problem of representing
groups on graphs. We show that with respect to polynomial time
turing reducibility, both abelian and solvable group
representability are all equivalent to graph isomorphism, even when
the group is presented as a permutation group via generators. On the
other hand, the representability problem for general groups on trees
is equivalent to checking, given a group G and n, whether a
nontrivial homomorphism from G to S_{n} exists. There does not
seem to be a polynomial time algorithm for this problem, in spite of
the fact that tree isomorphism has polynomial time algorithm.
Abstract:
The synchronization problem is investigated for a new class of deterministic
automata called locally strongly transitive. An application to synchronizing
colorings of aperiodic graphs with a cycle of prime length is also
considered.
Abstract:
A Solovay function is a computable upper bound g for prefixfree Kolmogorov
complexity K that is nontrivial in the sense that g agrees with
K, up to
some additive constant, on infinitely many places n. We obtain natural
examples of Solovay functions by showing that for any computable superlinear
time bound t, the timebounded version K^{t} of
K is a Solovay function.
Letting Ω_{g}=∑ 2^{g(n)}, we obtain as a corollary that the
MartinLöf randomness of the various variants of Chaitin's Ω extends
to the timebounded case in so far as for any t as above,
Ω_{Kt} is
MartinLöf random.
By generalizing results of Bienvenu and Downey and of Miller, we show that a
rightcomputable upper bound g of K is a Solovay function if
and only if Ω_{g} is MartinLöf random.
The problem whether the class of Ktrivial sets coincides with the class of
sets that are g(n)jumptraceable for all computable upper bounds
g of K has
recently received some attention. As a partial answer to this problem, we
demonstrate that a set A is Ktrivial if and only if
A is O(g(n)K(n))jump
traceable for all Solovay functions g, where by the preceding discussion the
equivalence remains true when g is replaced by
K^{t}.
Finally, we consider plain Kolmogorov complexity C and its timebounded
variant C^{t} of initial segments of computationally enumerable sets. Our main
theorem here has essentially the main attitude and structure as Kummer's gap
theorem, and asserts that every high c.e. Turing degree contains an c.e. set
B such that for any computable function t there is a constant
c_{t}>0 such
that for all m it holds that C^{t}(B(0) ... B(m1)) =>
c_{t}m, whereas for any
nonhigh c.e. set A there is a computable time bound t and a constant
c such
that for infinitely many m it holds that C^{t}(A(0) ... A(m1)) <= log m +
c. By similar methods it can be shown that any high degree contains a set
B
such that C^{t}(B(0) ... B(m1)) =>^{+} m/4. The constructed
sets B have high
unbounded but much lower timebounded Kolmogorov complexity, and accordingly
we obtain in addition an alternative and somewhat simpler proof of the
result due to Juedes, Lathrop, and Lutz that every high degree contains a
strongly deep set.
Abstract:
Nested Pushdown Trees are unfoldings of pushdown graphs
with an additional jumprelation. These graphs are closely related to
collapsible
pushdown graphs. They enjoy decidable μcalculus model checking
while monadic secondorder logic is undecidable on this class. We
show that nested pushdown trees are treeautomatic structures, whence
firstorder model checking is decidable. Furthermore, we prove that the
model checking is in 2EXPSPACE using pumping arguments on runs of
pushdown systems. For these arguments we also develop a Gaifman style
argument for graphs of small diameter.
Abstract:
If the given problem instance is partially solved, we want to
minimize our effort to solve the problem using that information.
In this paper we introduce the measure of entropy
H(S) for uncertainty in partially solved input data
S(X)=(X_{1}, ..., X_{k}), where
each X_{i} is already solved. We use the entropy measure to analyze
three example problems, sorting, shortest paths and minimum spanning trees.
For sorting X_{i} is an ascending run, and
for shortest paths, X_{i} is an acyclic part in the given graph.
For minimum spanning trees, X_{i} is interpreted as the partially
obtained minimum spanning tree for a subgraph.
The entropy measure, H(S), is defined by regarding
p_{i}=X_{i}/X as
a probability measure, that is, H(S)=nΣ^{k}_{i=1} p_{i} log
p_{i},
where n=Σ^{k}_{i=1}X_{i}.
Then we show that we can sort the input data S(X) in
O(H(S)) time,
and solve the shortest path problem in O(m+H(S)) time where
m is the number of edges of the graph.
Fianlly we show that the minimum spanning tree is computed in
O(m+H(S)) time.
Abstract: Given a finite graph whose edges are labeled with integer colors, we study the problem of determining whether there is an infinite path where either
Abstract:
A dichotomy theorem for counting problems due to Creignou and Hermann states
that or any finite set S of logical relations, the counting problem #SAT(S)
is either in FP, or #Pcomplete.
In the present paper we show a dichotomy theorem for polynomial evaluation.
That is, we show that for a given set S, either there exists a VNPcomplete
family of polynomials associated to S, or the associated family of
polynomials are all in VP. We give a concise characterization of the sets S
that give rise to "easy" and "hard" polynomials.
We also prove that several problems which were known to be #Pcomplete under
Turing reductions only are in fact #Pcomplete under manyone reductions.
Abstract:
The description of a single state of a modelled system is often complex
in practice, but few procedures for synthesis address this problem in depth.
We study systems in which a state is described by an arbitrary
finite structure, and changes of the state are represented by structure
rewriting rules, a generalisation of term and graph rewriting.
Both the environment and the controller are allowed to change the structure
in this way, and the question we ask is how a strategy for the controller
that ensures a given property can be synthesised.
We focus on one particular class of structure rewriting rules, namely on
separated structure rewriting, a limited syntactic class of rules.
To counter this restrictiveness, we allow the property to be ensured
by the controller to be specified in a very expressive logic:
a combination of monadic secondorder logic evaluated on states and
the modal mucalculus for the temporal evolution of the whole system.
We show that for the considered class of rules and this logic, it can
be decided whether the controller has a strategy ensuring a given property,
and in such case a finitememory strategy can be synthesised. Additionally,
we prove that the same holds if the property is given by a monadic
secondorder
formula to be evaluated on the structure being the limit of the evolution
of the system. As an example application, we show how a known result on
decidability of monadic secondorder properties of pushdown graphs is
a corollary of this result, and we discuss other possible generalisations.
Abstract:
Let I be a finite set of integers and F be a finite set of maps of the
form $n\mapsto k_{i} n + \ell_{i}$ with integer coefficients. For an integer
base k ≥ 2, we study the krecognizability of the minimal set
X of
integers containing I and satisfying f(X) ⊆ X for all f ∈ F.
In particular, answering a conjecture of Allouche and Shallit, we show under
some technical condition that if two of the constants k_{i}'s are
multiplicatively independent, then X is not krecognizable for any k
≥ 2.
Abstract:
We show that for some semiring K, the support of a recognizable series over
K is always recognizable if and only if in every finitely generated
subsemiring of K there exists a finite congruence such that the zero of K is
a singleton congruence class.
Abstract:
In this paper we study a subclass of pebble automata (PA) for data languages
for which the emptiness problem is decidable. Namely, we show that the
emptiness problem for weak 2pebble automata is decidable, while the same
problem for weak 3pebble automata is undecidable. We also introduce the
socalled top view weak PA.
Roughly speaking, top view weak PA are weak PA where the equality test is
performed only between the data values seen by the two most recently placed
pebbles.
The emptiness problem for this model is still decidable.
Abstract:
The satisfiability problem of hybrid logics with the downarrow binder is
known to be undecidable. This initiated a research program on decidable and
tractable fragments.
In this paper, we investigate the effect of restricting the propositional
part of the language on decidability and on the complexity of the
satisfiability problem over arbitrary, transitive, total frames, and frames
based on equivalence relations. We also consider different sets of temporal
and hybrid operators.
We trace the border of decidability and give the precise complexity of most
fragments, in particular for all fragments including negation. For the
monotone fragments, we are able to distinguish the easy from the hard cases,
depending on the allowed set of operators.
Abstract:
We investigate whether all Boolean submodular functions can be decomposed
into a sum of binary submodular functions over a possibly larger set of
variables. This question has been considered within several different
contexts in computer science, including computer vision, artificial
intelligence, and pseudoBoolean optimisation. Using a connection between
the expressive power of valued constraints and certain algebraic properties
of functions, we answer this question negatively.
Our results have several corollaries. First, we characterise precisely which
submodular polynomials of degree 4 can be expressed by quadratic submodular
polynomials. Next, we identify a novel class of submodular functions of
arbitrary arities which can be expressed by binary submodular functions, and
therefore minimised efficiently using a socalled expressibility reduction
to the MinCut problem. More importantly, our results imply limitations on
this kind of reduction and establish for the first time that it cannot be
used in general to minimise arbitrary submodular functions. Finally, we
refute a conjecture of Promislow and Young on the structure of the extreme
rays of the cone of Boolean submodular functions.
Abstract:
In this paper we show that the set of points covered by computable curves in
IR^{2} is a proper superset of the set of points covered by computable
curves with computable length, where a plan curve C computable if there
exists an injective, computable function f:[0;1] → IR^{2} such that
C
is the range of f. More precisely, we construct a computable curve
K and
a points z on K such that no computable curve of computable length
contains this point z. This gives a positive answer to a recent open
question of Gu, Lutz and Mayordomo.
Abstract:
We study the relations between Multiplicative Exponential Linear Logic
(meLL) and BaillotMazza Linear Logic by Levels (mL^{3}). We design a
decorationbased translation between propositional meLL and propositional
mL^{3}. The translation preserves the cut elimination. Moreover, we show that
there is a proof net Π of second order meLL that cannot have a
representative Π' in second order mL^{3} under any decoration. Every such a
representative should identify two distinct indices. This suggests that
levels can be an analytical tool in understanding the complexity of second
order quantifier.
Abstract:
The parameterized complexity classes of the Whierarchy are usually defined
as the problems reducible to certain natural complete problems by means of
fixedparameter tractable (fpt) reductions. We investigate whether
the classes can be characterised by means of weaker, logical reductions. We
show that each class W[t] has complete problems under
slicewise boundedvariable firstorder reductions. These are a
natural weakening of the slicewise boundedvariable LFP reductions
which, by a result of Flum and Grohe are known to be
equivalent to fpt reductions. If we relax the restriction on having a
bounded number of variables, we obtain reductions that are too strong in
that
there are problems in W[t+1] that reduce to problems in W[t] under
slicewise firtsorder reductions. On the other hand, we
show that if we consider slicewise quantifierfree firstorder
reductions, they are considerably weaker in that there are problems in
W[t+1] that provably cannot reduce to any problem in W[t] under such
reductions.
Abstract:
The model of Priority Algorithm syntactically formulates the concept of
greedy algorithm [BNR03]. In this paper we investigate properties of the
computation of optimal priority algorithms. The approximation power of
priority algorithms for Job Scheduling is wellunderstood. A Job Scheduling
subproblem is determined by a set of jobs, every finite subset of which
forms an input. To the best of our knowledge there is no previous work about
such arbitrary subproblems of Job Scheduling. An algorithm is optimal on a
set determining the subproblem if it gains optimal profit on every input.
Although there is strong evidence [PR07] that meaningful characterizations
for arbitrary subproblems are not possible, we are able to ask about
features of optimal priority algorithms. We ask these questions in the
general setting of an arbitrary Job Scheduling subproblem and an arbitrary
optimal priority algorithm. Our study shows that there is rich and
interesting structure in the computation of such algorithms.
Abstract:
Let C be a threshold logic circuit computing a Boolean function
MOD_{m}: {0, 1}^{n} → {0, 1}, where n
≥ 1 and m ≥ 2. Then C outputs "0"
if the number of "1"s in an input \Vec{x} ∈ {0, 1}^{n} to
C is a
multiple of m and, otherwise, C outputs "1". The function
MOD_{2} is
the socalled PARITY function, and MOD_{n+1} is the OR function. Let
s be the size of the circuit C, that is, C consists of
s threshold gates, and let e be the energy complexity of
C, that is, at most e gates in C output "1" for any input
\Vec{x} ∈ {0, 1}^{n}. In the paper, we prove that a very simple
inequality n/(m1) ≤ s^{e} holds for
every circuit C computing MOD_{m}. The inequality implies that there is a
tradeoff between the size s and energy complexity e of a threshold
circuit C computing MOD_{m}, and yields a lower bound
e = Ω ((log n  log m)/log log n) on e if
s=O(polylog(n)).
We actually obtain a general result on the socalled generalized mod
function, from which the result on the ordinary mod function
MOD_{m} immediately follows.
Abstract:
The longest path problem is the problem of finding a path of maximum length
in a graph. Polynomial solutions for this problem are known only for
small classes of graphs, while it is NPhard on general graphs, as it is a
generalization of the Hamiltonian path problem. Motivated by the work
of Uehara and Uno in~\cite{Ueh04}, where they left the longest path problem
open for the class of interval graphs, in this paper we show that the
problem can be solved in polynomial time on interval graphs. The proposed
algorithm runs in O(n^{4}) time, where n is the
number of vertices of
the input graph, and bases on a dynamic programming approach.
Abstract:
We consider approximation algorithms for the shortest common superstring
problem (SCS). It is wellknown that there exists a constant f>1 such that
there is no efficient approximation algorithm for SCS achieving a factor of
at most
f in the worst case, unless P=NP. We study SCS on random inputs and present
an approximation scheme that achieves, for every eps>0, a
1+epsapproximation in expected polynomial time. This result applies not
only if the letters are chosen independently at random, but also to the more
realistic mixing model, which allows dependencies among the letters of the
random strings. Our result is based on a sharp tail bound on the optimal
compression, which improves a previous result by Frieze and Szpankowski.
Abstract:
Algorithmic mechanism design considers distributed settings where the
participants, termed agents, cannot be assumed to follow the protocol but
rather their own interests. The protocol can be regarded as an algorithm
augmented with a suitable payment rule and the desired condition is termed
*truthfulness*, meaning that it is never convenient for an agent to report
false information.
Motivated by the applications, we extend the usual oneparameter and
multiparameter settings by considering agents with *private capacities*:
each agent can misreport her cost for `executing'' a single unit of work
*and* the maximum amount of work that each agent can actually execute (i.e.,
the capacity of the agent). We show that truthfulness in this setting is
equivalent to a simple condition on the underlying algorithm. By applying
this result to various problems considered in the literature (e.g., makespan
minimization on related machines) we show that only some of the existing
approaches to the case "without capacities" can be adapted to the case with
private capacities. This poses new interesting algorithmic challenges.
Abstract:
A dgem is a {+,,×}circuit having very few
×gates and computing from {x}∪Z a
univariate polynomial of degree d having d distinct integer
roots. We introduce dgems because they could help factoring
integers and because their existence for infinitely
many d would blatantly disprove a variant of the
BlumCuckerShubSmale conjecture. A natural step towards validating the
conjecture would thus be to rule out dgems for large d. Here
we construct dgems for several values of d up to 55. Our
2^{n}gems for n ≤ 4 are skew, that is, each
{+,}gate adds an integer. We prove that skew
2^{n}gems
if they exist require n {+,}gates, and that these for n ≥
5 would imply new solutions to the ProuhetTarryEscott problem in
number theory. By contrast, skew dgems over the real numbers are
shown to exist for every d.
Abstract: An intersection graph of n vertices assumes that each vertex is equipped with a subset of a global label set. Two vertices share an edge when their label sets intersect. Random Intersection Graphs (RIGs) (as defined in \cite{KSS99,S95}) consider label sets formed by the following experiment: each vertex, independently and uniformly, examines all the labels (m in total) one by one. Each examination is independent and the vertex succeeds to put the label in her set with probability p. Such graphs nicely capture interactions in networks due to sharing of resources among nodes. We study here the problem of efficiently coloring (and of finding upper bounds to the chromatic number) of RIGs. We concentrate in a range of parameters not examined in the literature, namely:
Abstract:
In this paper, we investigate three strategies
of how to use a spanning tree T of a graph G to navigate in
G, i.e., to move from a current vertex x
towards a destination vertex y via a path that is close to
optimal. In each strategy, each vertex v has full knowledge of its
neighborhood N_{G}[v] in G (or, kneighborhood
D_{k}(v,G), where
k is a small integer) and uses a small piece of global information
from spanning tree T (e.g., distance or ancestry information in
T), available locally at v, to navigate in G. We investigate
advantages and limitations of these strategies on particular
families of graphs such as graphs with locally connected spanning
trees, graphs with bounded length of largest induced cycle, graphs
with bounded treelength, graphs with bounded hyperbolicity. For
most of these families of graphs, the ancestry information from a
BreadthFirstSearchtree guarantees short enough routing paths. In
many cases, the obtained results are optimal up to a constant
factor.
Abstract:
We study a model of communication complexity that
encompasses many wellstudied problems, including
classical and quantum communication complexity,
the complexity of simulating distributions arising from
bipartite measurements of shared quantum states, and
XOR games. In this model, Alice gets an input x, Bob
gets an input y, and their goal is to each produce an output
a,b distributed according to some prespecified
joint distribution
p(a,bx,y).
Our results apply to any nonsignaling distribution,
that is, those where Alice's marginal distribution does not
depend on Bob's input, and vice versa,
therefore our techniques apply to any communication problem that
can be reduced to a nonsignaling distribution, including
quantum distributions,
Boolean and nonBoolean functions, most relations, partial
(promise) problems, in the twoplayer and multipartite settings.
By introducing a simple new technique based on affine combinations of
lowercomplexity distributions, we give elementary proofs and
very intuitive interpretations of the recent lower bounds
of Linial and Shraibman, which we generalize to the problem
of simulating any nonsignaling distribution.
The lower bounds
we obtain are also expressed as linear programs (or SDPs
for quantum communication).
We show that the dual formulations have
a striking interpretation, since they
coincide with maximum violations of Bell and Tsirelson inequalities.
The dual expressions are closely related to the winning
probability of XOR games.
We show that as in the case of Boolean functions, the gap
between the quantum and classical lower bounds is at most linear in
size of the support of the distribution, and does not depend on the
size of the inputs. This translates into a bound on
the gap between maximal Bell and Tsirelson inequalities, which
was previously known only for the case of distributions with Boolean
outcomes and uniform marginals.
Finally, we give an exponential upper bound on quantum and classical
communication complexity in the simultaneous messages model, for
any nonsignaling distribution.
One new consequence is that any quantum distribution
can be simulated with a logarithmic number of qubits in
the simultaneous messages model, independently of the
amount of entanglement in the bipartite state measured
by the two parties.
Abstract:
An edge cover C is a set of edges of an undirected graph such that every
vertex has an adjacent edge in C. We show that a Glauber dynamics Markov
chain for edge covers mixes rapidly for threeregular graphs (or graphs with
degrees at most three). Glauber dynamics have been studied extensively in
the statistical physics community, with special emphasis on lattice graphs.
Our results apply, for example, to the hexagonal lattice. Our proof of rapid
mixing introduces a new cycle/path decomposition for the canonical flow
argument.
Abstract:
We show that each level of the quantifier alternation hierarchy within
FO^{2}[<]  the 2variable fragment of the first order logic of order on
words  is a variety of languages. We then use the notion of condensed
rankers, a refinement of the rankers defined by Weis and Immerman, to
produce a decidable hierarchy of varieties which is interwoven with the
quantifier alternation hierarchy  and conjecturally equal to it. It
follows that the latter hierarchy is decidable within one unit: given a
formula alpha in FO^{2}[<], one can effectively compute an integer m such that
alpha is equivalent to a formula with at most m+1 alternating blocks of
quantifiers, but not to a formula with only m1 blocks. This is a much more
precise result than what is known about the quantifier alternation hierarchy
within FO[<], where no decidability result is known beyond the very first
levels.
Abstract: The main motivation of this paper is to study lower bounds for circuit and branching program size over monomial algebras. both in the noncommutative and commutative setting. Our main results are:
Abstract:
We define a framework called the prismoid of resources where each vertex
is a lambda calculus with the possibility of having different explicit
resources and/or explicit cut elimination based on a different choice to
make explicit or implicit (metalevel) the definition of the contraction,
weakening, substitution operations.
For all the calculi in the prismoid we show simulation of beta
reduction, confluence, preservation of betastrong normalisation and
strong normalisation
for typed terms. Full composition also holds for the prismoid base handling
explicit substitutions.
The whole development of the prismoid is done by making the set of resources
a parameter, so that the properties for each vertex are obtained as a
particular case of the general abstract proofs.
Abstract:
The concept of determinism, while clear and well assessed for
string languages, is still matter of research as far as picture
languages are concerned. We introduce here a new kind of
determinism, called snake, based on the boustrophedonic scanning
strategy, that is a natural scanning strategy used by many
algorithm on 2D arrays and pictures. We consider a
snakedeterministic variant of tiling systems, which defines the
socalled snakeDREC class of languages. SnakeDREC properly
extends the more traditional approach of diagonalbased
determinism, used e.g. by Deterministic tiling systems, and by
online tessellation automata. Our main result is showing that the
concept of snakedeterminism of tiles coincides with row (or
column) unambiguity.
Abstract:
Cellular automata (CA) are discrete, homogeneous dynamical systems.
Nonsurjective onedimensional CA have finite words with no preimage
(called orphans), pairs of different words starting and
ending identically and having the same image (diamonds) and
words with more/fewer preimages than the average number
(unbalanced words). Using a linear algebra approach, we
obtain new upper bounds on the lengths of the shortest such objects.
In the case of an nstate, nonsurjective CA with neighborhood
range 2 our bounds are of the orders O(n^{2}),
O(n^{3/2}) and
O(n) for the shortest orphan, diamond and unbalanced word,
respectively.
Abstract:
We study visibly pushdown automata (VPA) models for expressing and
evaluating queries on words with a nesting structure.
We define a query VPA model, which is a 2way deterministic
VPA that can mark in one run \emph{all} positions in a document
that satisfy a query, and show that it is equiexpressive as
unary monadic queries.
This surprising result parallels a classic result by Hopcroft and
Ullman for queries on regular word languages. We also compare our
model to query models on unranked trees, and show that our result
is fundamentally different from those known for automata on trees.
Abstract:
Originated from sand pile model, onedimensional sand automata are
a discrete dynamical system which is an intermediate between one
dimensional cellular automata and twodimensional cellular
automata. In this paper, we shall study the decidability of the
global behavior of this system according to his local definition. In
particular, we shall focus on the problem of injectivity and
surjectivity which have the property of being decidable for
onedimensional cellular automata and undecidable for
twodimensional one. We prove the following quite surprising
property that one (surjectivity) is undecidable whereas the other
one (injectivity) is decidable. For completeness, we also study this
question for some classical restriction of configurations (finite,
periodic and bounded ones).
Abstract:
We study deterministic regular expressions extended with the counting
operator. There exist two notions of determinism, strong and weak
determinism, which almost coincide for standard regular expressions. This,
however, changes dramatically in the presence of counting. In particular, we
show that weakly deterministic expressions with counting are exponentially
more succinct and strictly more expressive than strongly deterministic ones,
even though they still do not capture all regular languages. In addition, we
present a finite automaton model with counters, study its properties and
investigate the natural extension of the Glushkov construction translating
expressions with counting into such counting automata. This translation
yields a deterministic automaton if and only if the expression is strongly
deterministic. These results then also allow to derive upper bounds for
decision problems for strongly deterministic expressions with counting.
Abstract:
To make a joint decision, agents (or voters) are often required to
provide their preferences as linear orders. To determine a winner, the
given linear orders can be aggregated according to a voting
protocol. However, in realistic settings, the voters may often only
provide partial orders. This directly leads to the Possible
Winner problem that asks, given a set of partial votes, if a
distinguished candidate can stil become a winner. In this work, we consider
the
computational complexity of Possible Winner for the broad
class of voting protocols defined by scoring rules. Generally, a
scoring rule provides a score value for every position which a
candidate can have in a linear order. Prominent examples include
plurality, kapproval, and Borda. Generalizing previous NPhardness
results for some special cases and providing new manyone reductions,
we settle the computational complexity for all but one scoring
rule. More precisely, for an unbounded number of candidates and
unweigthed voters, we show that Possible Winner is
NPcomplete for all scoring rules except plurality, veto, and the
scoring rule defined by the scoring vector (2,1,...,1,0), and that it is
solvable in polynomial time for plurality and veto.
Abstract:
We consider games played on finite graphs, whose objective is to obtain a
trace belonging to a given set of accepting traces.
We focus on the states from which Player 1 cannot force a win.
We compare several criteria for establishing what is the preferable behavior
of Player 1 from those states, eventually settling on the notion of
admissible strategy.
As the main result, we provide a characterization of the goals
admitting positional admissible strategies.
In addition, we derive a simple algorithm for computing such strategies
for various common goals, and we prove the equivalence between
the existence of positional winning strategies and
the existence of positional subgame perfect strategies.
Abstract:
We investigate the computational complexity of a general "compression
task" centrally occurring in the recently developed technique of iterative
compression for exactly solving NPhard minimization problems. The core
issue (particularly but not only motivated by iterative compression)
is to determine the computational complexity of, given an already
inclusionminimal solution for an underlying (typically NPhard) vertex
deletion problem, to find a better disjoint solution. The complexity of
this task is so far lacking a systematic study. We show that, except
for few cases where it is polynomialtime solvable, it is otherwise
NPcomplete. Our result applies to a large class of vertex deletion
problems on undirected graphs, including problems such as Vertex Cover
(here the corresponding compression task is decidable in polynomial time)
or Undirected Feedback Vertex Set (here the corresponding compression
task is NPcomplete).
Abstract:
We consider a general framework in which a memoryless robot periodically
explores all the nodes of a connected anonymous graph by following local
information available at each vertex. For each vertex v, the endpoints of
all edges adjacent to v are assigned unique labels from the range
1 to deg(v) (the degree of v). The generic exploration
strategy is
implemented using a righthandrule transition function: after entering
vertex v via the edge labeled i, the robot proceeds with its
exploration, leaving via the edge having label [(i+1) mod deg(v)] at
v.
A lot of attention has recently been given to the problem of labeling the
graph so as to achieve a periodic exploration having the minimum possible
length π. It has recently been shown [Czyzowicz at al., Proc.
SIROCCO'09] that π ≤ 4 \frac13 n holds for all graphs of n vertices.
Herein, we provide a new labeling scheme which leads to shorter exploration
cycles, improving the general bound to π ≤ 4 n  2. This main result
is shown to be tight with respect to the class of labelings admitting
certain connectivity properties. The labeling scheme is based on a new graph
decomposition which may be of independent interest.
Abstract:
Given an arbitrary graph G and a number k, it is wellknown by a result
of Seymour and Thomas \cite{SeTo93} that G has treewidth strictly larger
than k if and only if it has a bramble of order k+2. Brambles are used
in combinatorics as certificates proving that the treewidth of a graph is
large.
From an algorithmic point of view, there are several algorithms computing
treedecompositions of G of width at most k, if such decompositions
exist and the running time is polynomial for constant k.
Nevertheless, when the treewidth of the input graph is larger than k, to
our knowledge there is no algorithm constructing a bramble of order k+2.
We give here such an algorithm, running in O(n^{k+4}) time. Moreover, for
classes of graphs with polynomial number of minimal separators, we define a
notion of compact brambles and show how to compute compact brambles
of order k+2 in polynomial time, not depending on k.
Abstract: In 1983 Akl and Taylor [Cryptographic Solution to a Problem of Access Control in a Hierarchy, ACM Transactions on Computer Systems, 1(3), 239248, 1983] first suggested the use of cryptographic techniques to enforce access control in hierarchical structures. Due to its simplicity and versatility, the scheme has been used, for more than twenty years, to implement access control in several different domains, including mobile agent environments and XML documents. However, despite of its use over the time, the scheme has never been fully analyzed with respect to security and efficiency requirements. In this paper we provide new results on the AklTaylor scheme and its variants. More precisely:
Abstract:
The paper studies the expressivity, relative succinctness and complexity of
satisfiability for hybrid extensions of the branchingtime logics CTL and
CTL+ by variables. Previous complexity results show that only fragments with
one variable do have elementary complexity. It is shown that H1CTL+ and
H1CTL are expressively equivalent but H1CTL+ is exponentially more succinct
than H1CTL. On the other hand, H1CTL1 does not capture CTL*, even with
arbitrarily many variables, as it cannot express the simple CTL* property
EGFp. The satisfiability problem for H1CTL+ is complete for triply
exponential time, this remains true for quite weak fragments and quite
strong extensions of the logic.
Abstract:
We present a simple algorithm for the maximum spanning star forest problem.
We take advantage of the fact that the problem is a special case of
complementary set cover and we adapt an algorithm of Duh and Fürer in
order to solve it. We prove that this algorithm computes 193/240 ≈
0.804approximate spanning star forests; this result improves a previous
lower bound of 0.71 by Chen et al. Although the algorithm is purely
combinatorial, our analysis defines a linear program that uses a parameter
f and which is feasible for values of the parameter f not smaller than
the approximation ratio of the algorithm. The analysis is tight and,
interestingly, it also applies to complementary versions of set cover such
as color saving; it yields the same approximation guarantee of 193/240
that marginally improves the previously known upper bound of Duh and
Fürer. We also show that, in general, a natural class of local search
algorithms do not provide better than 1/2approximate spanning star
forests.
Abstract:
A real α is called recursively enumerable ("r.e." for short) if there
exists a computable, increasing sequence of rationals which converges to
α. It is known that the randomness of an r.e. real α can be
characterized in various ways using each of the notions; programsize
complexity, MartinLöf test, Chaitin Ω number, the domination and
Ωlikeness of α, the universality of a computable, increasing
sequence of rationals which converges to α, and universal probability.
These equivalent characterizations are a central result of algorithmic
randomness and a current focus of the research. In this paper, we generalize
these characterizations of randomness over the notion of partial randomness
by parameterizing each of the notions above by a real T in (0,1], where the
notion of partial randomness is a stronger representation of the compression
rate by means of programsize complexity. As a result, we present ten
equivalent characterizations of the partial randomness of an r.e. real. The
resultant characterizations of partial randomness are powerful and have many
important applications. One of them is to present equivalent
characterizations of the dimension of an individual r.e. real. The
equivalence between the notion of Hausdorff dimension and compression rate
by programsize complexity (or partial randomness) has been established at
present by a series of works of many researchers over the last two decades.
The subject of the equivalence is one of the most active areas of the
current research of algorithmic randomness. In this paper, we present ten
equivalent characterizations of the dimension of an r.e. real.
Abstract:
This paper establishes a surprising reduction from parity and mean payoff
games to linear programming problems. While such a connection is trivial for
solitary games, it is surprising for two player games, because the players
have opposing objectives, whose natural translations into an optimisation
problem are minimisation and maximisation, respectively. Our reduction to
linear programming circumvents the need for concurrent minimisation and
maximisation by replacing one of them, the maximisation, by approximation.
The resulting optimisation problem can be translated to a linear programme
by a simple space transformation, which is inexpensive in the unit cost
model, but results in an exponential growth of the coefficients. The
discovered connection opens up unexpected applications  like
μcalculus model checking  of linear programming in the unit cost
model and thus turns the intriguing academic problem of finding a polynomial
time algorithm for linear programming in this model of computation (and
subsequently a strongly polynomial algorithm) into a problem of paramount
practical importance: All advancements in this area can immediately be
applied to accelerate solving parity and payoff games, or to improve their
complexity analysis.
Abstract:
We study communication problems in wireless networks supporting multiple
interfaces. In such networks, two nodes can communicate if they are close
and share a common interface. The activation of each interface has a cost
reflecting the energy consumed when a node uses this interface. We
distinguish between the symmetric and nonsymmetric case, depending on
whether all nodes have the same activation cost for each interface or not.
For the symmetric case, we present a 3/2+εapproximation algorithm
for the problem of achieving connectivity with minimum activation cost,
improving a previous bound of 2. For the nonsymmetric case, we show that
the connectivity problem is not approximable within a sublogarithmic factor
in the number of nodes and present a logarithmic approximation algorithm for
a more general problem that models group communication.
Abstract:
The problem FT^{t}_{d} consists in computing the value
in [k]={1,...,k}
taken by the root of a balanced dary tree of height h whose internal
nodes are labelled with dary functions on [k] and whose leaves are
labelled with elements of [k]. We propose
FT^{t}_{d} as a good candidate
for witnessing lspace \subsetneq logdcfl. We observe that the latter would
follow from a proof that kway branching programs solving
FT^{t}_{d} require
Ω(k^{unbounded function(h)}) size. We introduce a "state
sequence" method that can match the size lower bounds on
FT^{t}_{d} obtained by the
Neciporuk method and can yield slightly better (yet still subquadratic)
bounds for some nonboolean functions. Both methods yield the tight bounds
Θ(k^{3}) and Θ(k^{5/2}) for deterministic
and nondeterministic branching programs solving
FT^{3}_{2} respectively. We propose as a challenge
to break the quadratic barrier inherent in the Neciporuk method by adapting
the state sequence method to handle FT^{4}_{d}.
Abstract:
We show that ktree isomorphism can be decided in logarithmic space by
giving a logspace canonical labeling algorithm. This improves over the
previous StUL upper bound and matches the lower bound. As a consequence, the
isomorphism, the automorphism, as well as the canonization problem for
ktrees are all complete for deterministic logspace.
Abstract:
Most quantum algorithms that give an exponential speedup over
classical algorithms exploit the Fourier transform in some way. In
Shor's algorithm, the Fourier transform is used to discover
periodicity which is accomplished by sampling from the Fourier
spectrum of a function. In a generalization of this idea, quantum
Fourier sampling can be used to discover hidden subgroup structures
of some functions much more efficiently than it is possible
classically. Another problem for which the Fourier transform has
been recruited successfully on a quantum computer is the hidden
shift problem. Quantum algorithms for hidden shift problems usually
have a slightly different flavor from hidden subgroup algorithms, as
they use the Fourier transform to perform a correlation with a
given reference function, instead of sampling from the Fourier
spectrum directly. In this paper we show that hidden shifts can be
extracted efficiently from Boolean functions that are quadratic
forms. We also show how to identify an unknown quadratic form on n
variables using a linear number of queries, in contrast to the
classical case were this takes Θ(n^{2}) many queries to a black
box. What is more, we show that our quantum algorithm is robust in
the sense that it can also infer the shift if the function is close
to a quadratic, where we consider a Boolean function to be close to
a quadratic if it has a large Gowers U_{3} norm.
Abstract:
Cooperative game theory solution concepts define ways of dividing a
coalition's gains among its members ("imputations"). A prominent solution
concept is the core, focusing on stable imputations where no subset of
agents has an incentive to leave the grand coalition. However, some games
have empty cores.
We consider stabilizing cooperative games by having an external party offer
a supplemental payment to the grand coalition. The adjusted gains, the sum
of this payment and the original gains of the coalition, may be divided
among agents in a stable manner. Such a division of the adjusted gains is
called a superimputation, and the minimal sum of payments that stabilizes a
game is called the cost of stability (CoS).
We examine the CoS in threshold network flow games, where each player
controls an edge in the network flow graph, and a coalition of player
succeeds if the maximal flow it can send from the source to the sink exceeds
a certain threshold. We show that it is coNPcomplete to determine whether a
given superimputation in such a game is stable. We give bounds on the CoS
in general network flow games, and provide efficient algorithms for
computing the CoS and finding stable superimputations in several restricted
cases. We also consider the relation between the CoS in Network Flow Games
and the CoS in another known game theoretic domain, weighted voting games.
Abstract:
In contrast to extremal coNPcomplete problems, which are
frequently DPcomplete, many extremal NPcomplete problems are in P. We
investigate two extremal NPcomplete problems, the extremal colorability
problem with restricted degree and the extremal unfrozen nonimplicant
problem, and show that both of them are DPcomplete.