Displaying similar documents to “Logic and p -recognizable sets of integers.”

Corrigendum to our paper: How Expressions Can Code for Automata

Sylvain Lombardy, Jacques Sakarovitch (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

In a previous paper, we have described the construction of an automaton from a rational expression which has the property that the automaton built from an expression which is itself computed from a co-deterministic automaton by the state elimination method is co-deterministic. It turned out that the definition on which the construction is based was inappropriate, and thus the proof of the property was flawed. We give here the correct definition of the broken derived terms...

A Hierarchy of Automatic -Words having a Decidable MSO Theory

Vince Bárány (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

We investigate automatic presentations of -words. Starting points of our study are the works of Rigo and Maes, Caucal, and Carton and Thomas concerning lexicographic presentation, MSO-interpretability in algebraic trees, and the decidability of the MSO theory of morphic words. Refining their techniques we observe that the lexicographic presentation of a (morphic) word is in a certain sense canonical. We then generalize our techniques to a hierarchy of classes of -words enjoying...

Highly Undecidable Problems For Infinite Computations

Olivier Finkel (2009)

RAIRO - Theoretical Informatics and Applications

Similarity:

We show that many classical decision problems about -counter -languages, context free -languages, or infinitary rational relations, are Π½ -complete, hence located at the second level of the analytical hierarchy, and “highly undecidable”. In particular, the universality problem, the inclusion problem, the equivalence problem, the determinizability problem, the complementability problem, and the unambiguity problem are all Π½ -complete for context-free -languages or for infinitary...

Decision problems among the main subfamilies of rational relations

Olivier Carton, Christian Choffrut, Serge Grigorieff (2006)

RAIRO - Theoretical Informatics and Applications

Similarity:

We consider the four families of recognizable, synchronous, deterministic rational and rational subsets of a direct product of free monoids. They form a strict hierarchy and we investigate the following decision problem: given a relation in one of the families, does it belong to a smaller family? We settle the problem entirely when all monoids have a unique generator and fill some gaps in the general case. In particular, adapting a proof of Stearns, we show that it is recursively decidable whether...

Series which are both max-plus and min-plus rational are unambiguous

Sylvain Lombardy, Jean Mairesse (2006)

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

Similarity:

Consider partial maps Σ * → ℝ with a rational domain. We show that two families of such series are actually the same: the unambiguous rational series on the one hand, and the max-plus and min-plus rational series on the other hand. The decidability of equality was known to hold in both families with different proofs, so the above unifies the picture. We give an effective procedure to build an unambiguous automaton from a max-plus automaton and a min-plus one...

How expressions can code for automata

Sylvain Lombardy, Jacques Sakarovitch (2005)

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

Similarity:

In this paper we investigate how it is possible to recover an automaton from a rational expression that has been computed from that automaton. The notion of derived term of an expression, introduced by Antimirov, appears to be instrumental in this problem. The second important ingredient is the co-minimization of an automaton, a dual and generalized Moore algorithm on non-deterministic automata. We show here that if an automaton is then sufficiently “decorated”, the combination of these...