Research Group on Natural Computing

Speaker: Professor Oscar H. Ibarra
Department of Computer Science
University of California
Santa Barbara, CA 93106, USA

Title: On the Complexity of Parikh Membership Problems.

Abstract: We consider the problem of determining if a string w belongs to a language L specified by an automaton (e.g., NFA, PDA, counter machine, etc.) where the string w is specified by its Parikh vector. We investigate the complexity of this problem under various scenarios: the Parikh vector is given in unary, binary, the automaton is fixed (i.e., not part of the input), the automaton is not fixed and part of the input. We also look at related problems
involving semilinear sets and synchronized multitape automata.

Information:

• Date: Monday, 17-03-2014
• Time: 10:00.
• Place: Seminar room H1.50 (First floor, Módulo H, Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla)
• Language: English

Organized by: Research Group on Natural Computing

Related links: Announcement in IMUS