Reference : Reasoning about Infinite Computations
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/116648
Reasoning about Infinite Computations
English
Vardi, Moshe Y. [ > > ]
Wolper, Pierre mailto [Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > > >]
1994
Information and Computation
Academic Press
115
1
1-37
Yes (verified by ORBi)
International
0890-5401
1090-2651
San Diego
CA
[en] Temporal Logic ; Büchi automata ; expressiveness ; decision procedure
[en] We investigate extensions of temporal logic by connectives defined by finite automata on infinite words. We consider three different logics, corresponding to three different types of acceptance conditions (finite, looping, and repeating) for the automata. It turns out, however that these logics all have the same expressive power and that their decision problems are all PSPACE-complete. We also investigate connectives defined by alternating automata and show that they do not increase the expressive power of the logic or the complexity of the decision problem. (C) 1994 Academic Press, Inc.
Researchers
http://hdl.handle.net/2268/116648
10.1006/inco.1994.1092

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
VW94-IC.pdfAuthor postprint311.12 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.