The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
It is shown that small fragments of the first-order theory of the
subword order, the (partial) lexicographic path ordering on words,
the homomorphism preorder, and the infix order are undecidable. This
is in contrast to the decidability of the monadic second-order
theory of the prefix order [M.O. Rabin, Trans. Amer. Math. Soc., 1969] and of the theory of the
total lexicographic path ordering [P. Narendran and M. Rusinowitch, Lect. Notes Artificial
Intelligence, 2000] and, in case of the
...
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...
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...
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...
Currently displaying 21 –
40 of
61