Informatyka buchi-automata

2

Równoważność automatów Büchi i liniowego

Jest znanym faktem, że każda formuła LTL może być wyrażona przez automat Büchi . Ale najwyraźniej automaty Büchi są silniejszym i bardziej ekspresyjnym modelem. Słyszałem gdzieś, że automaty Büchi są równoważne μ- obliczeniom w czasie liniowym (to znaczy μ- obliczeniom ze zwykłymi punktami stałymi i tylko jednym operatorem czasowym: X …

30 logic automata formal-methods linear-temporal-logic buchi-automata

6

Generowanie kombinacji z zestawu par bez powtarzania elementów

Mam zestaw par. Każda para ma taką postać (x, y), że x, y należą do liczb całkowitych z zakresu [0,n). Jeśli więc n wynosi 4, to mam następujące pary: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) Mam już pary. Teraz muszę zbudować kombinację za pomocą n/2par, tak aby żadna liczba całkowita …

28 algorithms graphics data-structures computational-geometry operating-systems process-scheduling algorithms sorting database-theory relational-algebra finite-model-theory logic automata linear-temporal-logic buchi-automata complexity-theory np-complete decision-problem machine-learning algorithms pattern-recognition logic formal-languages formal-grammars context-free

1

Algorytm do tłumaczenia deterministycznego automatu Büchi na LTL (jeśli to możliwe)

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.FGaFGaFGa Potrzebuję algorytmu, który decyduje, czy język danego DBA można opisać w LTL. Czy …

10 logic automata linear-temporal-logic buchi-automata

Pytania otagowane jako buchi-automata