W książce Sakarovitcha na temat teorii automatów jest napisane we wstępie do części dotyczącej racjonalności w wolnej grupie, że przedstawiony w niej materiał stanowi „fundament prawdziwie matematycznej teorii języków bezkontekstowych”. Nie jest to jednak jednoznaczne, ponieważ języki bezkontekstowe i automaty wypychające są poza zakresem książki.
Zdaję sobie sprawę z niektórych powiązań wolnych grup (a zwłaszcza tego, co Sakarovitch nazywa inwolucyjnymi monoidami ) z teorią automatów pushdown i języków bezkontekstowych - np. Język Dyck, twierdzenie Shamira itp. Jednak miałem trudno jest znaleźć źródło, w którym „prawdziwie matematyczna teoria języków bezkontekstowych”, o której wspomina Sakarovitch, jest rzeczywiście zbudowana.
Najbliższą rzeczą, jaką znalazłem, jest książka Berstela na temat transdukcji i języków bezkontekstowych. Jednak na pierwszy rzut oka wydaje mi się, że automaty wypychające są w tej książce traktowane jedynie marginalnie, podczas gdy teoria racjonalnych podzbiorów grupy wolnej nie jest w ogóle stosowana. Być może materiał, którego szukam, przeznaczony był do tomu C Eilenberga, ale nie jestem tego pewien.
Chciałbym więc poprosić o wskaźnik do książki, ankiety lub zestawu dokumentów, z których mógłbym dowiedzieć się czegoś o „prawdziwie matematycznej teorii języków bezkontekstowych” Sakarovitcha i jej relacjach z wolnymi grupami oraz ich racjonalności podzbiory. A może szukam czegoś, co tak naprawdę nie istnieje?
źródło