TECHNICAL PROGRAM
(All presentations are in UCSB Engineering Sciences Building 1001)


Monday, June 26

8:00-8:45       Registration

8:45-9:00       Opening

9:00-10:00      Chair: Oscar H. Ibarra

                  Rajeev Alur, University of Pennsylvania

                       Invited Lecture:  AddingNesting Structure to Words


10:00-10:30     Coffee break

10:30-12:00     Chair: Zoltan Esik

                  Manfred Kufleitner

                       Polynomials, Fragments of Temporal Logic and the Variety DA over Traces

 
                  Manfred Droste and George Rahonis

                       Weighted Automata and Weighted Logics on Infinite Words         


                  Carsten Fritz and Thomas Wilke

                       Simulation Relations for Alternating Parity Automata and Parity Games


12:00-1:30      Lunch

1:30-3:00       Chair: Kai Salomaa


                  Cedric Bastien, Jurek Czyzowicz, Wojciech Fraczak, and Wojciech Rytter

                       Equivalence of Functions Represented by Simple Context-Free Grammars with Output


                  F. Mraz, F. Otto, and M. Platek

                       On the Gap-Complexity of  Simple RL-Automata
            

                  Sylvain Schmitz

                       Noncanonical LALR(1) Parsing


3:00- 3:30      Coffee break


3:30- 5:00      Chair: Markus Holzer

                  Alberto Bertoni, Christian Choffrut, and Beatrice Palano

                       Context-Free Grammars and XML Languages


                  Didier Caucal

                       Synchronization of Pushdown Automata


                  Martin Kutrib and Andreas Malcher

                       Context-Dependent Nondeterminism for Pushdown Automata


5:00-5:10       Break

5:10-6:10       Chair: Bala Ravikumar

                  Yo-Sub Han, Kai Salomaa, and Derick Wood

                       Prime Decompositions of Regular Languages


                  Nicolae Santean and Sheng Yu

                       On Weakly Ambiguous Finite Transducers


6:15            Welcoming Reception


Tuesday, June 27

8:15-9:00       Registration

9:00-10:00      Chair: Gheorghe Paun

                   Grzegorz Rozenberg, Leiden Institute of Advanced Computer Science & University of Colorado at Boulder

                        Invited Lecture:  Computational Nature of Biochemical Reactions

  
10:00-10:30     Coffee break

10:30-12:00     Chair: Giancarlo Mauri

                   Jurgen Dassow and Gyorgy Vaszil

                        Ciliate Bio-Operations on Finite String Multisets

                   Michael Domaratzki

                        Characterizing DNA Bond Shapes Using Trajectories

                   Natasha Jonoska, Lila Kari, and Kalpana Mahalingam

                        Involution Solid and Join Codes
 

                       
12:00-1:30      Lunch


1:30-3:00       Chair: Masami Ito
 
                   Vassilis Kountouriotis, Christos Nomikos, and Panos Rondogiannis

                        Well-Founded Semantics for Boolean Grammars

                 

                   Andreas Maletti
                        Hierarchies of Tree Series Transformations Revisited
    
                   F. Drewes, S. Ewert, C. du Toit, J. Hagberg, B. van der Merwe, and A. van der Walt

                        Bag Context Tree Grammars


3:00- 3:30      Coffee break

3:30- 5:00      Chair: Omer Egecioglu                          

                   Masami Ito, Peter Leupold, and Kayoko Shikishima-Tsuji

                        Closure of Language Classes under Bounded Duplication


                   Tomasz Jurdzinski

                        The Boolean Closure of Growing Context-Sensitive Languages

                 
                   Flavio D'Alessandro, Gwenael Richomme, and Stefano Varricchio                       
                        Well Quasi Orders and the Shuffle Closure of Finite Sets


5:00-5:10       Break

5:10-6:10       Chair: Sheng Yu

                 
                   Olivier Carton

                        The Growth Ratio of Synchronous Rational Relations is Unique


                   Dalia Krieger

                        On Critical Exponents in Fixed Points of Non-Erasing Morphisms


Wednesday, June 28

9:00-10:00      Chair: Grzegorz Rozenberg

                   Gheorghe Paun,  Institue of Mathematics of the Romanian Academy &  University of Sevilla

                        Invited Lecture:  Languages in Membrane Computing; Some Details for Spiking Neural P Systems


10:00-10:30     Coffee Break

10:30-12:00     Chair: Natasha Jonoska

                   Andrei Paun and Bianca Popa

                        P Systems with Proteins on Membranes and Membrane Division

                   M. Cavaliere, P. Frisco, and H.J. Hoogeboom

                        Computing by Only Observing


                   Paola Bonizzoni and Giancarlo Mauri

                        A Decision Procedure for Reflexive Regular Splicing Languages


12:00-1:30      Lunch

1:30-10:30      Trolley tour of Santa Barbara & courthouse;  conference dinner at the UCSB Faculty Club


Thursday, June 29

9:00-10:00      Chair: Oscar H. Ibarra
                   Yuri Gurevich, Microsoft Research