Jelenlegi hely

Intézeti szeminárium

Félév: 
2018/19 I. félév
Helyszín: 
Árpád tér 2. II. em. 220. sz.
Dátum: 
2018-10-09
Időpont: 
14:00-15:00
Előadó: 
Werner Kuich (Technische Universität Wien)
Cím: 
Weighted Pushdown Automata
Absztrakt: 

We start with a short introduction into semirings and formal power
series. Then we define weighted pushdown automata over complete
semirings by labeled directed infinite graphs with a finitely
defined structure that mirrors the LIFO (last in – first out)
principle in connection with the pushdown tape. The acceptance is
by empty tape and final state. We then define the infinite transition
matrix of the weighted pushdown automaton which is nothing else than
the adjacency matrix of the infinite graph.

Then we turn to pushdown automata over power series semirings and
show –  as a generalization of the equivalence of classical pushdown
automata and contextfree grammers – the equivalence of weighted
pushdown automata and algebraic systems. The proof is a generalization
of the wellknown triple construction and is much easier than the usual
proofs.

Eventually we discuss weighted restart pushdown automata that start
with empty tape and accept again by emty tape and final state.