CIAA 2004 Technical Program

Thursday July 22

8:00 - 8:45 Registration

8:45 - 9:00 Opening

9:00 - 10:00 Chair: Sheng Yu

• Oscar H. Ibarra, University of California, Santa Barbara
  Invited Lecture: Automata-Theoretic Techniques for Analyzing Infinite-State Systems

10:00 - 10:30 Coffee Break

10:30 - 12:00 Chair: Derick Wood

• B. Krawetz, J. Lawrence, J. Shallit: State Complexity and the Monoid of Transformations of a Finite Set
• J.-M. Champarnaud, F. Coulon, T. Paranthoen: Brute force determinization of NFAs by means of state covers
• O. Carton, J. Berstel: On the complexity of Hopcroft's state minimization algorithm

12:00 - 1:30 Lunch

1:30 - 3:00 Chair: Juergen Dassow

• L. Kari, S. Konstantinidis, P. Sosik: Substitutions, Trajectories and Noisy Channels
• Y. Han, B. Ma, K. Zhang: An Automata Approach to Match Gapped Sequence Tags against Protein Database
• A. Binder, R. Freund, G. Lojka, M. Oswald: Implementation of Catalytic P Systems

3:00 - 3:30 Coffee Break

3:30 - 5:00 Chair: John Brzozowski

• M. Giraud, D. Lavenier: Linear Encoding Scheme for Weighted Finite Automata
• G. Tischler: Parametric Weighted Finite Automata for Figure Drawing
• W. Debski, W. Fraczak: Concatenation State Machines and Simple Functions

6:00 Excursion : Cruise on Island Queen triple deck boat. Departure at 6:00 PM sharp from #1 Brock Street, return by 8:00 PM.

Friday July 23

8:30 - 9:30 Chair: Kai Salomaa

• Jeffrey O. Shallit, University of Waterloo
  Invited Lecture: Regular Expressions: Enumeration and State Complexity

9:30 - 10:00 Chair: Kai Salomaa

• V. Zakharov, I. Zakharyaschev: On the equivalence-checking problem for a model of programs related with multi-tape automata

10:00 - 10:30 Coffee Break

10:30 - 12:00 Chair: Jacques Sakarovitch

• C. Allauzen, M. Mohri, B. Roark: A General Weighted Grammar Library
• M. Frishert, L. Cleophas, B. Watson: FIRE Station: An environment for manipulating finite automata and regular expression views
• A. Geser, D. Hofbauer, J. Waldmann, H. Zantema: Finding finite automata that certify termination of string rewriting

12:00 - 1:15 Lunch

1:15 - 2:30 NSERC Workshop

2:30 - 4:00 Chair: Alexander Okhotin

• A. Yli-Jyrä: Approximating Dependency Grammars through Intersection of Regular Languages
• M. Vilares, J. Otero, J. Grana: Regional Finite-State Error Repair
• B. Borchardt: Code Selection by Tree Series Transducers

4:00 - 4:30 Coffee break

4:30 - 5:15 General meeting and CIAA 2005

5:15 - 6:00 Chair: Mark Daley

• Poster Session

7:00 Conference banquet

Saturday July 24

8:15 - 9:00 Chair: Sheng Yu

• Special session: XML representation for finite automata

9:00 - 10:00 Chair: Bruce Watson

• Y.-S. Han, D. Wood: The generalization of generalized automata: Expression automata
• J. Jirasek, G. Jiraskova, A. Szabari: State Complexity of Concatenation and Complementation of Regular Languages

10:00 - 10:30 Coffee Break

10:30 - 12:00 Chair: Giovanni Pighizzini

• J.-M. Champarnaud, F. Nicart, D. Ziadi: Computing the Follow Automaton of an Expression
• S. John: Minimal unambiguous eNFA
• H. Bordihn, M. Holzer, M. Kutrib: Some Non-Semi-Decidability Problems for Linear and Deterministic Context-Free Languages

12:00 - 1:00 Lunch

1:00 - 3:00 Chair: Michael Domaratzki

• B. Shan: Stochastic Context-Free Graph Grammars for Glycoprotein Modelling
• Z.S. Peng, H.F. Ting: Time and Space Efficient Algorithms for Constrained Sequence Alignment
• M. Daley, I. McQuillan: Viral gene compression: complexity and verification
• H. Nishimura, T. Yamakami: An Application of Quantum Finite Automata to Interactive Proof Systems

3:00 - 3:10 Closing

Last updated: 7 June 2004