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

Sylvain Lombardy; Jean Mairesse

Displaying similar documents to “Series which are both max-plus and min-plus rational are unambiguous”

Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations

Olivier Finkel (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We prove that for every countable ordinal one cannot decide whether a given infinitary rational relation is in the Borel class $Σ_{α}^{0}$ (respectively $Π_{α}^{0}$ ). Furthermore one cannot decide whether a given infinitary rational relation is a Borel set or a $Σ_{1}^{1}$ -complete set. We prove some recursive analogues to these properties. In particular one cannot decide whether an infinitary rational relation is an arithmetical set. We then deduce from the proof of these results some other ones, like: one cannot...

Translation from classical two-way automata to pebble two-way automata

Viliam Geffert, L'ubomíra Ištoňová (2011)

RAIRO - Theoretical Informatics and Applications

Similarity:

We study the relation between the standard two-way automata and more powerful devices, namely, two-way finite automata equipped with some $ℓ$ additional “pebbles” that are movable along the input tape, but their use is restricted (nested) in a stack-like fashion. Similarly as in the case of the classical two-way machines, it is not known whether there exists a polynomial trade-off, in the number of states, between the nondeterministic and deterministic two-way automata with $ℓ$ nested pebbles....

A note on Coinduction and Weak Bisimilarity for While Programs

J. J.M.M. Rutten (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

An illustration of coinduction in terms of a notion of weak bisimilarity is presented. First, an operational semantics $𝒪$ for while programs is defined in terms of a final automaton. It identifies any two programs that are weakly bisimilar, and induces in a canonical manner a compositional model $𝒟$ . Next $𝒪 = 𝒟$ is proved by coinduction.

The Helping Hierarchy

Patrizio Cintioli, Riccardo Silvestri (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Schöning [14] introduced a notion of helping and suggested the study of the class $P_{help} (𝒞)$ of the languages that can be helped by oracles in a given class $𝒞$ . Later, Ko [12], in order to study the connections between helping and "witness searching" , introduced the notion of self-helping for languages. We extend this notion to classes of languages and show that there exists a self-helping class that we call SH which contains all the self-helping classes. We introduce the Helping hierarchy whose levels...

Threshold Circuits for Iterated Matrix Product and Powering

Carlo Mereghetti, Beatrice Palano (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

The complexity of computing, via threshold circuits, the and of fixed-dimension $k \times k$ matrices with integer or rational entries is studied. We call these two problems ${𝖨𝖬𝖯}_{𝗄}$ and ${𝖬𝖯𝖮𝖶}_{𝗄}$ , respectively, for short. We prove that: (i) For $k \geq 2$ , ${𝖨𝖬𝖯}_{𝗄}$ does not belong to ${TC}^{0}$ , unless ${TC}^{0} = {NC}^{1}$ .newline (ii) For : ${𝖨𝖬𝖯}_{2}$ belongs to ${TC}^{0}$ while, for $k \geq 3$ , ${𝖨𝖬𝖯}_{𝗄}$ does not belong to ${TC}^{0}$ , unless ${TC}^{0} = {NC}^{1}$ . (iii) For any , ${𝖬𝖯𝖮𝖶}_{𝗄}$ belongs to ${TC}^{0}$ .