Title: Stochastic Languages at Sub-stochastic Cost Show Chinese title

Title: 随机语言在次随机成本下

Abstract: When does a deterministic computational model define a probability distribution? What are its properties? This work formalises and settles this stochasticity problem for weighted automata, and its generalisation cost register automata (CRA). We show that checking stochasticity is undecidable for CRAs in general. This motivates the study of the fully linear fragment, where a complete and tractable theory is established. For this class, stochasticity becomes decidable in polynomial time via spectral methods, and every stochastic linear CRA admits an equivalent model with locally sub-stochastic update functions. This provides a local syntactic characterisation of the semantics of the quantitative model. This local characterisation allows us to provide an algebraic Kleene-Schutzenberger characterisation for stochastic languages. The class of rational stochastic languages is the smallest class containing finite support distributions, which is closed under convex combination, Cauchy product, and discounted Kleene star. We also introduce Stochastic Regular Expressions as a complete and composable grammar for this class. Our framework provides the foundations for a formal theory of probabilistic computation, with immediate consequences for approximation, sampling, and distribution testing. Show Chinese abstract

Abstract: 确定性计算模型何时定义一个概率分布？ 它的性质是什么？ 这项工作为加权自动机及其推广的成本寄存器自动机（CRA）形式化并解决了这个随机性问题。 我们证明了一般情况下对于CRA来说，检查随机性是不可判定的。 这促使我们研究完全线性片段，在该片段中建立了一个完整且易于处理的理论。 对于此类，通过谱方法可以在多项式时间内判定随机性，并且每个随机线性CRA都存在一个具有局部次随机更新函数的等效模型。 这提供了定量模型语义的局部语法特征。 这种局部特征使我们能够为随机语言提供代数Kleene-Schutzenberger特征。 有理随机语言类是包含有限支持分布的最小类，它在凸组合、柯西乘积和折扣Kleene星运算下是封闭的。 我们还引入了随机正则表达式，作为该类的完整且可组合的语法。 我们的框架为概率计算的形式理论提供了基础，对近似、抽样和分布测试有直接的影响。