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 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 combinatorial theorem on -power-free words and an application to semigroups
A conjecture on the concatenation product
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...
A conjecture on the concatenation product
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....
A continuous family of automata : the Ising automata
A contribution to the top-to-bottom recognizer rehabilitation
A criterion for non-automaticity of sequences.
A decision method for the recognizability of sets defined by number systems
A deterministic subclass of context-free languages
A fast algorithm to decide on the equivalence of stateless DPDA
A finiteness property and an automatic structure for Coxeter groups.
A general framework for the derivation of regular expressions
The aim of this paper is to design a theoretical framework that allows us to perform the computation of regular expression derivatives through a space of generic structures. Thanks to this formalism, the main properties of regular expression derivation, such as the finiteness of the set of derivatives, need only be stated and proved one time, at the top level. Moreover, it is shown how to construct an alternating automaton associated with the derivation of a regular expression in this general framework....
A generalization of configurations in the sense of Gladkij
A generalization of the propositional calculus for purposes of the theory of logical nets with probabilistic elements