Displaying 521 – 540 of 948

Showing per page

On synchronized sequences and their separators

Arturo Carpi, Cristiano Maggi (2001)

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

We introduce the notion of a k -synchronized sequence, where k is an integer larger than 1. Roughly speaking, a sequence of natural numbers is said to be k -synchronized if its graph is represented, in base k , by a right synchronized rational relation. This is an intermediate notion between k -automatic and k -regular sequences. Indeed, we show that the class of k -automatic sequences is equal to the class of bounded k -synchronized sequences and that the class of k -synchronized sequences is strictly...

On synchronized sequences and their separators

Arturo Carpi, Cristiano Maggi (2010)

RAIRO - Theoretical Informatics and Applications

We introduce the notion of a k-synchronized sequence, where k is an integer larger than 1. Roughly speaking, a sequence of natural numbers is said to be k-synchronized if its graph is represented, in base k, by a right synchronized rational relation. This is an intermediate notion between k-automatic and k-regular sequences. Indeed, we show that the class of k-automatic sequences is equal to the class of bounded k-synchronized sequences and that the class of k-synchronized sequences is...

On the classes of languages accepted by limited context restarting automata

Friedrich Otto, Peter Černo, František Mráz (2014)

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

In the literature various types of restarting automata have been studied that are based on contextual rewriting. A word w is accepted by such an automaton if, starting from the initial configuration that corresponds to input w, the word w is reduced to the empty word by a finite number of applications of these contextual rewritings. This approach is reminiscent of the notion of McNaughton families of languages. Here we put the aforementioned types of restarting automata into the context of McNaughton...

On the continuity set of an Omega rational function

Olivier Carton, Olivier Finkel, Pierre Simonnet (2008)

RAIRO - Theoretical Informatics and Applications

In this paper, we study the continuity of rational functions realized by Büchi finite state transducers. It has been shown by Prieur that it can be decided whether such a function is continuous. We prove here that surprisingly, it cannot be decided whether such a function f has at least one point of continuity and that its continuity set C(f) cannot be computed. In the case of a synchronous rational function, we show that its continuity set is rational and that it can be computed. Furthermore...

On the decidability of semigroup freeness∗

Julien Cassaigne, Francois Nicolas (2012)

RAIRO - Theoretical Informatics and Applications

This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup S is defined as: given a finite subset X ⊆ S, decide whether each element of S has at most one factorization over X. To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoids....

On the decidability of semigroup freeness

Julien Cassaigne, Francois Nicolas (2012)

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

This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup S is defined as: given a finite subset X ⊆ S, decide whether each element of S has at most one factorization over X. To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoids. In 1991, Klarner, Birget and Satterfield proved the undecidability...

On the decidability of semigroup freeness∗

Julien Cassaigne, Francois Nicolas (2012)

RAIRO - Theoretical Informatics and Applications

This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup S is defined as: given a finite subset X ⊆ S, decide whether each element of S has at most one factorization over X. To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoids....

On the Decidability of the Equivalence Problem for Monadic Recursive Programs

Vladimir A. Zakharov (2010)

RAIRO - Theoretical Informatics and Applications

We present a uniform and easy-to-use technique for deciding the equivalence problem for deterministic monadic linear recursive programs. The key idea is to reduce this problem to the well-known group-theoretic problems by revealing an algebraic nature of program computations. We show that the equivalence problem for monadic linear recursive programs over finite and fixed alphabets of basic functions and logical conditions is decidable in polynomial time for the semantics based on the free monoids...

Currently displaying 521 – 540 of 948