Page 1 Next

Displaying 1 – 20 of 942

Showing per page

3 x + 1 minus the + .

Monks, Kenneth G. (2002)

Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]

A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-Automata

Daniel Kirsten (2008)

RAIRO - Theoretical Informatics and Applications

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 S -Automatic Sequences

Emilie Charlier, Tomi Kärki, Michel Rigo (2009)

Actes des rencontres du CIRM

An infinite word is S -automatic if, for all n 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 2 , we state that a multidimensional infinite word x : d Σ over a finite alphabet Σ is S -automatic for some abstract numeration...

A characterization of poly-slender context-free languages

Lucian Ilie, Grzegorz Rozenberg, Arto Salomaa (2010)

RAIRO - Theoretical Informatics and Applications

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 𝒪 ( n k ) . 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 conjecture on the concatenation product

Jean-Eric Pin, Pascal Weil (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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

Jean-Eric Pin, Pascal Weil (2010)

RAIRO - Theoretical Informatics and Applications

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....

Currently displaying 1 – 20 of 942

Page 1 Next