Program

 

PROGRAM

Monday, September 20

09:00 - 09:30 Registration

09:30 - 09:40 Opening

09:40 - 10:30 Eric Allender. The New Complexity Landscape around Circuit Minimization - Invited lecture

10:30 - 10:50 Break

10:50 - 12:05

  • »Dmitry Berdinsky and Prohrak Kruengthomya. Nonstandard Cayley Automatic Representations for Fundamental Groups of Torus Bundles over the Circle
  • »Fabian Birkmann, Stefan Milius and Henning Urbat. On Language Varieties without Boolean Operations
  • »Valentina Dorigatti and Paolo Massazza. Partially Directed Animals with a Bounded Number of Holes

12:05 - 13:35 Lunch

13:35 - 14:50

  • »Ziyuan Gao, Sanjay Jain, Ji Qi, Philipp Schlicht, Frank Stephan and Jacob Tarr. Ordered Semiautomatic Rings with Applications to Geometry
  • »Manasi S. Kulkarni, Jayalal Sarma and Janani Sundaresan. On the Computational Power of Programs over BA2 Monoid
  • »Siddharth Bhaskar, Jane Chandlee, Adam Jardine and Christopher Oakden. Boolean Monadic Recursive Schemes as a Logical Characterization of the Subsequential Functions

14:50 - 15:10 Break

15:10 - 16:25

  • »Sabine Broda, António Machiavelo, Nelma Moreira and Rogério Reis. Location Based Automata for Expressions with Shuffle
  • »Sankardeep Chakraborty, Roberto Grossi, Kunihiko Sadakane and Srinivasa Rao Satti. Succinct Representations for (Non)Deterministic Finite Automata
  • »Susanna Donatelli and Serge Haddad. Expressiveness and Conciseness of Timed Automata for the Verification of Stochastic Models

16:25 - 16:45 Break

16:45 - 17:35

  • »Mehmet Utkan Gezer. Windable Heads & Recognizing NL with Constant Randomness
  • »Chris Keeler and Kai Salomaa. Alternating Finite Automata with Limited Universal Branching

Tuesday, September 21

09:00 - 09:50 Christoph Haase. Approaching Arithmetic Theories with Finite-state Automata - Invited lecture

09:50 - 10:10 Break

10:10 - 11:25

  • »Nadia Labai, Tomer Kotek, Magdalena Ortiz and Helmut Veith. Pebble-intervals Automata and FO2 with Two Orders
  • »Kévin Perrot, Pacôme Perrotin and Sylvain Sené. Optimising Attractor Computation in Boolean Automata Networks
  • »Semyon Petrov and Alexander Okhotin. On the Transformation of Two-way Deterministic Finite Automata to Unambiguous Finite Automata

11:25 - 11:45 Break

11:45 - 13:00

  • »Ahmet Bilal Uçan. Limited Two-way Deterministic Finite Automata with Advice
  • »Kazuyuki Amano. On the Size of Depth-two Threshold Circuits for the Inner Product Mod 2 Function
  • »Riccardo Dondi, Giancarlo Mauri and Italo Zoppis. Complexity Issues of String to Graph Approximate Matching

13:00 - 14:30 Lunch

14:30 - 15:45

  • »Aaron Lye. Deciding Non-emptiness of Hypergraph Languages Generated by Connection-preserving Fusion Grammars is NP-complete
  • »Hiroki Morizumi. On the Power of Nondeterministic Circuits and Co-nondeterministic Circuits
  • »Mikhail Mrykhin and Alexander Okhotin. On Hardest Languages for One-dimensional Cellular Automata

15:45 - 16:05 Break

16:05 - 16:55

  • »Giovanni Pighizzini, Branislav Rovan and Šimon Sádovský. Usefulness of Information and Unary Languages
  • »Hans Zantema. Complexity of Automatic Sequences

Wednesday, September 22

09:00 - 09:50 Artur Jeż. Recompression: Technique for Word Equations and Compressed Data - Invited lecture

09:50 - 10:10 Break

