..
Suche
Hinweise zum Einsatz der Google Suche
Personensuchezur unisono Personensuche
Veranstaltungssuchezur unisono Veranstaltungssuche
Katalog plus

Straight-Line Programs, Word Equations and their Interplay 2022

ICALP 2022 Satellite Workshop, July 4, 2022, Paris

 

Scientific Context

Straight-line programs, i.e., context free grammars that produce a unique string, have been studied intensively in data compression, information theory and stringology and found numerous in such areas like computational group theory, computational topology, program analysis, and verification. Plandowski and Rytter recognized in the late 1990’s their importance for the solution of word equations. Since then, the connection between straight-line programs and word equations turned out to be fruitful. The goal of the workshop is to disseminate recent results on straight-line programs and word equations, and help to gain a new perspective on them, thereby finding possible connections or avenues for new applications of techniques. For researchers not working in the field, the workshop will give a good summary on recent progress in this active field.

 

Format of the workshop

We plan to have an in-person workshop in Paris. In addition, we will offer a basic hybrid mode for online participants.

 

Invited speakers

 

Program

  • 9:30-10:30: Moses Ganardi, Balancing in grammar-based compression
  • 10:30-11:00: coffee break
  • 11:00-12:00: Laura Ciobanu, Group equations with abelian predicates
  • 12:00-12:30: Murray Elder, SLPs in the proof that isomorphism testing for plain groups is in Sigma_3^P
  • 12:30-14:00: lunch
  • 14:00-15:00: Joel Day, Towards a better understanding of (subclasses) of quadratic word equations
  • 15:00-15:30: Florin Manea, Formal languages via theories over strings: What’s decidable?
  • 15:30-16:00: coffee break
  • 16:00-16:30: Nikhil Balaji, Testing equivalence of SLPs in RNC using cyclotomic integers
  • 16:30-17:00: Louisa Seelbach, Entropy bounds for grammar-based tree compressors
  • 17:00-17:30: Markus Schmid, Query evaluation over SLP-represented document databases in the framework of document spanners
  • 17:30-18:00: Artur Jez, (Restricted) word equations coming from database theory

 

Organizers

 

Important Dates

  • Deadline for contributions: April 14 April 24, 2022,
  • Notification of acceptance: April 30, 2022,
  • Workshop: July 4, 2022,

 

Contact

Questions about the workshop can be directed to Artur Jeż or Markus Lohrey.