Weighted simple reset pushdown automata

被引：4

作者：

Droste, Manfred ^{[1
]}

Dziadek, Sven ^{[1
]}

Kuich, Werner ^{[2
]}

机构：

[1] Univ Leipzig, Inst Informat, Leipzig, Germany

[2] Tech Univ Wien, Inst Diskrete Math & Geometrie, Vienna, Austria

来源：

THEORETICAL COMPUTER SCIENCE | 2019年 / 777卷

基金：

奥地利科学基金会;

关键词：

Context-free languages; Pushdown automata; Weighted automata;

D O I：

10.1016/j.tcs.2019.01.016

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We define a new normal form for weighted pushdown automata. The new type of automaton uses a stack but has only limited access to it. Only three stack commands are available: popping a symbol, pushing a symbol or leaving the stack unaltered. Additionally, E-transitions are not used. We prove that this automaton model can recognize all weighted context-free languages (i.e., generates all algebraic power series). (C) 2019 Elsevier B.V. All rights reserved.

引用

页码：252 / 259

页数：8

共 12 条

[1] Berstel J., 1979, Transductions and Context-Free Languages
[2] Blass A., 2006, NOTE NESTED WORDS
[3] Conway J.H., 1971, Regular Algebra and Finite Machines
[4] Droste M., LOGIC OMEGA PU UNPUB
[5] The Triple-Pair Construction for Weighted ω-Pushdown Automata
Droste, Manfred
Esik, Zoltan
Kuich, Werner
[J]. ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE, 2017, (252): : 101 - 113
[6] Logics for Weighted Timed Pushdown Automata
Droste, Manfred
Perevoshchikov, Vitaly
[J]. FIELDS OF LOGIC AND COMPUTATION II: ESSAYS DEDICATED TO YURI GUREVICH ON THE OCCASION OF HIS 75TH BIRTHDAY, 2015, 9300 : 153 - 173
[7] THE CHOMSKY-SCHUTZENBERGER THEOREM FOR QUANTITATIVE CONTEXT-FREE LANGUAGES
Droste, Manfred
Vogler, Heiko
[J]. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2014, 25 (08) : 955 - 969
[8] Eilenberg S., 1974, PURE APPL MATH A, V59, DOI [10.1016/S0079-8169(08)60875-2, DOI 10.1016/S0079-8169(08)60875-2]
[9] Esik Zoltan, 2007, MODERN AUTOMATA THEO
[10] Kuich W., 1986, MONOGR THEORET COMPU, V5, DOI [10.1007/978-3-642-69959-7, DOI 10.1007/978-3-642-69959-7]

← 1 2 →