论文标题
大概是由信息理论激发的NFA普遍性和相关问题
Approximate NFA Universality and Related Problems Motivated by Information Theory
论文作者
论文摘要
在编码和信息理论中，希望构建最大代码，该代码可以是可变长度代码或固定长度的错误控制代码。但是，决定代码的最大性归结为决定给定的NFA是否是通用的，这是一个难题（包括NFA是否接受固定长度的所有单词的情况）。另一方面，可以知道代码是否最大，这是可以接受的，然后归结为给定的NFA是否是“近似”通用。在这里，我们介绍了$（1-ε）$ - 通用自动机的概念，并介绍了多项式随机近似算法，以测试NFA通用性和相关的硬自动机问题，以在一组单词上进行某些自然概率分布。我们还得出结论，随机方面是必要的，因为对于任何固定的多项式计算$ε$，近似概述的普遍性仍然很难。
In coding and information theory, it is desirable to construct maximal codes that can be either variable length codes or error control codes of fixed length. However deciding code maximality boils down to deciding whether a given NFA is universal, and this is a hard problem (including the case of whether the NFA accepts all words of a fixed length). On the other hand, it is acceptable to know whether a code is `approximately' maximal, which then boils down to whether a given NFA is `approximately' universal. Here we introduce the notion of a $(1-ε)$-universal automaton and present polynomial randomized approximation algorithms to test NFA universality and related hard automata problems, for certain natural probability distributions on the set of words. We also conclude that the randomization aspect is necessary, as approximate universality remains hard for any fixed polynomially computable $ε$.
