Abstract | ||
---|---|---|
We show that linear-time temporal logic over concrete domains made of finite strings and the prefix relation admits a PSpace-complete satisfiability problem. Actually, we extend a known result with the concrete domain made of the set of natural numbers and the greater than relation (corresponding to the singleton alphabet case) and we solve an open problem mentioned in several publications. Since ... |
Year | DOI | Venue |
---|---|---|
2016 | 10.1093/logcom/exv028 | Journal of Logic and Computation |
Keywords | Field | DocType |
Temporal logic,string theory,prefix relation,translation,complexity | Discrete mathematics,Natural number,Open problem,Boolean satisfiability problem,Prefix,Decidability,PSPACE,Temporal logic,Singleton,Mathematics | Journal |
Volume | Issue | ISSN |
26 | 3 | 0955-792X |
Citations | PageRank | References |
2 | 0.38 | 17 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Stéphane Demri | 1 | 832 | 60.65 |
Morgan Deters | 2 | 283 | 17.25 |