-regular languages defined by a limit operator.
minus the .
5-abelian cubes are avoidable on binary alphabets
A k-abelian cube is a word uvw, where the factors u, v, and w are either pairwise equal, or have the same multiplicities for every one of their factors of length at most k. Previously it has been shown that k-abelian cubes are avoidable over a binary alphabet for k ≥ 8. Here it is proved that this holds for k ≥ 5.
-пространства.
A bound for the -equivalence problem of polynomial D0L systems
We give a bound for the -equivalence problem of polynomially bounded D0L systems which depends only on the size of the underlying alphabet.
A bound for the ω-equivalence problem of polynomial D0L systems
We give a bound for the ω-equivalence problem of polynomially bounded D0L systems which depends only on the size of the underlying alphabet.
A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata
We show that the termination of Mohri's algorithm is decidable for polynomially ambiguous weighted finite automata over the tropical semiring which gives a partial answer to a question by Mohri [29]. The proof relies on an improvement of the notion of the twins property and a Burnside type characterization for the finiteness of the set of states produced by Mohri's algorithm.
A cellular automaton model of brain tumor treatment and resistance.
A cellular automaton on a torus.
A characterization of harmonic languages
A Characterization of Multidimensional -Automatic Sequences
An infinite word is -automatic if, for all , its st letter is the output of a deterministic automaton fed with the representation of in the considered numeration system . In this extended abstract, we consider an analogous definition in a multidimensional setting and present the connection to the shape-symmetric infinite words introduced by Arnaud Maes. More precisely, for , we state that a multidimensional infinite word over a finite alphabet is -automatic for some abstract numeration...
A characterization of poly-slender context-free languages
A characterization of poly-slender context-free languages
For a non-negative integer k, we say that a language L is k-poly-slender if the number of words of length n in L is of order . We give a precise characterization of the k-poly-slender context-free languages. The well-known characterization of the k-poly-slender regular languages is an immediate consequence of ours.
A characterization of rational star languages generated by strong codes.
A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations
A classification of rational languages by semilattice-ordered monoids
We prove here an Eilenberg type theorem: the so-called conjunctive varieties of rational languages correspond to the pseudovarieties of finite semilattice-ordered monoids. Taking complements of members of a conjunctive variety of languages we get a so-called disjunctive variety. We present here a non-trivial example of such a variety together with an equational characterization of the corresponding pseudovariety.
A coalgebraic semantics of subtyping
Coalgebras have been proposed as formal basis for the semantics of objects in the sense of object-oriented programming. This paper shows that this semantics provides a smooth interpretation for subtyping, a central notion in object-oriented programming. We show that different characterisations of behavioural subtyping found in the literature can conveniently be expressed in coalgebraic terms. We also investigate the subtle difference between behavioural subtyping and refinement.
A Coalgebraic Semantics of Subtyping
Coalgebras have been proposed as formal basis for the semantics of objects in the sense of object-oriented programming. This paper shows that this semantics provides a smooth interpretation for subtyping, a central notion in object-oriented programming. We show that different characterisations of behavioural subtyping found in the literature can conveniently be expressed in coalgebraic terms. We also investigate the subtle difference between behavioural subtyping and refinement.
A coalgebraic view on reachability
Coalgebras for an endofunctor provide a category theoretic framework for modeling a wide range of state-based systems of various types. We provide an iterative construction of the reachable part of a given pointed coalgebra that is inspired by and resembles the standard breadth-first search procedure to compute the reachable part of a graph. We also study coalgebras in Kleisli categories: for a functor extending a functor on the base category, we show that the reachable part of a given pointed coalgebra...
A coin tossing algorithm for counting large numbers of events