Temporal specifications are essential for verification and monitoring, yet writing formulas that capture the intended behaviour is difficult. Active learning derives such specifications through interaction between a learner and a teacher, but remains underexplored for temporal logics. Existing approaches require the teacher to answer equivalence queries and to construct counterexamples, and they often rely on SAT-based learning procedures that restart the search after each new example. We present an active-learning framework for LTLf in which the teacher only labels traces and answers natural-language questions about the intended behaviour. The learner maintains an enumerated version space of candidate formulas, generates traces that distinguish candidates, and uses the teacher's hints to rank candidates or to restrict the search. We prove consistency with the observed examples, identification within bounded hypothesis classes with a bound on the number of queries, and a PAC guarantee for the final hypothesis. In experiments with a simulated teacher on 36 targets, including targets in four standard environments, the learner identifies every target when it compares all rivals, with fewer than seven queries beyond an initial sample of ten traces on average. Correct hints reduce the number of queries by up to 16% and the number of generated candidates by a fifth, and hints used for ranking never prevent identification, even when incorrect. Our enumeration-based version space is faster than the SAT-based approach of previous learners at every target size.
Does anything happen too often or not often enough?
Which event, and how should its repetition change?
GFB
Table 1: Questions at both levels and the formula families Hc of the question types. Level 1 answers are Yes, No, or Unsure; Level 2 is asked after a Yes answer. B and B′ stand for Boolean formulas. In our experiments, a simulated teacher answers.
Table 2: Benchmark targets. ∣S∣ : number of reachable environment states. Sizes count syntax-tree nodes, with ¬p counted as one node.
Free traces
Environments
Top- 3
Exhaustive
Top- 3
Exhaustive
Order of rivals
Succ.
Exact
MQ
Succ.
MQ
Eq.
Succ.
Exact
MQ
Succ.
MQ
Eq.
Enumeration
92
77
15.5
100
16.2
14.2
40
20
8.7
80
12.5
310
Semantic (closest)
64
56
13.5
100
15.9
20.1
40
20
8.6
80
12.2
310
Semantic (farthest)
100
85
16.1
100
16.1
11.9
41
20
9.5
80
12.5
308
Split
100
85
15.7
100
15.7
11.8
64
25
10.6
80
12.4
296
Table 3: RQ1 and RQ2: identification and cost by order of rivals and stopping rule. All runs use the enumeration-based version space, the progression-based Distinguish and no hints. Top- 3 : top- K rule with K=3 ; Exhaustive: K=∞ . Succ.: runs with φH≡φT (free, out of 100 ) or φH≡EφT (environments, out of 80 ). Exact: runs with φH=φT up to notation; under the exhaustive rule, 85 free and 30 environment runs for every order. MQ: mean membership queries per run, including the 10 initial traces; top- 3 means include failed runs. Eq.: mean comparisons per run under the exhaustive rule that found a rival equivalent to φH .
Free traces
Environments
∣φT∣
N
MQ
Time
Max
Cand.
N
MQ
Time
2
10
10.6 (10–13)
0.01
0.03
0.2
20
8.7 (5–11)
0.02
3
15
11.4 (10–13)
0.01
0.02
1.0
10
10.5 (7–13)
0.02
5
35
15.7 (10–20)
0.10
0.11
55.8
45
14.0 (9–21)
0.19
6
20
18.6 (14–22)
1.07
1.32
536
5
18.4 (17–19)
1.02
7
20
20.9 (13–32)
7.94
10.70
3,944
–
–
–
Table 4: RQ2: cost by target size under the exhaustive rule with enumeration order (no hints). N : runs; MQ: mean (minimum–maximum); Time: mean seconds per run; Max: maximum seconds per run; Cand.: mean number of generated formulas, in thousands.
Progr.
MONA
SAT
∣φT∣
n
Time
Mem.
Time
Mem.
Time
Mem.
2
3
0.83
281
0.78
281
0.89
315
3
4
0.79
281
0.80
281
0.98
316
5
6
0.87
290
0.97
290
1.63
356
6
7
1.81
350
1.98
352
3.03
415
7
8
8.82
702
9.92
728
22.35
486
Table 5: RQ2: three implementations on the free targets (exhaustive rule, enumeration order, no hints). Progr.: enumerated version space and progression-based Distinguish , as in all other runs; MONA: the same with automata-based Distinguish ; SAT: SAT-based version space with progression-based Distinguish . Time: mean seconds per run; Mem.: mean peak memory in MB. Each run has its own process, which adds about 0.7 s, so times are not comparable with Table 4 . Rows for n=9,10 : the four size- 7 targets with seeds 41 and 42 and a limit of 600 s (one run each for Progr. and MONA); the SAT entry gives the runs that finished.
Free traces
Environments
Succ.
Exhaustive
Succ.
Exhaustive
Hints
Top- 3
Exh.
MQ
Cand.
Time
Top- 3
Exh.
MQ
Cand.
Time
None
92/100
100/100
16.2
916
1.83
40/80
80/80
12.5
57
0.18
Level 1, ranking
95/100
100/100
16.0
916
1.84
64/80
80/80
12.4
57
0.20
Level 1, pruning
94/100
100/100
14.6
710
1.56
54/80
80/80
10.5
46
0.12
None †
66/70
70/70
16.0
964
1.94
25/55
55/55
13.7
77
0.23
Table 6: RQ3: effect of hints. All runs use enumeration order of rivals and the enumeration-based version space. Succ.: successful runs under the top- 3 and the exhaustive rule. MQ, Cand. (generated formulas, in thousands) and Time (seconds) are means under the exhaustive rule. Rows marked † cover only the targets that receive a Level-2 hint ( 70 free and 55 environment runs); None † is the run without hints on these targets.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Environment
States
Targets
Office world
108
7
Taxi
101
3
DoorKey 5×5
62
4
DoorKey 6×6
154
2
Appendix
Table 7: Environment configurations used in the experiments.
Figure 1: Office world, drawn from the implemented map. Thick lines denote walls and gaps denote doorways. S marks the start; the other labels identify coffee ( f ), mail ( e ), the office ( g ), plants ( n ), and locations a,b,c,d .
Figure 2: Illustrative Taxi environment. Image: still frame from the official Gymnasium documentation . The pictured taxi and passenger positions need not match the experiment’s reset seed.
Figure 3: DoorKey environments. (a) Illustrative 5×5 layout from the official MiniGrid documentation ; its initial configuration may differ from the experiment’s. (b) Grid drawn from the 6×6 experiment with reset seed 0 : K denotes the key, D the locked door, G the goal, and the arrow the agent’s initial position and orientation. In (a), the key and door are yellow, the goal is green, and the agent is a red triangle.
Learning temporal logic specifications from system demonstrations is essential for tasks such as formal verification and controller synthesis, especially in safety-critical domains. Existing approaches typically assume demonstrations are correct or only affected by misclassification errors. In practice, however, system traces are often uncertain or incomplete due to sensor faults, measurement errors, or data loss. We present a framework for learning minimal Linear Temporal Logic (LTL) formulas from demonstrations with uncertainty. Our approach models uncertainty via Hamming distance to generate possible estimates around each observed trace, which are grouped with constraints requiring that at least one trace per group is consistent with the learned formula. Our problem is then reduced to an equivalent Pseudo-Boolean Optimization. We evaluate our method against state-of-the-art LTL learning approaches and show that it recovers specifications that more closely align with ground-truth formulas under uncertainty.
Automated mining of formal specifications is vital for verifying real-time systems. However, existing passive learning approaches remain restricted to deterministic specifications or limited fragments of Timed Regular Expressions (TRE). To our knowledge, this paper presents the first framework to tackle precise passive learning for an expressive timed logic, Metric Interval Temporal Logic (MITL) without relying on predefined templates or restricted logic fragments. Our approach formally reduces the timed learning problem into a scalable untimed one. By identifying quantitative timing differences between positive and negative traces, we synthesise precise timed constraints and inject them as new Boolean atomic propositions. This embeds timing into the alphabet, delegating the complex formula evaluation to highly optimised, off-the-shelf untimed LTL tools. Crucially, our framework is complete, guaranteeing a separating specification can always be found. We evaluate our implementation across several benchmarks, demonstrating the effectiveness of our approach.
We study the problem of learning linear temporal logic (LTL) formulas from examples, as a first step towards expressing a property separating positive and negative instances in a way that is comprehensible for humans. Given positive and negative words, the goal is to find a smallest formula satisfied by the positive words and not by the negative ones. We study the computational complexity of this problem for all fragments of negation-free LTL built from the operators F (eventually), G (globally), X (next), ∧ (conjunction), and ∨ (disjunction), without the until operator. We show that the problem is in NP for all fragments, that it is in polynomial time for the fragments containing none of the pairs {X,∧}, {X,∨}, {F,∧} and {G,∨}, and that it is NP-complete for all other fragments, already for alphabets with two or three letters. We also show that the fragment with only X and ∧ has a polynomial time 3-approximation algorithm, but no polynomial time approximation scheme unless P = NP. These results motivate the search for efficient heuristics.