On the expressive power of temporal logic for infinite words (Q805240): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q224640 |
||
| Property / reviewed by | |||
| Property / reviewed by: Gheorghe Păun / rank | |||
Revision as of 19:45, 11 February 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the expressive power of temporal logic for infinite words |
scientific article |
Statements
On the expressive power of temporal logic for infinite words (English)
0 references
1991
0 references
The paper gives a self-contained algebraic proof of the equivalence between propositional temporal logic and star-free languages of infinite words. The equivalence is known, but the previous proof was indirectly obtained by establishing first the equivalence with the first-order logic. The present proof is based on a theorem of Schützenberger, which characterizes the \(\omega\)-star-free languages in terms of prefix codes.
0 references
propositional temporal logic
0 references
star-free languages
0 references
infinite words
0 references
