• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >Greibach Normal Form for omega-Algebraic Systems and Weighted Simple omega-Pushdown Automata
【24h】

Greibach Normal Form for omega-Algebraic Systems and Weighted Simple omega-Pushdown Automata

机译：欧米伽-代数系统的Greibach范式和加权的简单欧米伽-推下自动机

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

摘要

In weighted automata theory, many classical results on formal languages have been extended into a quantitative setting. Here, we investigate weighted context-free languages of infinite words, a generalization of omega-context-free languages (Cohen, Gold 1977) and an extension of weighted context-free languages of finite words (Chomsky, Sch??tzenberger 1963). As in the theory of formal grammars, these weighted languages, or omega-algebraic series, can be represented as solutions of mixed omega-algebraic systems of equations and by weighted omega-pushdown automata. In our first main result, we show that mixed omega-algebraic systems can be transformed into Greibach normal form. Our second main result proves that simple omega-reset pushdown automata recognize all omega-algebraic series that are a solution of an omega-algebraic system in Greibach normal form. Simple reset automata do not use epsilon-transitions and can change the stack only by at most one symbol. These results generalize fundamental properties of context-free languages to weighted languages.
机译：在加权自动机理论中，关于形式语言的许多经典结果已扩展到定量设置中。在这里，我们研究了无穷词的加权无上下文语言，无ω语言的泛化（Cohen，Gold 1977）和无词加权无上下文语言的扩展（Chomsky，Sch？tzenberger 1963）。像形式语法理论中一样，这些加权语言或欧米伽-代数级数可以表示为方程式的混合欧米伽-代数系统的解，也可以表示为欧米伽-下推加权自动机。在我们的第一个主要结果中，我们证明了混合的欧米-代数系统可以转化为Greibach正规形式。我们的第二个主要结果证明，简单的omega-reset下推自动机可以识别所有Greibach正规形式的omega-algebraic系统解决方案的omega-algebraic系列。简单的重置自动机不使用epsilon转换，最多只能更改一个符号来更改堆栈。这些结果将无上下文语言的基本属性推广到加权语言。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号