• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Annual ACM/IEEE Symposium on Logic in Computer Science >A Generalised Twinning Property for Minimisation of Cost Register Automata*
【24h】

A Generalised Twinning Property for Minimisation of Cost Register Automata*

机译：最小化成本登记自动机的广义孪生属性*

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Weighted automata (WA) extend finite-state automata by associating with transitions weights from a semiring S, defining functions from words to S. Recently, cost register automata (CRA) have been introduced as an alternative model to describe any function realised by a WA by means of a deterministic machine. Unambiguous WA over a monoid (M,⊗) can equivalently be described by cost register automata whose registers take their values in M, and are updated by operations of the form x :=y⊗c, with c ϵ M. This class is denoted by CRA⊗cM. We introduce a twinning property and a bounded variation property parametrised by an integer k, such that the corresponding notions introduced originally by Choffrut for finite-state transducers are obtained for k=1. Given an unambiguous weighted automaton W over an infinitary group (G,⊗) realizing some function f, we prove that the three following properties are equivalent: i) W satisfies the twinning property of order k, ii) f satisfies the k-bounded variation property, and iii) f can be described by a CRA⊗c(G) with at most k registers.In the spirit of tranducers, we actually prove this result in a more general setting by considering machines over the semiring of finite sets of elements from (G,⊗) : the three properties are still equivalent for such finite-valued weighted automata, that is the ones associating with words subsets of G of cardinality at most ℓ, for some natural ℓ. Moreover, we show that if the operation ⊗ of G is commutative and computable, then one can decide whether a WA satisfies the twinning property of order k. As a corollary, this allows to decide the register minimisation problem for the class CRA⊗c(G). Last, we prove that a similar result holds for finite-valued finite-state transducers, and that the register minimisation problem for the class CRA.c(B*) is PSPACE-complete.
机译：加权自动机（WA）通过与来自半环S的过渡权重相关联来扩展有限状态自动机，定义从单词到S的功能。最近，已经引入了成本寄存器自动机（CRA）作为替代模型来描述由WA实现的任何功能通过确定性机器。等价类集（M，⊗）上的明确WA可以等效地由成本寄存器自动机描述，其寄存器的值以M为单位，并通过x：=y⊗c形式的操作进行更新，其中c ϵM。通过CRA ⊗c M.我们引入参数为整数k的孪生性质和有界变化性质，以便在k = 1的情况下获得Choffrut最初为有限状态换能器引入的相应概念。给定一个实现函数f的不定式（G，⊗）上明确的加权自动机W，我们证明以下三个性质是等价的：i）W满足k阶孪生性质，ii）f满足k界变化属性，并且iii）f可以由CRA描述 ⊗c （G）最多具有k个寄存器。在换能器的精神上，我们实际上通过考虑机器对（G，⊗）有限元集的半环进行了证明，从而证明了这一结果是更通用的：这三个属性对于这样的有限值加权自动机，即对于某些自然ℓ，它最多与基数的G的单词子集相关联。此外，我们表明，如果G的运算is是可交换的并且是可计算的，则可以确定WA是否满足k级的孪生性质。因此，可以确定类CRA的寄存器最小化问题 ⊗c （G）。最后，我们证明了有限值有限状态换能器的相似结果，并且证明了CRA类的寄存器最小化问题。 c （B * ）是PSPACE完整的。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号