Dana Angluin ; Dana Fisman - Constructing Concise Characteristic Samples for Acceptors of Omega Regular Languages

lmcs:12283 - Logical Methods in Computer Science, November 8, 2024, Volume 20, Issue 4 - https://doi.org/10.46298/lmcs-20(4:10)2024
Constructing Concise Characteristic Samples for Acceptors of Omega Regular LanguagesArticle

Authors: Dana Angluin ; Dana Fisman

    A characteristic sample for a language $L$ and a learning algorithm $\textbf{L}$ is a finite sample of words $T_L$ labeled by their membership in $L$ such that for any sample $T \supseteq T_L$ consistent with $L$, on input $T$ the learning algorithm $\textbf{L}$ returns a hypothesis equivalent to $L$. Which omega automata have characteristic sets of polynomial size, and can these sets be constructed in polynomial time? We address these questions here. In brief, non-deterministic omega automata of any of the common types, in particular Büchi, do not have characteristic samples of polynomial size. For deterministic omega automata that are isomorphic to their right congruence automata, the fully informative languages, polynomial time algorithms for constructing characteristic samples and learning from them are given. The algorithms for constructing characteristic sets in polynomial time for the different omega automata (of types Büchi, coBüchi, parity, Rabin, Street, or Muller), require deterministic polynomial time algorithms for (1) equivalence of the respective omega automata, and (2) testing membership of the language of the automaton in the informative classes, which we provide.


    Volume: Volume 20, Issue 4
    Published on: November 8, 2024
    Accepted on: August 19, 2024
    Submitted on: September 18, 2023
    Keywords: Computer Science - Formal Languages and Automata Theory

    Classifications

    Mathematics Subject Classification 20201

    Consultation statistics

    This page has been seen 460 times.
    This article's PDF has been downloaded 264 times.