All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 3 Next

Displaying 41 – 60 of 119

Showing per page

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

Une caractérisation simple des nombres de Sturm

Cyril Allauzen (1998)

Journal de théorie des nombres de Bordeaux

Un mot sturmien est la discrétisation d’une droite de pente irrationnelle. Un nombre de Sturm est la pente d’un mot sturmien qui est invariant par une substitution non triviale. Ces nombres sont certains irrationnels quadratiques caractérisés par la forme de leur développement en fraction continue. Nous donnons une caractérisation très simple des nombres de Sturm : un nombre irrationnel positif est de Sturm (de première espèce) si et seulement s’il est quadratique et à conjugué négatif.

Currently displaying 41 – 60 of 119