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

Viliam Geffert; L'ubomíra Ištoňová

Displaying similar documents to “Translation from classical two-way automata to pebble two-way automata”

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

Coalgebras for Binary Methods: Properties of Bisimulations and Invariants

Hendrik Tews (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Coalgebras for endofunctors $𝒞 \to 𝒞$ can be used to model classes of object-oriented languages. However, binary methods do not fit directly into this approach. This paper proposes an extension of the coalgebraic framework, namely the use of $𝒞^{o p} \times 𝒞 \to 𝒞$ . This extension allows the incorporation of binary methods into coalgebraic class specifications. The paper also discusses how to define bisimulation and invariants for coalgebras of extended polynomial functors and proves many...

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

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.

Improved Lower Bounds on the Approximability of the Traveling Salesman Problem

Hans-Joachim Böckenhauer, Sebastian Seibert (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

This paper deals with lower bounds on the approximability of different subproblems of the Traveling Salesman Problem (TSP) which is known not to admit any polynomial time approximation algorithm in general (unless $𝒫 = 𝒩𝒫$ ). First of all, we present an improved lower bound for the Traveling Salesman Problem with Triangle Inequality, -TSP for short. Moreover our technique, an extension of the method of Engebretsen [11], also applies to the case of relaxed and sharpened triangle inequality, respectively,...