Titlebook: Developments in Language Theory; 13th International C Volker Diekert,Dirk Nowotka Conference proceedings 2009 Springer-Verlag Berlin Heidel

barium-study

Post Correspondence Problem and Small Dimensional Matricese Post Correspondence Problem. The presentation is based on the article Halava et al. “Undecidability bounds for integer matrices using Claus instances” (Internat. J. Foundations of Comput. Sci. 18, 2007, 931–948).

patriot

Size Complexity of Two-Way Finite Automataall its early history, and introduce some of the concepts used in its study. We then sketch a possible future, describe a natural systematic way of pursuing it, and record some of the progress that has been achieved. We add little to what is already known—only exposition, terminology, and questions.

promote

Matrix Mortality and the Černý-Pin Conjecture{.,.}.. For the subclass of automata whose transition monoids have the property that each regular -class is a subsemigroup, we give a tight bound on lengths of reset words for synchronizing automata thereby answering a question of Volkov.

环形