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.
źródło
Odpowiedzi:
Niestandardowe tematy, nie. Przepraszam, nie mam ogólnego przeglądu.
Chciałbym jednak rzucić okiem na pracę doktorską Klausa Reinhardta, aby uzyskać przynajmniej zdjęcie różnych rodzin zamieszkujących ten obszar. Schemat zoo znajduje się na stronie 64. Zmotywowani przez sieci Petriego z łukami inhibitora Reinhardt bada priorytetowe liczniki z ograniczeniami, kiedy wykonać testy zerowe. Nietrywialne.
Nawiasem mówiąc, twoje ostatnie przykładowe pytanie zostało omówione na tym forum przez użytkownika Sama Jonesa. Kolejne odniesienie do Ibarry.
źródło