Constructing Concise Characteristic Samples for Acceptors of Omega Regular Languages
arxiv(2022)
摘要
A characteristic sample for a language L and a learning algorithm
L is a finite sample of words T_L labeled by their membership in
L such that for any sample T ⊇ T_L consistent with L, on input
T the learning algorithm 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.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要