.png){kind=icon}
.png){kind=icon}
Return
A Framework for Computing Upper Bounds in Passive Learning Settings
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-04590-4_16.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The task of inferring logical formulas from examples has garnered significant attention as a means to assist engineers in creating formal specifications used in the design, synthesis, and verification of computing systems. Among various approaches, enumeration algorithms have emerged as some of the most effective techniques for this task. These algorithms employ advanced strategies to systematically enumerate candidate formulas while minimizing redundancies by avoiding the generation of syntactically different but semantically equivalent formulas. However, a notable drawback is that these algorithms typically do not provide guarantees of termination. This paper develops an abstract framework to bound the size of possible solutions for a logic inference task, thereby providing a termination guarantee for enumeration algorithms through the introduction of a sufficient stopping criterion. The proposed framework is designed with flexibility in mind and is applicable to a broad spectrum of practically relevant logical formalisms, including Modal Logic, Linear Temporal Logic, Computation Tree Logic, Alternating-time Temporal Logic, Probabilistic Computation Tree Logic and even selected inference tasks for automata. In addition, our approach enabled us to develop a meta algorithm that enumerates over the semantics of formulas rather than their syntactic representations, offering new possibilities for reducing redundancy.
Keywords:
Passive learning
stopping criterion
temporal logic
Journal
L
IF:
0
Papers:
19
Citations:
0