KUČERA, Antonín a Jan STREJČEK. The Stuttering Principle Revisited: On the Expressiveness of Nested X and U Operators in the Logic LTL. J. Bradfield (Ed.). In Proceedings of the Annual Conference of the European Association for Computer Science Logic (CSL'02). Berlin: Springer, 2002. s. 276-291. ISBN 3-540-44240-5.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název The Stuttering Principle Revisited: On the Expressiveness of Nested X and U Operators in the Logic LTL
Autoři KUČERA, Antonín (203 Česká republika, garant) a Jan STREJČEK (203 Česká republika).
J. Bradfield (Ed.).
Vydání Berlin, Proceedings of the Annual Conference of the European Association for Computer Science Logic (CSL'02), s. 276-291, 2002.
Nakladatel Springer
Další údaje
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
Obor Computer hardware and architecture
Stát vydavatele Německo
Utajení není předmětem státního či obchodního tajemství
Kód RIV RIV/00216224:14330/02:00006381
Organizační jednotka Fakulta informatiky
ISBN 3-540-44240-5
UT WoS 000187294300019
Klíčová slova anglicky verification; concurrency; weak bisimilarity; infinite-state systems
Štítky concurrency, infinite-state systems, verification, weak bisimilarity
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: doc. RNDr. Jan Strejček, Ph.D., učo 3366. Změněno: 20. 12. 2011 18:12.
Anotace
It is known that LTL formulae without the `next' operator are invariant under the so-called stutter-equivalence of words. In this paper we extend this principle to general LTL formulae with given nesting depths of the `next' and `until' operators. This allows us to prove the semantical strictness of three natural hierarchies of LTL formulae, which are parametrized either by the nesting depth of just one of the two operators, or by both of them. As another interesting corollary we obtain an alternative characterization of LTL languages, which are exactly the regular languages closed under the generalized form of stutter equivalence. We also indicate how to tackle the state-space explosion problem with the help of presented results.
Návaznosti
GA201/00/0400, projekt VaVNázev: Nekonečně stavové souběžné systémy - modely a verifikace
Investor: Grantová agentura ČR, Standardní projekty
GA201/00/1023, projekt VaVNázev: Algoritmy a nástroje pro praktickou verifikaci souběžných systémů
Investor: Grantová agentura ČR, Standardní projekty
MSM 143300001, záměrNázev: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Výzkumné záměry
VytisknoutZobrazeno: 17. 10. 2019 17:58