Angluin-Style Learning of Deterministic Büchi and Co-Büchi Automata
Authors: Yong Li, Sven Schewe, Qiyi Tang
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We develop efficient techniques for the cases, where we learn deterministic B uchi automata (DBAs) or deterministic co-B uchi automata (DCAs). This is based on the observation that some classes of FDFAs can be used to learn DBAs for DBA recognisable languages, rather than having to resort to nondeterministic ones. We believe that the restriction to DBAs and DCAs in equivalence queries also makes our algorithm more appealing to realistic applications, as the operations are cheap NL for DBAs and DCAs. The main contribution of this paper is that it provides the first Angluin-style learning algorithm for DBAs. Theorem 1. Our DBA learner depicted in Fig. 1 terminates and learns a correct DBA of L. Corollary 1. Our DBA learning algorithm runs in time polynomial in the size of the periodic FDFA of L. A rough complexity analysis of our algorithm leads to the upper bound O(n32 m |Σ|). |
| Researcher Affiliation | Academia | 1 Department of Computer Science, University of Liverpool 2 Key Laboratory of System Software (Chinese Academy of Sciences) and State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences |
| Pseudocode | Yes | Algorithm 1: Refinement of the conjecture FDFA F (Page 4) and Algorithm 2: Counterexample generation for Case (3c) (Page 5). |
| Open Source Code | Yes | Our DBA learning algorithm has been implemented in the tool ROLL [Li et al., 2019], which is publicly available at https://github.com/iscas-tis/roll-library. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments, therefore no datasets are used for training. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments, therefore no training/validation/test dataset splits are provided. |
| Hardware Specification | No | The paper is theoretical and does not describe or require specific hardware for experimental execution. |
| Software Dependencies | No | The paper mentions that the DBA learning algorithm has been implemented in the tool ROLL, but it does not specify any software dependencies with version numbers within the paper itself. |
| Experiment Setup | No | The paper is theoretical and does not conduct experiments, therefore no experimental setup details are provided. |