Friday, February 4, 2022

[DMANET] Straight-Line Programs, Word Equations and their Interplay -- ICALP 2022 workshop CALL FOR PAPERS

Straight-Line Programs, Word Equations and their Interplay -- ICALP 2022

July 4th - Paris, France

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.

** Topics of interest **

Include (but are not limited to):
- Algorithms for straight-line programs
- All aspects of word equations in various classes of (semi)groups
- Applications of straight-line programs in all areas of computer
science and mathematics
  (group theory, computational topology, information theory, database
theory, algebraic complexity theory, etc.)
- Grammar-based compression and related compression methods and formalisms
  (dictionary based compression, string attractors, other measures of
repetitiveness, etc.)
- Extensions of straight-line programs to other data types (trees,
graphs, arrays, etc.)
- Related algebraic formalisms (e.g., noncommutative polynomial identity
- Equations over trees (e.g., context unification)

** Format **
Currently we plan to have a physical workshop. If the pandemic situation
does not allow a physical meeting,
we will switch to hybrid or fully online mode.

** Invited speakers **
Laura Ciobanu (Heriot-Watt University, Edinburgh, UK)
Joel Day (Loughborough University, UK)
Moses Ganardi (Max Planck Institute for Software Systems,
Kaiserslautern, Germany)

** Submission instructions **
Everyone interested in giving a contributed talk should submit a short
abstract (at most 2 pages) to the organizers by email
(aje(at),  lohrey(at)

Accepted contributions will not be part of formal proceedings. We do
accept submissions of work recently published or currently
under review.

** Important dates **
Deadline for contributions: April 14, 2022,
Notifiaction of acceptance: April 31, 2022,
Workshop: July 4, 2022,

** Organizers **
Artur Jeż

Markus Lohrey
* Contributions to be spread via DMANET are submitted to
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.