Résumé de séminaire

Résumé :

In this talk, I consider automatic and asynchronously automatic graphs. The nodes of any such graph are the words over some underlying alphabet. The edges of an automatic graph are determined by a synchronous two-tape automaton: it reads two nodes (i.e., two words) synchronously and decides whether they are joined by an edge or not. Typical examples are graphs associated to semi-Thue systems: here, two words are connected if one can be obtained from the other by just one application of a rule. In an asynchronously automatic graph, the two-tape automaton is not supposed to read the two tapes synchronously.

The first-order theory of any automatic graph is decidable; I sketch an automata-theoretic proof due to Jacquemard, Dauchet & Tisson, and to Khoussainov & Nerode. This decision procedure runs in nonelementary time. I will indicate how to derive a doubly exponential nondeterministic time lower bound for the decision procedure - the huge gap between these two bounds constitutes an open question. (The lower bound stems from joint work with Markus Lohrey that will be presented in a subsequent talk)

W. Thomas constructed an asynchronously-automatic graph with an undecidable first-order theory. Here, I will present another such graph of independent interest: the subword as well as the infix relation of words are asynchronously automatic and their respective first-order theories are undecidable.

Références :

Home page : http://www.mcs.le.ac.uk/~dkuske