Back to Search
Start Over
Weighted simple reset pushdown automata
- 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).
- Subjects :
- TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES
General Computer Science
Computer science
Pushdown automaton
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Theoretical Computer Science
Automaton
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
Stack (abstract data type)
010201 computation theory & mathematics
Simple (abstract algebra)
Symbol (programming)
0202 electrical engineering, electronic engineering, information engineering
020201 artificial intelligence & image processing
Algebraic number
Algorithm
Reset (computing)
Computer Science::Formal Languages and Automata Theory
Subjects
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