Campus Event Calendar
Event Entry
New for: D2, D3
What and Who
PhD Application Talk: Flip-pushdown automata: Nondeterministic ε-moves can be removed
Marek Kosta
PhD Application Talk
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI
MPI Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 25 July 2011
11:15
90 Minutes
E1 4
024
Saarbrücken
Abstract
Flip-pushdown automaton is pushdown automaton which has ability to flip its pushdown throughout the computation. Here we solve in the affirmative the following open problem posed by Holzer and Kutrib: What is the power of ε-moves for nondeterministic flip-pushdown automata – can they be removed without affecting the computational capacity? (ε denotes the empty word.)
Moreover, we prove here that the family of languages recognized by the deterministic variant of the flip-pushdown automata (with k-pushdown reversals) is closed under intersection with regular sets, complement and inverse homomorphism, but it is not closed under union, intersection, (non-erasing) homomorphism, reverse, concatenation and (positive) iteration.
Contact
IMPRS-CS
-1803
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Please note: The talks will take place in random order!
Heike Przybyl, 07/21/2011 12:21 -- Created document.