|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 22 van 30 gevonden artikelen
| Titel: |
Relative Nondeterministic Information Logic is EXPTIME-complete |
| Auteur: |
Demri, Stéphane Ewa |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 75 (2007) nr. 1-4 pagina's 163-178 |
| Jaar: |
2007-03-06 |
| Inhoud: |
We define a relative version of the logic NIL introduced by Orłowska, Pawlak and Vakarelov and we show that its satisfiability is not only decidable but also EXPTIME-complete. Such a logic combines two ingredients that are seldom present simultaneously in information logics: frame conditions involving more than one information relation and relative frames. The EXPTIME upper bound is obtained by designing a well-suited decision procedure based on the nonemptiness problem of Büchi automata on infinite trees. The paper provides evidence that Büchi automata on infinite trees are crucial language acceptors even for relative information logics with multiple types of relations. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 22 van 30 gevonden artikelen
| << vorige | volgende >> |