-
Chapter
Characterizing Morphic Sequences
Morphic sequences form a natural class of infinite sequences, extending the well-studied class of automatic sequences. Where automatic sequences are known to have several equivalent characterizations and the c...
-
Article
Open AccessCorrection: The paint pot problem and common multiples in monoids
-
Article
Open AccessThe paint pot problem and common multiples in monoids
Illustrated by a problem on paint pots that is easy to understand but hard to solve, we investigate whether particular monoids have the property of common right multiples. As one result we characterize general...
-
Chapter
Passive Automata Learning: DFAs and NFAs
It is a natural question to find a DFA or NFA for which a given set of words should be accepted and another given set should not be accepted. In this short note we investigate how to find a smallest automaton ...
-
Chapter and Conference Paper
Deadlock in Packet Switching Networks
A deadlock in a packet switching network is a state in which one or more messages have not yet reached their target, yet cannot progress any further. We formalize three different notions of deadlock in the con...
-
Chapter and Conference Paper
Complexity of Automatic Sequences
Automatic sequences can be defined by DFAs with output (DFAO) in two natural ways. We propose to consider the minimal size of a corresponding DFAO as the complexity measure of the automatic sequence, for both ...
-
Chapter and Conference Paper
DFAs and PFAs with Long Shortest Synchronizing Word Length
It was conjectured by Černý in 1964, that a synchronizing DFA on n states always has a synchronizing word of length at most $$...
-
Chapter and Conference Paper
Finding DFAs with Maximal Shortest Synchronizing Word Length
It was conjectured by Černý in 1964 that a synchronizing DFA on n states always has a shortest synchronizing word of length at most ...
-
Chapter and Conference Paper
Classifying Non-periodic Sequences by Permutation Transducers
Transducers order infinite sequences into natural classes, but permutation transducers provide a finer classification, respecting certain changes to finite segments. We investigate this hierarchy for non-perio...
-
Chapter and Conference Paper
Using SMT for Solving Fragments of Parameterised Boolean Equation Systems
Fixpoint logics such as parameterised Boolean equation systems (PBESs) provide a unifying framework in which a number of practical decision problems can be encoded. Efficient evaluation methods (solving methods i...
-
Chapter and Conference Paper
Proving Termination of Graph Transformation Systems Using Weighted Type Graphs over Semirings
We introduce techniques for proving uniform termination of graph transformation systems, based on matrix interpretations for string rewriting. We generalize this technique by adapting it to graph rewriting ins...
-
Chapter and Conference Paper
The Degree of Squares is an Atom
We answer an open question in the theory of degrees of infinite sequences with respect to transducibilityby finite-state transducers. An initial study of this partial order of degrees was carried out in [1], but ...
-
Chapter and Conference Paper
Termination Analysis for Graph Transformation Systems
We introduce two techniques for proving termination of graph transformation systems. We do not fix a single initial graph, but consider arbitrary initial graphs (uniform termination), but also certain sets of ...
-
Chapter and Conference Paper
Termination of Cycle Rewriting
String rewriting can not only be applied on strings, but also on cycles and even on general graphs. In this paper we investigate termination of string rewriting applied on cycles, shortly denoted as cycle rewr...
-
Chapter and Conference Paper
Erratum: Cinderella versus the Wicked Stepmother
The name of the first author of the paper starting on page 57 of this volume has been printed incorrectly. It should read: Marijke H.L. Bodlaender
-
Chapter and Conference Paper
Cinderella versus the Wicked Stepmother
We investigate a combinatorial two-player game, in which one player wants to keep the behavior of an underlying water-bucket system stable whereas the other player wants to cause overflows. This game is motiva...
-
Chapter and Conference Paper
Complexity of Guided Insertion-Deletion in RNA-Editing
Inspired by RNA-editing, we study an elementary formalism of string replacement based on insertion and deletion using a fixed finite set of guides, and in which only occurrences of a single symbol are inserted or...
-
Chapter and Conference Paper
Well-Definedness of Streams by Termination
Streams are infinite sequences over a given data type. A stream specification is a set of equations intended to define a stream. We propose a transformation from such a stream specification to a TRS in such a ...
-
Chapter and Conference Paper
A Tool Proving Well-Definedness of Streams Using Termination Tools
A stream specification is a set of equations intended to define a stream, that is, an infinite sequence over a given data type. In [5] a transformation from such a stream specification to a TRS is defined in s...
-
Chapter and Conference Paper
Degrees of Undecidability in Term Rewriting
Undecidability of various properties of first order term rewriting systems is well-known. An undecidable property can be classified by the complexity of the formula defining it. This gives rise to a hierarchy ...
