Monday, March 21, 2022

[DMANET] Straight-Line Programs, Word Equations and their Interplay -- ICALP 2022 workshop 2nd 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,
Notification of acceptance: April 31, 2022,
Workshop: July 4, 2022,

** Organizers **
Artur Jeż

Markus Lohrey

Artur Jeż

* 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.