Strongly Unambiguous Büchi Automata Are Polynomially Predictable With Membership Queries
Strongly Unambiguous Büchi Automata Are Polynomially Predictable With Membership Queries
复制标题
非常明确的 Büchi 自动机可通过成员查询进行多项式预测
DOI：
10.4230/lipics.csl.2020.8
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
D. Fisman
中科院分区：
文献类型：
--
作者：
D. Angluin;Timos Antonopoulos;D. Fisman
一个Büchi自动机是强无二义性的，如果每个词w ∈ n至多有一条最终路径。它们是完全可表达的：每一个正则ω-语言都可以用一个SUBA来表示。SUBA的等价性和包容性可以在多项式时间内确定。SUBA可以指数小于确定性Muller自动机，并且可以指数大于确定性Büchi自动机。在这项工作中，我们表明，SUBAs可以学习在多项式时间内使用成员资格和某些非适当的等价查询，这意味着他们是多项式可预测的成员资格查询。相比之下，在合理的密码学假设下，非确定性Büchi自动机不是多项式可预测的成员查询。2012 ACM学科分类计算理论→无限对象上的自动机;计算理论
A Büchi automaton is strongly unambiguous if every word w ∈ Σ has at most one final path. Many properties of strongly unambiguous Büchi automata (SUBAs) are known. They are fully expressive: every regular ω-language can be represented by a SUBA. Equivalence and containment of SUBAs can be decided in polynomial time. SUBAs may be exponentially smaller than deterministic Muller automata and may be exponentially bigger than deterministic Büchi automata. In this work we show that SUBAs can be learned in polynomial time using membership and certain non-proper equivalence queries, which implies that they are polynomially predictable with membership queries. In contrast, under plausible cryptographic assumptions, non-deterministic Büchi automata are not polynomially predictable with membership queries. 2012 ACM Subject Classification Theory of computation → Automata over infinite objects; Theory of computation
过去、现在和无限的未来
DOI：
10.4230/lipics.icalp.2016.95
发表时间：
2016
期刊：
影响因子：
--
作者：
Thomas Wilke
通讯作者：
Thomas Wilke