### $\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')

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.

In a previous paper, the authors studied the polynomial closure of a variety of languages and gave an algebraic counterpart, in terms of Mal’cev products, of this operation. They also formulated a conjecture about the algebraic counterpart of the boolean closure of the polynomial closure – this operation corresponds to passing to the upper level in any concatenation hierarchy. Although this conjecture is probably true in some particular cases, we give a counterexample in the general case. Another...

In a previous paper, the authors studied the polynomial closure of a variety of languages and gave an algebraic counterpart, in terms of Mal'cev products, of this operation. They also formulated a conjecture about the algebraic counterpart of the boolean closure of the polynomial closure – this operation corresponds to passing to the upper level in any concatenation hierarchy. Although this conjecture is probably true in some particular cases, we give a counterexample in the general case....