10:10 - 11:25

  • »Alexander Okhotin and Alexey Sorokin. Cyclic Shift on Multi-component Grammars
  • »Nathan Grosshans. The Power of Programs over Monoids in J
  • »Ondrej Klíma and Peter Kostolányi. Geometrically Closed Positive Varieties of Star-free Languages

11:25 - 11:45 Break

11:45 - 13:00

  • »Tomoyuki Yamakami. Intersection and Union Hierarchies of Deterministic Context-free Languages and Pumping Lemmas
  • »Takayuki Miyazaki and Yasuhiko Minamide. Context-free Grammars with Lookahead
  • »David Belanger, Ziyuan Gao, Sanjay Jain, Wei Li and Frank Stephan. Learnability and Positive Equivalence Relations

13:00 - 14:30 Lunch

14:30 - 15:45

  • »Frits Vaandrager, Roderick Bloem, and Masoud Ebrahimi. Learning Mealy Machines with One Timer
  • »Borzoo Bonakdarpour and Sarai Sheinvald. Finite-word Hyperlanguages
  • »Jens Oliver Gutsfeld, Markus Müller-Olm and Christian Dielitz. Temporal Logics with Language Parameters

15:45 - 16:05 Break

16:05 - 16:55

  • »Mamoru Ishizuka, Takahito Aoto and Munehiro Iwami. Commutative Rational Term Rewriting
  • »K. Subramani and Piotr Wojciechowski. Tree-like Unit Refutations in Horn Constraint Systems

Thursday, September 23

09:00 - 09:50 Jean-Éric Pin. How to Prove that a Language is Regular or Star-free? - Invited lecture

09:50 - 10:10 Break

10:10 - 11:25

  • »Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler and Oleg Verbitsky. On the Weisfeiler-Leman Dimension of Fractional Packing
  • »Stefano Crespi Reghizzi and Pierluigi San Pietro. Homomorphic Characterization of Tree Languages Based on Comma-free Encoding
  • »Frederic Dörband, Thomas Feller and Kevin Stier. Approximated Determinisation of Weighted Tree Automata

11:25 - 11:45 Break

11:45 - 13:00

  • »Jing Ji and Jeffrey Heinz. Input Strictly Local Tree Transducers
  • »Bastien Sérée, Loïg Jezequel and Didier Lime. An Algorithm for Single-source Shortest Paths Enumeration in Parameterized Weighted Graphs
  • »Paola Bonizzoni, Clelia De Felice, Rocco Zaccagnino and Rosalba Zizza. Lyndon Words versus Inverse Lyndon Words: Queries on Suffixes and Bordered Words

13:00 - 14:30 Lunch

14:30 - 15:45

  • »Jeffery Dick, Laura K. Hutchinson, Robert Mercas and Daniel Reidenbach. Reducing the Ambiguity of Parikh Matrices
  • »Francesco Dolce, L’ubomíra Dvoráková and Edita Pelantová. On Balanced Sequences and Their Asymptotic Critical Exponent
  • »Stefan Hoffmann. Completely Reachable Automata, Primitive Groups and the State Complexity of the Set of Synchronizing Words

15:45 - 16:05 Break

16:05 - 16:55

  • »Aaron Moss. Simplified Parsing Expression Derivatives
  • »Jean Néraud. Complete Variable-length Codes: An Excursion into Word Edit Operations

Friday, September 24

09:00 - 09:50 Thomas Place. Deciding Classes of Regular Languages: A Language Theoretic Point of View - Invited lecture

09:50 - 10:10 Break

10:10 - 11:00

  • »Julian Pape-Lange. Cadences in Grammar-compressed Strings
  • »Aaron Lye. Context-sensitive Fusion Grammars Are Universal

11:00 - 11:20 Break

11:20 - 12:10

  • »Frederic Dörband, Thomas Feller and Kevin Stier. Sequentiality of Group-weighted Tree Automata
  • »Stefan Hoffmann. State Complexity of the Set of Synchronizing Words for Circular Automata and Automata over Binary Alphabets

12:10 - 12:20 Closing