Ludwig Staiger

TCS Journal 2023 Journal Article

Frontiers of Computability, Randomness, and Complexity (dedicated to the 70th birthday of Professor Cristian Calude)

• Alastair A. Abbott
• Cezar Câmpeanu
• Ludwig Staiger
• Marius Zimand
• Arto Salomaa

TCS Journal 2021 Journal Article

Automata for solid codes

• Helmut Jürgensen
• Ludwig Staiger

Solid codes provide outstanding fault-tolerance when used for information transmission through a noisy channel involving not only symbol substitutions, but also synchronisation errors and black-outs. In this paper we provide an automaton theoretic characterisation of solid codes which takes this fault-tolerance into account. The fault-tolerance afforded by a solid code L can be summarised as follows: Consider messages, encoded using L, being sent through a noisy channel. Any code words in L, which are present in the received message, will be decoded correctly, unless they themselves happen to be the results of errors. Thus, errors in the received message will not lead to incorrect decodings of those parts which are error-free. In this paper we consider acceptors which are fault-tolerant in this sense when analysing such received messages. These acceptors characterise the class of solid codes. For finite solid codes an automaton characterisation was published in the sixties by Levenshtein and Romanov. The characterisation uses state-invariant finite-state transducers which act as decoders in such a way that an output is generated exactly when a code word has been read completely. State-invariance means that acceptance does not depend on the initial state — every state can be used as the initial state. The results of Levenshtein and Romanov depend strongly on the fact that the code is finite. In this paper we provide a general automaton theoretic characterisation of arbitrary solid codes without any such restriction. Moreover, the solid code is regular as a language if and only if the automaton used in the characterisation can be reduced to an equivalent finite automaton with equivalent properties. The main results of this paper are as follows: Every acceptor defines a solid code. For every solid code there is a fault-tolerant acceptor defining the code. Such acceptors expose the decomposition of potentially faulty received messages according to the code. For solid codes which are regular as languages these acceptors can be chosen to be finite while preserving all important combinatorial properties. Part of this work was presented at the 14th Journées Montoises of Theoretical Computer Science [32].

TCS Journal 2021 Journal Article

Bi-immunity over different size alphabets

• Cristian S. Calude
• Karen Frilya Celine
• Ziyuan Gao
• Sanjay Jain
• Ludwig Staiger
• Frank Stephan

In this paper we study various notions of bi-immunity over alphabets with b ≥ 2 elements and recursive transformations between sequences on different alphabets which preserve them. Furthermore, we extend the study from sequences bounded by a constant to sequences over the alphabet of all natural numbers, which may or may not be bounded by a recursive function, and relate them to the Turing degrees in which they can occur.

TCS Journal 2017 Journal Article

Shift-invariant topologies for the Cantor space X

• Stefan Hoffmann
• Sibylle Schwarz
• Ludwig Staiger

The space of one-sided infinite words plays a crucial rôle in several parts of Theoretical Computer Science. Usually, it is convenient to regard this space as a metric space, the Cantor space. It turned out that for several purposes topologies other than the one of the Cantor space are useful, e. g. for studying fragments of first-order logic over infinite words or for a topological characterisation of random infinite words. It is shown that these topologies refine the topology of the Cantor space. Moreover, from common features of these topologies we extract properties which characterise a large class of topologies. It turns out that, for this general class of topologies, the corresponding closure and interior operators respect the shift operations and also, to some extent, the definability of sets of infinite words by finite automata.

I&C Journal 2016 Journal Article

Finite state incompressible infinite sequences

• Cristian S. Calude
• Ludwig Staiger
• Frank Stephan

In this paper we define and study finite state complexity of finite strings and infinite sequences as well as connections between these complexity notions to randomness and normality. We show that the finite state complexity does not only depend on the codes for finite transducers, but also on how the codes are mapped to transducers. As a consequence we relate the finite state complexity to the plain (Kolmogorov) complexity, to the process complexity and to prefix-free complexity. Working with prefix-free sets of codes we characterise Martin-Löf random sequences in terms of finite state complexity: the weak power of finite transducers is compensated by the high complexity of enumeration of finite transducers. We also prove that every finite state incompressible sequence is normal, but the converse implication is not true. These results also show that our definition of finite state incompressibility is stronger than all other known forms of finite automata based incompressibility, in particular the notion related to finite automaton based betting systems introduced by Schnorr and Stimm. The paper concludes with a discussion of open questions.

TCS Journal 2011 Journal Article

Universal recursively enumerable sets of strings

• Cristian S. Calude
• André Nies
• Ludwig Staiger
• Frank Stephan

