Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1]
LTL on Finite and Process Traces: Complexity Results and a Practical Reasoner
Authors: Valeria Fionda, Gianluigi Greco
JAIR 2018 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | The paper investigates the theoretical underpinnings of LTLp and of a related logic formalism, named LTLf... In addition, a thorough complexity analysis has been conducted... Finally, based on the theoretical findings of the paper, a practical reasoner specifically tailored for LTLp and LTLf has been developed by leveraging state-of-the-art SAT solvers. The behavior of the reasoner has been experimentally compared with other systems available in the literature. |
| Researcher Affiliation | Academia | Valeria Fionda EMAIL Gianluigi Greco EMAIL De Ma CS, University of Calabria, Italy |
| Pseudocode | No | The paper describes algorithms conceptually and details logical transformations using grammar-like rules and inductive definitions (e.g., Lemma 10, Theorem 12, Section 7.2 Encoding Approach), but it does not include a distinct section or figure labeled as 'Pseudocode' or 'Algorithm' with structured, code-like steps. |
| Open Source Code | Yes | We present a reasoner, called LTL2SAT, for LTLp and LTLf formulas.3 For the classes on which satisfiability is feasible in polynomial time, LTL2SAT implements ad-hoc efficient solution approaches. For the other classes, LTL2SAT encodes the temporal formula into a propositional one and uses a state-of-the-art SAT solver to compute a model. The reasoner is available at http://ltl2sat.wordpress.com/ |
| Open Datasets | Yes | The first group of datasets we have considered is the one used by Li et al. (2014a), where Aalta has been shown to outperform LTL reasoners adapted to deal with finite traces... (i) datasets C1, C2, E, Q, R, S, U, U2, Counter, Rnd and Rnd Conj have been published and discussed by Rozier and Vardi (2007, 2010, 2011); (ii) Alaska-lift and Alaska-szy have been originally used by De Wulf et al. (2008); (iii) Acacia, Anzu, Forobots, Schuppan-O1, Schuppan-O2 and Schuppan-phltl have been posted by Schuppan and Darmawan (2011); (iv) Trp-N5x, Trp-N5y, Trp-N12x and Trp-N12y have been introduced by Hustadt and Schmidt (2002)... We also used logs made available by the IEEE Task-Force on Process Mining, an organization aiming at promoting the research, development, education and understanding of process mining (see http://datacentrum.3tu.nl/). |
| Dataset Splits | No | The paper mentions several benchmarks and describes how some synthetic datasets were generated (e.g., 'randomly generated', 'generated 5 formulas in the class (n, m)'). However, it does not specify explicit training, validation, or test splits for any of the datasets used in its experimental evaluations. |
| Hardware Specification | Yes | Experiments have been carried out on a PC Intel Core i5 2,4 GHz, 8GB RAM and times are the average of five runs. |
| Software Dependencies | No | LTL2SAT uses glucose (Audemard & Simon, 2009), a state-of-the-art SAT solver. In particular, pt(ϕ) is given as input to the Encoder module that produces a SAT translation of the formula by initially considering a model length m = 1. The paper mentions Glucose as a SAT solver used by LTL2SAT but does not specify a version number. |
| Experiment Setup | Yes | we used both a benchmark dataset already used by Li et al. and a dataset taken from the business process domain (hence, more specific for LTLp)... by setting a timeout limit of 5 minutes for solving each instance... Nu SMV has been invoked with the -bmc length option set to the theoretical bounds on the length of the models we obtain via our analysis... for each combination number n of variables, number m of constraints , we generated 5 formulas... we performed the first run by setting m = 1 and we doubled the length m at each of the subsequent runs, without stopping the process when m exceeded the theoretical bound on the length, but only when the timeout of 600 seconds has been reached in some run. |