### $\infty $-regular languages defined by a limit operator.

Skip to main content (access key 's'),
Skip to navigation (access key 'n'),
Accessibility information (access key '0')

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.

We give a bound for the $\omega $-equivalence problem of polynomially bounded D0L systems which depends only on the size of the underlying alphabet.

We give a bound for the ω-equivalence problem of polynomially bounded D0L systems which depends only on the size of the underlying alphabet.

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.

An infinite word is $S$-automatic if, for all $n\ge 0$, its $(n+1)$st letter is the output of a deterministic automaton fed with the representation of $n$ in the considered numeration system $S$. 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 $d\ge 2$, we state that a multidimensional infinite word $x:{\mathbb{N}}^{d}\to \Sigma $ over a finite alphabet $\Sigma $ is $S$-automatic for some abstract numeration...

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 $\mathcal{O}\left({n}^{k}\right)$. 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.

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.

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.