- 14.7.2010, 15:15 Uhr, Johannisgasse 26, 4-42
Ingmar Meinecke (Universität
Leipzig):
Regular Expressions on Average and in the Long Run -
Quantitative aspects of systems like consumption of resources, output of
goods, or reliability can be modeled by weighted automata. Recently,
objectives like the average cost or the longtime peak power consumption
of a system have been modeled by weighted automata which are not
semiring weighted anymore. Instead, operations like limit superior,
limit average, or discounting are used to determine the behavior of
these automata. Here, we introduce a new class of weight structures
subsuming a range of these models as well as semirings. Our main result
shows that such weighted automata and Kleene-type regular expressions
are expressively equivalent both for finite and infinite words.
This is joint work with Manfred Droste.
- 15.6.2010, 9:15 Uhr, Johannisgasse 26, 4-42
Jiamou
Liu (University of Auckland und Universität
Leipzig):
Computable Categoricity of Graphs with Finite Components -
A graph is computable if its set of nodes and edge relation are
computable sets. A computable graph is computably categorical if any
two computable presentations of the graph are computably isomorphic.
We focus on the class of computably categorical graphs. In particular,
we investigate the strongly locally finite graphs: graphs all of whose
components are finite. In this talk we discuss the following results:
(1) We present a necessary and sufficient condition for certain
classes of strongly locally finite graphs to be computably
categorical. (2) Whenever there exists an infinite Δ 20-set of
components that can be properly embedded into infinitely many
components of the graph, the graph is not computably categorical. (3)
There exists a strongly locally finite computably categorical graph
with a infinite chain of properly embedded components.
- 9.6.2010, 15:15 Uhr, Johannisgasse 26, 4-42
Markus Lohrey ( Universität
Leipzig):
Branching time model checking of one-counter processes -
One-counter processes are pushdown processes which operate only
on a unary stack alphabet. In this talk, I will survey recent
progress on the complexity of various model checking problems over
one-counter processes.
The main focus will be on the temporal logic CTL and its
fragment EF. It turns out that CTL model checking over
one-counter processes is PSPACE-complete, where the lower
bound already holds (i) for a fixed one-counter process
(expression complexity) and (ii) for a fixed CTL formula (data complexity).
The proof of the second result uses two interesting techniques
from computational complexity theory:
(i) Converting a natural number from Chinese remainder representation
into binary
representation is in logspace-uniform NC1 and
(ii) PSPACE is AC0-serializable.
For the CTL fragment EF we obtain complexity results
for the complexity class PNP.
This is joint work with Stefan Göller.
- 26.5.2010, 15:15 Uhr, Johannisgasse 26, 4-42
Manfred Droste ( Universität
Leipzig):
Random constructions of countable abelian p-groups -
By Ulm's theorem, countable reduced abelian p-groups are
characterized, uniquely up to isomorphism, by their Ulm invariants.
Given a sequence f of Ulm invariants, we provide a probabilistic
construction of a countable abelian p-group Gf, having the set
of natural numbers as its domain, with Ulm invariants less or equal to f.
We then show that with probability 1, Gf has precisely f as
its sequence of Ulm invariants. This establishes the existence part
of Ulm's theorem in a probabilistic way. We also develop new results
for valuated abelian p-groups which are essential for our
construction.
Joint work with Rüdiger Göbel (Essen)
- 19.5.2010, 15:15 Uhr, Johannisgasse 26, 4-42
Christian Mathissen ( Universität
Leipzig):
Compressed Conjugacy and the Word Problem for Outer Automorphism
Groups of Graph Groups -
Similar to a trace monoid, a graph group is given by a finite
undirected graph (G,I), where G is the set of generators and every
edge (a,b) in I gives rise to a commutation relation ab=ba. We study
the conjugacy problem, i.e. the decision problem whether two given
words u,v over G represent conjugated elements in the graph group. We
also study an extension, the so-called simultaneous conjugacy problem.
We show that for graph groups the conjugacy problem as well as a
restricted version of the simultaneous conjugacy problem can be solved
in polynomial time even if input words are represented in a compressed
form. As a consequence it follows that the word problem for the outer
automorphism group of a graph group can be solved in polynomial time.
(Joint work with Niko Haubold and Markus Lohrey)
- 11.5.2010, 9:30 Uhr, Johannisgasse 26, 4-42
Martin Huschenbett (Universität Leipzig):
A Kleene-Schützenberger theorem for trace series over strong bimonoids -
We study weighted trace automata with weights in strong bimonoids.
Traces are a generalization of words that allow to model concurrency and
strong bimonoids are algebraic structures that can be regarded as
"semirings without distributivity", e.g. non-distributive lattices. We
show that if both operations of the bimonoid are locally finite the
classes of recognizable and mc-rational trace series coincide and, in
general, are properly contained in the class of c-rational series. We
further prove the coincidence of all three classes under the additional
assumption of commutativity and idempotence of the strong bimonoid.
- 28.4.2010, 15:15 Uhr, Johannisgasse 26, 4-42
Jiamou
Liu (University of Auckland und Universität
Leipzig):
The Isomorphism Problem for ω-Automatic Trees -
We study ω-automatic trees of finite height. These trees can be coded by ω-words in such a way that their domains and edge relations are recognized by Büchi automata. Such a tree is injectively ω-automatic if each node is represented by a unique ω-word. We present several results on the isomorphism problem for (injectively) ω-automatic trees of finite height: (i) The isomorphism problem for (injectively) ω-automatic trees of height 1 (resp. 2) is decidable (resp. Π10-complete). (ii) The isomorphism problem for injectively ω-automatic trees of height 3 is Π11-hard. (iii) The isomorphism problem for (injectively) ω-automatic trees of finite height is at least as hard as second-order arithmetic and does therefore not belong to the analytical hierarchy. Moreover, assuming the continuum hypothesis, we can show that the isomorphism problem for (injectively) ω-automatic trees of finite height is interreducible with second-order arithmetic. All proofs are elementary and do not rely on theorems from set theory.
- 21.4.2010, 15:15 Uhr, Johannisgasse
26, 4-42
Thomas
Weidner (Universität Leipzig):
On
the size of injective tree automatic representations and the
complexity of their computation -
It has been shown that every
tree automatic structure admits an injective tree automatic
representation, but no good size or time bounds are known. We
construct, given an arbitrary tree automatic representation as
input, an injective one in single exponential time. Furthermore
we show an exponential lower bound for the size of injective tree
automatic representations.
-