Helmut Jürgensen

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 2017 Journal Article

Higher-level constructs for families and multisets

• Helmut Jürgensen

In an earlier paper we argued that the concept of multisets should be based on families, that is, on sets and functions between sets, rather than, as usual, on sets and cardinal numbers. We showed how certain fundamental problems regarding the distinguishablity of objects as well as unexpected anomalies of the basic operations of union, intersection, and complement can be avoided elegantly using families rather than multisets. On the other hand, there is a trivial mapping of families to multisets. Hence, using families does not introduce any significant formal complications. The difficulties with the usual definition of multisets by multiplicities reach beyond the philosophical or metamathematical foundations. For the basic operations one can find acceptable compromises. For higher-level set constructs like Cartesian products, projections, relations, functions, or the power set the multiset counterparts are rather contrived, and many of the constructions leave the strict definition of multisets, actually introducing family-like constructs through a back door. In the earlier paper we proposed to use families instead of multisets to resolve the basic problems. In this paper we show that families instead of multisets support the higher-level constructions even, when no appropriate multiset-based constructions exist. We also show that multisets form a category and that the natural mapping from families to multisets is a functor. This emphasizes our claim that, for a definition of multisets, one should start with families and only introduce multiplicities as a secondary concept.

TCS Journal 2016 Journal Article

Descriptional Complexity of Formal Systems

• Helmut Jürgensen
• Juhani Karhumäki
• Alexander Okhotin

TCS Journal 2014 Journal Article

Graph transformation for incremental natural language analysis

• Suna Bensch
• Frank Drewes
• Helmut Jürgensen
• Brink van der Merwe

Millstream systems have been proposed as a non-hierarchical method for modelling natural language. Millstream configurations represent and connect multiple structural aspects of sentences. We present a method by which the Millstream configurations corresponding to a sentence are constructed. The construction is incremental, that is, it proceeds as the sentence is being read and is complete when the end of the sentence is reached. It is based on graph transformations and a lexicon which associates words with graph transformation rules that implement the incremental construction process. Our main result states that, for an effectively nonterminal-bounded reader R and a Millstream system MS based on monadic second-order logic, the correctness of R with respect to MS can be checked: it is decidable whether all graphs generated by R belong to the language of configurations specified by MS.

TCS Journal 2012 Journal Article

Relativized codes

• Mark Daley
• Helmut Jürgensen
• Lila Kari
• Kalpana Mahalingam

A code C over an alphabet Σ is a set of words such that every word in C + has a unique factorization over C, that is, a unique C -decoding. When not all words in C + appear as messages, a weaker notion of unique factorization can be used. Thus we consider codes C relative to a given set of messages L, such that each word in L has a unique C -decoding. We extend this idea of relativizing code concepts to restricted message spaces. In general terms, from a predicate P defining a class of codes, P -codes, we derive a relativized version of such codes, P -codes relative to a given language L. In essence, C ⊆ Σ + is a P -code relative to L ⊆ Σ + if P is true on its domain restricted to L. This systematic approach leads to the relativization of the definitions of many classes of codes, including prefix, suffix, bifix and solid codes. It can also be applied to certain classes of languages, like overlap-free languages, which are not codes, but which can be defined using a similar logical framework. In this paper, we explore the mechanism of this relativization and compare it to other existing methods for relativizing code properties to restricted message spaces.

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.

I&C Journal 2008 Journal Article

Synchronization

• Helmut Jürgensen

Synchronization of a system can be achieved by applying an input sequence which causes the system to enter a known state. We survey synchronization issues from the points of view of automaton and coding theory. A connection between properties of codes and synchronizing words is established which may offer a new view of Černý’s conjecture.

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.