On the complexity of linear temporal logic with team semantics (Q2193280)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 7239088
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On the complexity of linear temporal logic with team semantics |
scientific article; zbMATH DE number 7239088 |
Statements
On the complexity of linear temporal logic with team semantics (English)
0 references
25 August 2020
0 references
The paper considers the well-known temporal logic LTL, but with a novel semantics, based on teams, that is, sets of traces rather than single traces. Boolean negation is also added, since it is not available in the logic, where Boolean connectives behave in a nonstandard way. The problem of characterizing stuttering-invariant formulas is partially solved. Satisfiability and model checking of LTL with negation are shown to be logspace equivalent to third-order arithmetic.
0 references
complexity
0 references
team semantics
0 references
linear temporal logic
0 references
0.8059624433517456
0 references
0.7938379049301147
0 references
0.7896596193313599
0 references
0.7888897657394409
0 references
0.7737239599227905
0 references
