А что такое по-английски asynchronous automaton? Мне чрезвычайно кажется странным, что эти слова разные по-англ. и по-фр., вроде давно должно было бы синхронизоваться (sorry for the pun).

complementation - плохо т.к. отсылает к complement language что другое
ну да, я об этом и говорю. Построение автомата, распознающего дополнение языка в A*.