Page 1 Next

Displaying 1 – 20 of 23

Showing per page

Una introducción a la W-calculabilidad: Operaciones básicas.

Buenaventura Clares Rodríguez (1983)

Stochastica

Our purpose is to introduce the W-composition, W-minimalization and W-primitive recursion operations as operations between W-valued functions, where W denotes the ordered semiring ([0,1],+,≤). We prove that: 1) the set of W-calculable functions is closed under the W-composition and W-primitice recursion operations, and 2) the set of the partially W-calculable functions is closed under the W-minimalization operation.

Undecidability of infinite post correspondence problem for instances of size 8

Jing Dong, Qinghui Liu (2012)

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

The infinite Post Correspondence Problem (ωPCP) was shown to be undecidable by Ruohonen (1985) in general. Blondel and Canterini [Theory Comput. Syst. 36 (2003) 231–245] showed that ωPCP is undecidable for domain alphabets of size 105, Halava and Harju [RAIRO–Theor. Inf. Appl. 40 (2006) 551–557] showed that ωPCP is undecidable for domain alphabets of size 9. By designing a special coding, we delete a letter from Halava and Harju’s construction. So we prove that ωPCP is undecidable for domain alphabets...

Undecidability of infinite post correspondence problem for instances of size 8

Jing Dong, Qinghui Liu (2012)

RAIRO - Theoretical Informatics and Applications

The infinite Post Correspondence Problem (ωPCP) was shown to be undecidable by Ruohonen (1985) in general. Blondel and Canterini [Theory Comput. Syst. 36 (2003) 231–245] showed that ωPCP is undecidable for domain alphabets of size 105, Halava and Harju [RAIRO–Theor. Inf. Appl. 40 (2006) 551–557] showed that ωPCP is undecidable for domain alphabets of size 9. By designing a special coding, we delete a letter from Halava and Harju’s construction. So we prove that ωPCP is undecidable for domain alphabets...

Undecidability of infinite post correspondence problem for instances of Size 9

Vesa Halava, Tero Harju (2006)

RAIRO - Theoretical Informatics and Applications

In the infinite Post Correspondence Problem an instance (h,g) consists of two morphisms h and g, and the problem is to determine whether or not there exists an infinite word ω such that h(ω) = g(ω). This problem was shown to be undecidable by Ruohonen (1985) in general. Recently Blondel and Canterini (Theory Comput. Syst.36 (2003) 231–245) showed that this problem is undecidable for domain alphabets of size 105. Here we give a proof that the infinite Post Correspondence Problem is undecidable...

Undecidability of topological and arithmetical properties of infinitary rational relations

Olivier Finkel (2003)

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

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

Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations

Olivier Finkel (2010)

RAIRO - Theoretical Informatics and Applications

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

Currently displaying 1 – 20 of 23

Page 1 Next