Loading [MathJax]/extensions/MathZoom.js
Displaying 41 –
60 of
119
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...
A simplified proof is given for the following result due to
Lisovik: it is undecidable for two given ε–free finite
substitutions, whether they are equivalent on the regular language
b{0,1}*c.
We prove that for every countable ordinal one cannot decide whether a given infinitary rational relation is in the Borel class (respectively ). Furthermore one cannot decide whether a given infinitary rational relation is a Borel set or a -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...
We prove that for every countable ordinal α one cannot decide
whether a given infinitary rational relation is in the Borel class
(respectively ). Furthermore
one cannot
decide whether a given infinitary rational relation is a Borel set or a
-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...
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