Programme

The programme is available for download:

- .pdf file: A4 format - 6 pages

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).