The main topics of the present work are universal machines for plain and prefix-free description complexity and their domains. It is characterised when an r. e. set W is the domain of a universal plain machine in terms of the description complexity of the spectrum function s W mapping each non-negative integer n to the number of all strings of length n in W; furthermore, a characterisation of the same style is given for supersets of domains of universal plain machines. Similarly the prefix-free sets which are domains or supersets of domains of universal prefix-free machines are characterised. Furthermore, it is shown that the halting probability Ω V of an r. e. prefix-free set V containing the domain of a universal prefix-free machine is Martin-Löf random, while V may not be the domain of any universal prefix-free machine itself. Based on these investigations, the question whether every domain of a universal plain machine is the superset of the domain of some universal prefix-free machine is discussed. A negative answer to this question had been presented at CiE 2010 by Mikhail Andreev, Ilya Razenshteyn and Alexander Shen, while this paper was under review.

TCS Journal 2009 Journal Article

Topology on words

• Cristian S. Calude
• Helmut Jürgensen
• Ludwig Staiger

We investigate properties of topologies on sets of finite and infinite words over a finite alphabet. The guiding example is the topology generated by the prefix relation on the set of finite words, considered as a partial order. This partial order extends naturally to the set of infinite words; hence it generates a topology on the union of the sets of finite and infinite words. We consider several partial orders which have similar properties and identify general principles according to which the transition from finite to infinite words is natural. We provide a uniform topological framework for the set of finite and infinite words to handle limits in a general fashion.

TCS Journal 2007 Journal Article

Finite automata encoding geometric figures

• Helmut Jürgensen
• Ludwig Staiger
• Hideki Yamasaki

Finite automata are used for the encoding and compression of images. For black-and-white images, for instance, using the quad-tree representation, the black points correspond to ω -words defining the corresponding paths in the tree that lead to them. If the ω -language consisting of the set of all these words is accepted by a deterministic finite automaton then the image is said to be encodable as a finite automaton. For grey-level images and colour images similar representations by automata are in use. In this paper we address the question of which images can be encoded as finite automata with full infinite precision. In applications, of course, the image would be given and rendered at some finite resolution–this amounts to considering a set of finite prefixes of the ω -language–and the features in the image would be approximations of the features in the infinite precision rendering. We focus on the case of black-and-white images–geometrical figures, to be precise–but treat this case in a d -dimensional setting, where d is any positive integer. We show that among all polygons and convex polyhedra in d -dimensional space exactly those with rational corner points are encodable as finite automata. In the course of proving this we show that the set of images encodable as finite automata is closed under rational affine transformations. Several properties of images encodable as finite automata are consequences of this result. Finally we show that many simple geometric figures such as circles and parabolas are not encodable as finite automata.

TCS Journal 2007 Journal Article

The Kolmogorov complexity of infinite words

• Ludwig Staiger

We present a brief survey of results on relations between the Kolmogorov complexity of infinite strings and several measures of information content (dimensions) known from dimension theory, information theory or fractal geometry. Special emphasis is placed on bounds on the complexity of strings in constructively given subsets of the Cantor space. Finally, we compare the Kolmogorov complexity to the subword complexity of infinite strings.

TCS Journal 2002 Journal Article

The Kolmogorov complexity of real numbers

• Ludwig Staiger

We consider for a real number α the Kolmogorov complexities of its expansions with respect to different bases. In the paper it is shown that, for usual and self-delimiting Kolmogorov complexity, the complexity of the prefixes of their expansions with respect to different bases r and b are related in a way that depends only on the relative information of one base with respect to the other. More precisely, we show that the complexity of the length l·log r b prefix of the base r expansion of α is the same (up to an additive constant) as the log r b-fold complexity of the length l prefix of the base b expansion of α. Then we consider the classes of reals of maximum and minimum complexity. For maximally complex reals we use our result to derive a further complexity theoretic proof for the base independence of the randomness of real numbers. Finally, we consider Liouville numbers as a natural class of low complex real numbers.

I&C Journal 2001 Journal Article

Iterated Function Systems and Control Languages

• Henning Fernau
• Ludwig Staiger

Valuations—morphisms from (Σ*, ·, e) to ((0, ∞), ·, 1)—are a generalization of Bernoulli morphisms introduced by Eilenberg [“Automata, Languages, and Machines”, Academic Press, New York, 1974]. Here, we show how to generalize the notion of entropy (of a language) in order to obtain new formulas to determine the Hausdorff dimension of fractal sets (also in Euclidean spaces), especially defined via regular (ω-)languages. By doing this, we can sharpen and generalize earlier results in two ways: first, we treat the case where the underlying basic iterated function system contains noncontractive mappings and, second, we obtain results valid for nonregular languages as well.

