Combinatorial systems defined over one- and two-letter alphabets.
Complexity results for prefix grammars
Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars.
Complexity results for prefix grammars
Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars.
Congruences parfaites et quasi-parfaites
Conjugacy in monoids.
Finiteness results on rewriting systems
Halteprobleme von Fang-Systemen (Tag Systems).
On Markov Properties Of Finitely Presented Groups
On Markov properties of finitely presented groups.
Post grammars as a programming language description tool
Some Recent Results on Squarefree Words
Stackautomaten in Labyrinthen.
The unsolvability of the emptiness problem of the two deterministic finite transducer mappings
Thue Congruences and the Church-Rosser property.
Undecidability of infinite post correspondence problem for instances of size 8
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
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...
Неразрешимое промежуточное исчисление
О поиске вывода в исчислениях общего типа
О правилах типа сечения в исчислениях общего вида
О существовании нерекурсивных базисов конечных автоматов