Seminario Interdipartimentale di Algoritmica
 
 

Monday, September 27, 2004  12:30 AM
Automata-Theoretic Techniques for Analyzing Infinite-State Systems
Oscar H. Ibarra
University of California at Santa Barbara

DIS - Dipartimento di Informatica e Sistemistica, via Salaria 113
C3 Room, second floor

Abstract:

Automata theory tries to answer questions concerning machine models and languages they define. Classical questions like the relationships between finite/pushdown automata and regular/context-free languages, their closure and decidable properties are standard material in many undergraduate theory courses. New questions that arise from real-world applications, such as in verification, internet/web services, and molecular computing are providing interesting and challenging problems to automata theorists. In this talk, I will present some automata-theoretic and related techniques for analyzing various forms of restricted infinite-state systems in the areas of formal verification, e-services, and membrane systems.

This research was supported in part by NSF Grants CCR-0208595 and CCF-0430945.