MFCS Conference 1998 Conference Paper

IFS and Control Languages

• Henning Fernau
• Ludwig Staiger

Abstract Valuations — morphisms from (σ *, ·, e ) to ((0, ∞), ·, 1) —are a generalization of Bernoulli morphisms introduced in [7]. Here, we show how to generalize the notion of entropy (of a language) in order to obtain new formulae to determine the Hausdorff dimension of fractal sets (also in Euclidean spaces) especially defined via regular Ω-languages. In this way, we can sharpen and generalize earlier results [1, 10, 11, 20, 29].

CSL Conference 1998 Conference Paper

Rich omega-Words and Monadic Second-Order Arithmetic

• Ludwig Staiger

Abstract Rich ω -words are one-sided infinite strings which have every finite word as a subword (infix). Infix-regular w-words are one-sided infinite strings for which the infix set of a suffix is a regular language. We show that for a regular ω -language F (a set of predicates definable in Büchi's restricted monadic second order arithmetic) the following conditions are equivalent: 1. F contains a rich ω -word. 2. F is of second Baire category in the Cantor space of ω -words. 3. F is a non-nullset for a class of measures (including the natural Lebesgue measure on Cantor space). 4. F has maximum Hausdorff dimension. This shows that, although we cannot fully translate Compton's result (Theorem 1 below) on rich ℤ-words (in the MSO theory of the integers) 2 to MSO arithmetic on naturals, a set definable in MSO arithmetic and containing a rich w-word is large in several respects simultaneously. Moreover, we show under the assumption of an exchanging property for ‘distinguishing’ prefixes that two regular w-words not necessarily being rich but having the same sets of infixes occurring infinitely often are indistinguishable by MSO formulas or, equivalently, by finite automata.

TCS Journal 1997 Journal Article

Finite acceptance of infinite words

• Igor Litovsky
• Ludwig Staiger

In this paper we consider the following two types of finite acceptance of infinite words by finite automata: An infinite word ξ is accepted if and only if there is a run on input ξ for which 1. (1) an accepting state is visited at least once, or 2. (2) an accepting state is visited at least once but only finitely often. The resulting classes of regular ω-languages are characterized by language-theoretic means, and they are positioned into the known hierarchies of regular ω-languages.

TCS Journal 1997 Journal Article

On syntactic congruences for ω-languages

• Oded Maler
• Ludwig Staiger

In this paper we investigate several questions related to syntactic congruences and to minimal automata associated with ω-languages. In particular we investigate relationships between the so-called simple (because it is a simple translation from the usual definition in the case of finitary languages) syntactic congruence and its infinitary refinement (the iteration congruence) investigated by Arnold (Theoret. Comput. Sci. 39 (1985) 333–335). We show that in both cases not every ω-language having a finite syntactic monoid is regular and we give a characterization of those ω-languages having finite syntactic monoids. Among the main results we derive a condition which guarantees that the simple syntactic congruence and Arnold's syntactic congruence coincide and show that all (including infinitestate) ω-languages in the Borel class Fσ∩G δ satisfy this condition. We also show that all ω-languages in this class are accepted by their minimal-state automaton — provided they are accepted by any Muller automaton. Finally we develop an alternative theory of recognizability of ω-languages by families of right-congruence relations, and define a canonical object (much smaller then Arnold's monoid) associated with every ω-language. Using this notion of recognizability we give a necessary and sufficient condition for a regular ω-language to be accepted by its minimal-state automaton.

TCS Journal 1988 Journal Article

Ein satz über die entropie von untermonoiden

• Ludwig Staiger

Let X be a finite alphabet. For L ⊆ X ∗ let ϱ L denote the radius of convergence of the structure generating function sL: = σ n=0 ∞ card(L∩Xn)·tn of the language L. The entropy of L is defined as H L: = -logcardX ϱ L. We shall prove the following proposition: Theorem. Let L be an arbitrary subset of X ∗. Then for every ϵ > 0 there is a finite subset U of L such that H L ∗ − H U ∗ < ϵ.

MFCS Conference 1986 Conference Paper

The Centers of Context-Sensitive Languages

• Ludwig Staiger
• Werner Nehrlich

TCS Journal 1984 Journal Article

Projection lemmas for ω-languages

• Ludwig Staiger

The paper presents projection lemmas relating the infinite behaviour of deterministic and unboundedly branching nondeterministic infinite automata.

MFCS Conference 1981 Conference Paper

Complexity and Entropy

• Ludwig Staiger

MFCS Conference 1975 Conference Paper

Finite Automata Acceptation of Infinite Sequences

• Klaus W. Wagner
• Ludwig Staiger