Logika LTL i deterministycznych automatów BUCHI są nieporównywalne: DBA nie może wyrazić , i nie mogą wyrażać LTL „co najmniej dziwne jest każda litera«a»” . Ale czasami interesujące jest, czy język DBA może być wyrażony w LTL.
Potrzebuję algorytmu, który decyduje, czy język danego DBA można opisać w LTL. Czy znasz na to algorytmy?
Przypuszczamy, że inny kierunek jest rozstrzygalny (przekonwertować formułę na NBA, zastosować konstrukcję zestawu mocy, sprawdzić równoważność), ale do tej pory nie mieliśmy pojęcia o tym, który chcesz.
—
Raphael
Nie jestem pewien, czy to w ogóle możliwe, ale chciałbym zauważyć, że przez automaty Buchi ludzie zwykle mają na myśli NBA (który jest bardziej ekspresyjny niż DBA). NBA jest również bardziej wyrazisty niż LTL.
—
Daniil
@Daniil od Ciebie referencje (języki definiowane pierwszego rzędu): „Pokazujemy również, że aperiodyczność (tj. Definiowalność pierwszego rzędu (różnicowalność LTL)) zwykłego języka can można zadecydować w przestrzeni wielomianowej” .nice ref!
@Ayrat, dzięki, to naprawdę dobre wprowadzenie, byłem bardzo szczęśliwy, kiedy go znalazłem. Jest też cała książka o nieskończonych słowach . Niestety, jeszcze nie przeczytałem.
—
Daniil