On the expressive power of temporal logic for infinite words (Q805240): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0304-3975(91)90281-6 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2036410693 / rank | |||
Normal rank | |||
Revision as of 19:51, 19 March 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
