Back to Search Start Over

Weighted simple reset pushdown automata

Authors :
Manfred Droste
Werner Kuich
Sven Dziadek
Source :
Theoretical Computer Science. 777:252-259
Publication Year :
2019
Publisher :
Elsevier BV, 2019.

Abstract

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, ϵ-transitions are not used. We prove that this automaton model can recognize all weighted context-free languages (i.e., generates all algebraic power series).

Details

ISSN :
03043975
Volume :
777
Database :
OpenAIRE
Journal :
Theoretical Computer Science
Accession number :
edsair.doi...........ea85c2f4fba5bfd0e469c4fa9ff9abc9
Full Text :
https://doi.org/10.1016/j.tcs.2019.01.016