Straight-Line Programs, Word Equations and their Interplay 2022

ICALP 2022 Satellite Workshop, July 4, 2022, Paris

 

Workshop venue

Université Paris Cité (this is not the same place as the main part of ICALP), 45 Rue des Saints-Pères, 75006 Paris (2nd floor, room Franklin). 

 

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. Please contact the organizers if you plan to attend virtually.

 

Invited speakers

• Laura Ciobanu
• Joel Day
• Moses Ganardi

 

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

• Artur Jeż

  aje(at)cs.uni.wroc.pl

• Markus Lohrey

  lohrey(at)eti.uni-siegen.de

 

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.