Learning Formal Specifications from Membership and Preference Queries

Active learning is a well-studied approach to learning formal specifications, such as automata. In this work, we extend active specification learning by proposing a novel framework that strategically requests a combination of membership labels and pair-wise preferences, a popular alternative to membership labels. We formalize the notion of using preference queries in the context of specification learning by introducing Membership Respecting Preferences (MemRePs), a class of pair-wise preferences that can be used in conjunction with membership queries. The combination of pair-wise preferences and membership labels allows for a more flexible approach to active specification learning, often reducing the number of membership queries required to learn specifications. We instantiate our framework for two different classes of specifications, demonstrating the generality of our approach. Our results suggest that learning from both modalities allows us to robustly and conveniently identify specifications via membership and preferences.