Weighted simple reset pushdown automata

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 th...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2019-07, Vol.777, p.252-259
Main Authors: Droste, Manfred, Dziadek, Sven, Kuich, Werner
Format: Article
Language:English
Subjects:
Computer Science
Context-free languages
Formal Languages and Automata Theory
Pushdown automata
Weighted automata
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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).
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2019.01.016