|
Thursday, April 2 |
|
|
8:00 - 8:45 |
Registration |
|
8:45 - 9:00 |
Opening |
|
9:00 - 10:30 |
BRUNO COURCELLE: Monadic Second-order
Logic for Graphs. Algorithmic and Language Theoretical Applications (I)
Invited Tutorial |
|
10:30 - 10:50 |
Coffee Break |
|
10:50 - 12:20 |
NATHALIE BERTRAND, SOPHIE PINCHINAT, JEAN-BAPTISTE RACLET: Refinement and Consistency of Timed Modal Specifications |
|
OLAF BEYERSDORFF, JOHANNES KÖBLER, SEBASTIAN MÜLLER:
Nondeterministic Instance Complexity and Proof Systems with Advice |
|
|
BEATE BOLLIG: Larger Lower Bounds on the OBDD
Complexity of Integer Multiplication |
|
|
12:20 - 12:30 |
Break |
|
12:30 - 14:00 |
FRANZ BAADER, ANDREAS BAUER, ALWEN TIU: Matching Trace Patterns with Regular
Policies |
|
CHRISTOPH BEHLE, ANDREAS KREBS, STEPHANIE REIFFERSCHEID: Non-Solvable
Groups are not in FO+MOD+MÂJ2[REG]
|
|
|
CHRISTIAN GLASSER, A. PAVAN,
STEPHEN TRAVERS: The
Fault Tolerance of NPHard Problems |
|
|
14:00 - 16:00 |
Lunch |
|
16:00 - 17:30 |
RAPHAËL BAILLY,
FRANÇOIS DENIS: Absolute Convergence of Rational Series
is Semi-decidable |
|
KIMMO FREDRIKSSON, SZYMON GRABOWSKI: Nested Counters in Bit-parallel String Matching |
|
|
TOMOHIRO I, SHUNSUKE INENAGA,
HIDEO BANNAI,
MASAYUKI TAKEDA:
Counting Parameterized Border Arrays for a Binary Alphabet |
|
|
17:30 - 17:50 |
Coffee Break |
|
17:50 - 18:50 |
AUDE LIEFOOGHE, HÉLÈNE TOUZET, JEAN-STÉPHANE VARRÉ: Self-overlapping Occurrences and Knuth-Morris-Pratt Algorithm for Weighted Matching |
|
ADAM ROMAN: Genetic Algorithm for
Synchronization |
|
|
18:50 - 19:00 |
Break |
|
19:00 - 20:00 |
MARKÉTA LOPATKOVÁ, TOMÁŠ HOLAN: Segmentation Charts for Czech
Relations among Segments in Complex Sentences |
|
MAKOTO NAKAMURA, TAKASHI HASHIMOTO, SATOSHI TOJO: Prediction of Creole Emergence in
Spatial Language Dynamics |
|
|
Friday, April 3 |
|
|
8:00 - 9:30 |
BRUNO COURCELLE: Monadic Second-order
Logic for Graphs. Algorithmic and Language Theoretical Applications (II)
Invited Tutorial |
|
9:30 - 9:45 |
Break |
|
9:45 - 11:15 |
MATTHIAS BÜCHSE, TORSTEN STÜBER:
Monadic Datalog Tree Transducers |
|
OLIVIER GAUWIN, JOACHIM NIEHREN, SOPHIE TISON: Bounded Delay and Concurrency for Earliest Query Answering |
|
|
|
FLORENT JACQUEMARD, FRANCIS KLAY, CAMILLE VACHER: Rigid Tree Automata |
|
11:15 - 11:45 |
Coffee Break |
|
11:45 - 12:45 |
ANNA KASPRZIK: Two Equivalent Regularizations for
Tree Adjoining Grammars |
|
NEIL MOORE: The Halting Problem and Undecidability of Document Generation
under Access Control for Tree Updates |
|
|
12:45 - 13:00 |
Break |
|
13:00 - 14:00 |
CELINE SCORNAVACCA, VINCENT BERRY, VINCENT RANWEZ: From Gene Trees to Species Trees
through a Supertree Approach |
|
LUTZ STRASSBURGER: A Kleene
Theorem for Forest Languages |
|
|
14:00 - 16:00 |
Lunch |
|
16:00 - 17:30 |
YOHJI AKAMA: Commutative Regular Shuffle Closed Languages, Noetherian
Property, and Learning Theory |
|
NINA GIERASIMCZUK: Learning by Erasing in Dynamic
Epistemic Logic |
|
|
RYUICHI MATOBA, MAKOTO NAKAMURA, SATOSHI TOJO: Efficiency
of the Symmetry Bias in Grammar Acquisition |
|
|
17:30 - 18:00 |
Coffee Break |
|
18:00 - 19:00 |
FRANK J. BALBACH, THOMAS ZEUGMANN: Recent Developments in Algorithmic
Teaching - Invited Talk |
|
19:30 |
Visit to the Old City |
|
Saturday, April 4 |
||
|
9:00 - 10:30 |
BRUNO COURCELLE: Monadic Second-order
Logic for Graphs. Algorithmic and Language Theoretical Applications (III)
Invited Tutorial |
|
|
10:30 - 11:00 |
Coffee Break |
|
|
11:00 - 12:30 |
ISABELLE GNAEDIG: Termination of Priority Rewriting |
|
|
MASAMI ITO, PETER LEUPOLD, VICTOR MITRANA: Bounded Hairpin Completion |
||
|
JÜRGEN DASSOW, SHERZOD TURAEV: Grammars Controlled by Special Petri
Nets |
||
|
12:30 - 12:45 |
Break |
|
|
12:45 - 14:15 |
PAROSH ABDULLA, GIORGIO DELZANNO, LAURENT VAN BEGIN:
A LanguageBased Comparison of Extensions of Petri
Nets with and without Whole-Place Operations |
|
|
TOBIAS BERG, HARALD HEMPEL: Reoptimization
of Traveling Salesperson Problems: Changing Single Edge-Weights
|
||
|
VICTOR MITRANA, BIANCA TRUTHE: On Accepting Networks of Evolutionary
Processors with at Most Two Types of Nodes |
||
|
14:15 |
Lunch |
|
Sunday, April 5
9:0018:00 Conference Trip with Lunch
|
Monday, April 6 |
|
|
8:30 - 9:30 |
MARKUS HOLZER, MARTIN KUTRIB: Descriptional
and Computational Complexity of Finite Automata (I) - Invited Tutorial |
|
9:30 - 9:45 |
Break |
|
9:45 - 11:15 |
BERNARD BOIGELOT, JEAN-FRANÇOIS DEGBOMONT: Partial Projection of Sets
Represented by Finite Automata, with Application to State-Space
Visualization |
|
PASCAL CARON, JEAN-MARC CHAMPARNAUD,
LUDOVIC MIGNOT: Multi-tilde Operators and their Glushkov
Automata |
|
|
CYRIL NICAUD: On the Average Size of Glushkovs Automata |
|
|
11:15 - 11:45 |
Coffee Break |
|
11:45 - 12:45 |
ELENA PRIBAVKINA, EMANUELE RODARO: Finitely
Generated Synchronizing Automata |
|
P. VIJAY SUMAN, PARITOSH PANDYA: Determinization
and Expressiveness of Integer Reset Timed Automata with Silent Transitions |
|
|
12:45 - 13:00 |
Break |
|
13:00 - 14:00 |
SICCO VERWER, MATHIJS DE
WEERDT, CEES WITTEVEEN: One-clock
Deterministic Timed Automata are Efficiently
Identifiable in the Limit |
|
ALEXEI LISITSA, IGOR POTAPOV, RAFIQ SALEH: Automata on Gauss Words |
|
|
14:00 - 16:00 |
Lunch |
|
16:00 - 17:30 |
FRANCINE BLANCHET-SADRI,
EMILY ALLEN,
CAMERON BYRUM, ROBERT MERCAS: How Many Holes Can an Unbordered Partial Word Contain? |
|
FRANCINE BLANCHET-SADRI,
ROBERT MERCAS,
ABRAHAM RASHIN,
ELARA WILLETT:
An Answer to a Conjecture on Overlaps in Partial Words Using Periodicity
Algorithms |
|
|
MICHELANGELO BUCCI, ALESSANDRO
DE LUCA:
On a Family of Morphic Images of Arnoux-Rauzy Words |
|
|
17:30 - 18:00 |
Coffee Break |
|
18:00 - 19:00 |
SANJAY JAIN: Hypothesis Spaces for Learning
Invited Talk |
|
19:30 |
Visit to the City Hall |
|
Tuesday, April 7 |
|
|
8:30 - 9:30 |
MARKUS HOLZER, MARTIN KUTRIB: Descriptional
and Computational Complexity of Finite Automata (II) - Invited Tutorial |
|
9:30 - 9:45 |
Break |
|
9:45 - 11:15 |
GIANPIERO CATTANEO, ALBERTO DENNUNZIO, ENRICO FORMENTI, JULIEN PROVILLARD: Non-Uniform
Cellular Automata |
|
ADAM CLARRIDGE, KAI SALOMAA: A Cryptosystem Based on the Composition
of Reversible Cellular Automata |
|
|
GALINA JIRÁSKOVÁ, GIOVANNI PIGHIZZINI: Converting Self-Verifying
Automata into Deterministic Automata |
|
|
11:15 - 11:45 |
Coffee Break |
|
11:45 - 12:45 |
SERGEY AFONIN, DENIS GOLOMAZOV: Minimal Union-free
Decompositions of Regular Languages |
|
HENNING BORDIHN, MARKUS HOLZER, MARTIN KUTRIB: Undecidability
of Operation Problems for T0L Languages and Subclasses |
|
|
12:45 - 13:00 |
Break |
|
13:00 - 14:00 |
PAUL SALIMOV: Constructing Infinite
Words of Intermediate Arithmetical Complexity |
|
WATARU MATSUBARA, KAZUHIKO KUSANO, HIDEO BANNAI, AYUMI SHINOHARA: A Series of Run-rich
Strings |
|
|
14:00 - 16:00 |
Lunch |
|
16:00 - 17:00 |
JIAMOU LIU, MIA MINNES: Analysing
Complexity in Classes of Unary Automatic Structures |
|
JORDI LLULL-CHAVARRÍA, ÓSCAR
VALERO: An Application of Generalized
Complexity Spaces to Denotational Semantics via the
Domain of Words |
|
|
17:00 - 17:30 |
Coffee Break |
|
17:30 - 18:30 |
YO-SUB HAN, KAI SALOMAA, SHENG YU: State Complexity of Combined
Operations for Prefix-Free Regular Languages |
|
NUTAN LIMAYE, MEENA MAHAJAN: Membership Testing: Removing Extra
Stacks from Multi-stack Pushdown Automata |
|
|
18:30 - 18:45 |
Break |
|
18:45 - 19:45 |
KAI SALOMAA: State Complexity of Nested Word
Automata - Invited Talk |
|
Wednesday, April 8 |
|
|
8:30 - 9:30 |
MARKUS HOLZER, MARTIN KUTRIB: Descriptional
and Computational Complexity of Finite Automata (III) - Invited Tutorial |
|
9:30 - 9:45 |
Break |
|
9:45 - 11:15 |
TOMÁŠ MASOPUST: A Note on the Generative Power of
Some Simple Variants of Context-Free Grammars
Regulated by Context Conditions |
|
KAORU ONODERA: New Morphic
Characterizations of Languages in Chomsky Hierarchy using Insertion and
Locality |
|
|
DANA PARDUBSKÁ,
MARTIN PLÁTEK, FRIEDRICH OTTO: On Parallel Communicating Grammar
Systems and Correctness Preserving Restarting Automata |
|
|
11:15 - 11:45 |
Coffee Break |
|
11:45 - 12:45 |
PAOLA BONIZZONI, CLAUDIO FERRETTI, ANTHONATH ROSLIN SAGAYA MARY, GIANCARLO MAURI: Picture Languages Generated by
Assembling Tiles |
|
NICOLAS OLLINGER: Tiling the Plane with a Fixed Number
of Polyominoes |
|
|
12:45 - 13:00 |
Break |
|
13:00 - 14:30 |
JANUSZ BRZOZOWSKI, JEFFREY SHALLIT, ZHI XU: Decision Problems for Convex
Languages |
|
BENJAMIN CARLE, PALIATH NARENDRAN: On Extended Regular Expressions |
|
|
KEES HEMERIK: Towards a Taxonomy for ECFG and RRPG
Parsing |
|
|
14:30 |
Closing |
With the support of Ministerio de Ciencia e Innovación, Gobierno de España
(MICINN-TIN2009-06274-E).