Obecnie prowadzę badania nad językiem formalnym, które obejmują klasy języków powyżej zwykłego, ale poniżej kontekstowego. Patrzę na takie rzeczy, jak maszyny zliczające z odwróceniem, maszyny liczące na jednym stosie, deterministyczne CFL itp.
Zastanawiam się, czy ktokolwiek wie o dobrej książce lub opracowaniu, które opisuje właściwości tych języków. Większość tego, na co patrzę, jest zbyt niejasna lub zbyt nowa, aby być w mojej książce Hopcroft-Ullman, nawet w wydaniu z 1979 roku.
Głównie szukam, które klasy językowe są zawarte w sobie nawzajem, właściwości zamykania tych języków i rozstrzygalność podstawowych problemów (problemów F) w tych językach.
Oto kilka przykładów rzeczy, które sprawdziłbym w tym dokumencie:
- Czy wszystkie języki są akceptowane przez maszyny liczników z licznikiem cofania również akceptowane przez maszyny liczników pojedynczych bez ograniczeń?
- Czy deterministyczne, odwrócone języki MultiCounter są zamknięte pod lewą i prawą konkatenacją?
- Czy uniwersalność jest rozstrzygalna dla maszyn z pojedynczym licznikiem.
To tylko przykładowe pytania, mam wiele innych, które pojawiają się w mojej codziennej pracy.
Na początek próbowałem prześledzić, które gazety przytaczają Oscara Ibarry „Odwrócone maszyny wielokontrowe i ich problemy decyzyjne”, ale nie znalazłem wiele.