Enforcing Structure on Temporal Sequences: The Allen Constraint

By Pierre Roy, Guillaume Perez, Jean-Charles Régin, Alexandre Papadopoulos, François Pachet, and Marco Marchini.

In Principles and Practice of Constraint Programming (CP 2016), Lecture Notes in Computer Science, vol. 9892, pp. 786–801, Springer, Toulouse, 2016.

Read the paper (PDF)
Springer chapter and DOI

About the paper

A note’s position in a list does not tell us where it falls in time when notes have different durations. This paper introduces the Allen global constraint to connect event indexes with their temporal positions, making it possible to impose structural requirements and synchronize sequences.

Abstract summary

The constraint identifies events through temporal relations and keeps track of their indexes. The authors use multivalued decision diagrams (MDDs) to compile the constraint and filter candidate sequences. They demonstrate the method on audio-track synchronization and musical score generation.

Related work

See Markov Constraints for related work on controlling generated sequences, Enforcing Meter in Finite-Length Markov Sequences for metrical constraints, and Exact Sampling for Regular and Markov Constraints with Belief Propagation for the sampling method.

Back to Publications