Résumé | We study the complexity of the following problems:
Given a one counter automaton A
1) construct an NFA that accepts the upward closure of the language of A (w.r.t. subword ordering)
2) construct an NFA that accepts the downward closure of the language of A
3) construct an NFA that accepts a language whose Parikh-image is the Parikh-image of the language of A.
Joint work with M.F. Atig (Uppsala), D. Chistikov (Oxford), P. Hofman (Cachan), P. Saivasan (Kaiserlautern) and G. Zetzsche (Cachan). |