7th International Conference on Language and Automata Theory and Applications LATA 2013, April 2 - 5, 2013 Bilbao, Spain Program
Tuesday, April 2 8:00 – 8:50 Registration 8:50 – 9:00 Opening 9:00 – 9:50 J IN -Y I C AI: Complexity Dichotomy for Counting Problems – Invited Lecture Thomas Zeugmann
9:50 – 10:00 10:00 – 11:40 Eli Shamir
11:40 – 12:10 12:10 – 13:50 Jin-Yi Cai
13:50 – 15:30 15:30 – 17:10 Francine Blanchet-Sadri
17:10 – 17:20 17:20 – 18:10 Kousha Etessami
Break B RINK VAN DER M ERWE , M ARK FARAG , AND J ACO G ELDENHUYS: Counting Minimal Symmetric Difference NFAs H ENNING F ERNAU , P INAR H EGGERNES , Y NGVE V ILLANGER: A Multivariate Analysis of Some DFA Problems R ODRIGO DE S OUZA: Uniformisation of Two-Way Transducers K ENJI H ASHIMOTO , RYUTA S AWADA , YASUNORI I SHIHARA , H IROYUKI S EKI , T ORU F UJIWARA: Determinacy and Subsumption for Single-Valued Bottom-Up Tree Transducers Coffee Break A ISTIS ATMINAS , VADIM L OZIN , M IKHAIL M OSHKOV: Deciding WQO for Factorial Languages E LI S HAMIR: Pumping, Shrinking and Pronouns: from Context Free to Indexed Grammars K RISHNENDU C HATTERJEE , S IDDHESH C HAUBAL , S ASHA R UBIN: How to Travel Between Languages C EWEI C UI , Z HE D ANG , T HOMAS R. F ISCHER , O SCAR H. I BARRA: Execution Information Rate for Some Classes of Automata Lunch É RIC L AUGEROTTE , N ADIA O UALI S EBTI , D JELLOUL Z IADI: From Regular Tree Expression to Position Tree Automaton S TUART H ABER , W ILLIAM H ORNE , P RATYUSA M ANADHATA , M I RANDA M OWBRAY, P RASAD R AO : Efficient Submatch Extraction for Practical Regular Expression D ANIEL G O Cˇ , H AMOON M OUSAVI , J EFFREY S HALLIT: On the Number of Unbordered Factors J ÖRG E NDRULLIS , C LEMENS G RABMAYER , D IMITRI H ENDRIKS: MixAutomatic Sequences Break J OËL O UAKNINE: Discrete Linear Dynamical Systems (I) – Invited Tutorial
Wednesday, April 3 9:00 – 9:50 J OËL O UAKNINE: Discrete Linear Dynamical Systems (II) – Invited Tutorial Kousha Etessami
9:50 – 10:00 10:00 – 11:40 Bala Ravikumar
11:40 – 12:10 12:10 – 13:50 Riccardo Dondi
13:50 – 15:30 15:30 – 16:20 Jörg Endrullis
16:20 – 16:30 16:30 – 17:20 Joël Ouaknine
17:30
Break G IORGIO D ELZANNO , R ICCARDO T RAVERSO: Decidability and Complexity Results for Verification of Asynchronous Broadcast Networks T IM S MITH: Infiniteness and Boundedness in 0L, DT0L, and T0L Systems FABRIZIO B IONDI , A XEL L EGAY, B O F RIIS N IELSEN , A NDRZEJ WA˛SOWSKI : Maximizing Entropy over Markov Processes O LGA T VERETINA: A Conditional Superpolynomial Lower Bound for Extended Resolution Coffee Break ´ S EBASTIAN B ALA , A RTUR K ONI NSKI : Unambiguous Automata Denoting Finitely Sequential Functions B ENEDIKT B OLLIG , A ISWARYA C YRIAC , L OÏC H ÉLOUËT, A HMET K ARA , T HOMAS S CHWENTICK: Dynamic Communicating Automata and Branching High-Level MSCs PARISA B ABAALI , C HRISTOPHER K NAPLUND: On the Construction of a Family of Automata that are Generically Non-Minimal S EBASTIAN B ALA , D ARIUSZ J ACKOWSKI: Limited Non-Determinism Hierarchy of Counter Automata Lunch ¯ R USIN ¸ Š F REIVALDS , T HOMAS Z EUGMANN , G RANT P OGOSYAN : On the Size Complexity of Deterministic Frequency Automata J OHANNA B JÖRKLUND , H ENNING F ERNAU , A NNA K ASPRZIK: MAT Learning of Universal Automata Break L UKE O NG: Recursion Schemes, Collapsible Pushdown Automata, and HigherOrder Model Checking (I) – Invited Tutorial Visit to the City
Guggenheim Museum
Flower Puppy
Thursday, April 4 9:00 – 9:50 L UKE O NG: Recursion Schemes, Collapsible Pushdown Automata, and HigherJoël Ouaknine Order Model Checking (II) – Invited Tutorial 9:50 – 10:00 Break 10:00 – 11:40 V ICTOR S ELIVANOV, A NTON K ONOVALOV: Boolean Algebras of Regular Luke Ong ω-Languages A NGELO M ONTANARI , P IETRO S ALA: Interval Logics and ωB-Regular Languages K ARIN Q UAAS: Model Checking Metric Temporal Logic over Automata with one Counter TAKAHITO A OTO , M UNEHIRO I WAMI: Termination of Rule-Based Calculi for Uniform Semi-Unification 11:40 – 12:10 Coffee Break 12:10 – 13:50 J URRIAAN R OT, M ARCELLO B ONSANGUE , J AN R UTTEN: Coinductive Vadim Lozin Proof Techniques for Language Equivalence X IAOJIE D ENG , Y U Z HANG , Y UXIN D ENG , FARONG Z HONG: The Buffered π-calculus: A Model for Concurrent Languages M ICHAEL L UTTENBERGER , M AXIMILIAN S CHLUND: Convergence of Newton’s Method over Commutative Semirings M ILKA H UTAGALUNG , M ARTIN L ANGE , E TIENNE L OZES: Revealing vs. Concealing: More Simulation Games for Büchi Inclusion 13:50 – 15:30 Lunch 15:30 – 17:10 O SCAR I BARRA , B ALA R AVIKUMAR: On Bounded Languages and ReversalYuxin Deng Bounded Automata K ATSUHIKO N AKAMURA , K EITA I MADA: Eliminating Stack Symbols in Push-Down Automata and Linear Indexed Grammars V ÉRONIQUE B RUYÈRE , M ARC D UCOBU , O LIVIER G AUWIN: Visibly Pushdown Automata: Universality and Inclusion via Antichains F LORENT J ACQUEMARD , M ICHAEL R USINOWITCH: Rewrite Closure and CF Hedge Automata 17:10 – 17:20 Break 17:20 – 18:10 T HOMAS S CHWENTICK: XML Schema Management: a Challenge for AuEljas Soisalon- tomata Theory – Invited Lecture Soininen
Calatrava Bridge (Zubizuri)
Friday, April 5 9:00 – 9:50 K OUSHA E TESSAMI: Algorithms for Analyzing and Verifying Infinite-State Andrei Recursive Probabilistic Systems – Invited Lecture Voronkov
9:50 – 10:00 10:00 – 11:40 Benedikt Bollig
11:40 – 12:10 12:10 – 13:50 Tomasz Walen´
13:50 – 15:30 15:30 – 16:20 ¯ ¸š Rusin Freivalds
16:20 – 16:30 16:30 – 17:20 Friedrich Otto
17:20
Break F RIEDRICH O TTO: Asynchronous PC Systems of Pushdown Automata ˇ Š ÍMA : A Turing Machine Distance Hierarchy S TANISLAV Ž ÁK , J I RÍ T OMASZ K OCIUMAKA , J AKUB R ADOSZEWSKI , W OJCIECH RYTTER , T OMASZ WALE N´ : Linear-Time Version of Holub’s Algorithm for Morphic Imprimitivity Testing R AJEEV A LUR , S AMPATH K ANNAN , K EVIN T IAN , Y IFEI Y UAN: On The Complexity of Shortest Path Problems on Discounted Cost Graphs Coffee Break F RANCINE B LANCHET-S ADRI , J USTIN L AZAROW: Suffix Trees for Partial Words and the Longest Common Compatible Prefix Problem D ANIEL G O Cˇ , K ALLE S AARI , J EFFREY S HALLIT: Primitive Words and Lyndon Words in Automatic and Linearly Recurrent Sequences F RANCINE B LANCHET-S ADRI , M ICHELLE B ODNAR , N ATHAN F OX , J OE H IDAKATSU: A Graph Polynomial Approach to Primitivity L UKE S CHAEFFER: Ostrowski Numeration and the Local Period of Sturmian Words Lunch S EPPO S IPPU , E LJAS S OISALON -S OININEN: Online Matching of Multiple Regular Patterns with Gaps and Character Classes B ILLEL B ENZAID , R ICCARDO D ONDI , N ADIA E L -M ABROUK: Duplication-Loss Genome Alignment: Complexity and Algorithm Break A NDREI V ORONKOV: The Lazy Reviewer Assignment Problem in EasyChair – Invited Lecture Closing
We acknowledge the support by:
