The complexity of counting models of linear-time temporal logic

DOI10.1007/S00236-016-0284-ZMaRDI QIDQ1745344zbMATH OpenOpenAlexFDO

Authors Hazem Torfah, Martín G. Zimmermann

Publication date 17 April 2018

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2014/4846/

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Temporal logic (03B44)

Recommendations

• The complexity of counting models of linear-time temporal logic
• Counting Models of Linear-Time Temporal Logic
• The complexity of propositional linear temporal logics
• scientific article; zbMATH DE number 2196601
• The complexity of the temporal logic with ``until over general linear time
• Complexity of Metric Temporal Logics with Counting and the Pnueli Modalities
• Complexity of metric temporal logics with counting and the Pnueli modalities
• Model-Checking Counting Temporal Logics on Flat Structures
• The complexity of linear-time temporal logic over the class of ordinals
• The complexity of propositional linear temporal logics in simple cases

Cites work

• Bounded Synthesis
• Computational Complexity
• Counting Models of Linear-Time Temporal Logic
• LTL Path Checking Is Efficiently Parallelizable
• Polynomial Space Counting Problems
• Safety, liveness and fairness in temporal logic
• Stochastic Boolean satisfiability
• Symbolic model checking: \(10^{20}\) states and beyond
• The complexity of computing the permanent
• The complexity of counting models of linear-time temporal logic
• The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
• The complexity of propositional linear temporal logics
• Unbeast: Symbolic Bounded Synthesis

Cited in

(7)

• Counting Models of Linear-Time Temporal Logic
• The complexity of counting models of linear-time temporal logic
• A counting logic for structure transition systems
• New complexity results for some linear counting problems using minimal solutions to linear Diophantine equations (extended abstract)
• From LTL to rLTL monitoring: improved monitorability through robust semantics
• scientific article; zbMATH DE number 2016845 (Why is no real title available?)
• Model-Checking Counting Temporal Logics on Flat Structures

Describes a project that uses

Uses Software

• Unbeast
• Acacia+

This page was built for publication: The complexity of counting models of linear-time temporal logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1745344)