Reasoning about Infinite Computations
The work
| Authors | Moshe Y. Vardi; Pierre Wolper |
|---|---|
| Editors | |
| Type | article |
| Year | 1994 |
| Citekey | vardi1994reasoning |
Where it appeared
| Published in | Information and Computation |
|---|---|
| Publisher | Elsevier BV |
| Volume | 115 |
| Issue | 1 |
| Pages | 1--37 |
Identifiers
| DOI | 10.1006/inco.1994.1092 |
|---|
Access
| Landing page | https://doi.org/10.1006/inco.1994.1092 |
|---|---|
| Free full text | https://orbi.uliege.be/bitstream/2268/116648/1/VW94-IC.pdf |
Related
| Distinct from | burch1992symbolic |
|---|---|
| Distinct from | girard1987linear |
| Distinct from | halpern2001unusual |
| Distinct from | vardi1986automatatheoretic |
Abstract
The authors investigate extensions of temporal logic by connectives defined by finite automata on infinite words, and consider three different logics, corresponding to three different types of acceptance conditions for the automata. It turns out that these logics all have the same expressive power and that their decision problems are all PSPACE- complete. The authors also investigate connectives defined by alternating automata and show that they do not increase the expressive power of the logics or the complexity of the decision problems.
A copy is held
pdf, 311.1 kB. Not published — it may be under copyright. The facts and links here are.
How it got here
| How it got here | import via drheap-program-correctness |
|---|---|
| Added | 2026-08-25 00:00 UTC |
| Approved by | a person 2026-09-23 14:11 UTC |
Filed under
Cite it as
@article{vardi1994reasoning,
title = {Reasoning about Infinite Computations},
author = {Moshe Y. Vardi and Pierre Wolper},
year = {1994},
journal = {Information and Computation},
publisher = {Elsevier BV},
volume = {115},
number = {1},
pages = {1--37},
doi = {10.1006/inco.1994.1092},
}
This record lives at https://refs.drheap.org/vardi1994reasoning/ and will keep doing so.