Критерий в самом деле тот же. Автор критерия - больше компьютер сайентист, чем математик, поэтому ждать от него какой-то алгебры не приходится.
Я потом нашел на citeseer еще одну (более позднюю) статью, в которой тоже нет серьезной математики, но по крайней мере там внятно изложен список имеющихся результатов, а также интересных (и нерешенных) задач. У статьи очень смешной заголовок - типа "Все, что на самом деле нужно стране - это монета достоинством 18 центов".
http://citeseer.ist.psu.edu/shallit02what.html