5.26. arith_sliding

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Used in the definition of some automaton

Constraint

πšŠπš›πš’πšπš‘_πšœπš•πš’πšπš’πš—πš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšπ™΄π™»π™Ύπ™Ώ,πš…π™°π™»πš„π™΄)

Arguments
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πšπ™΄π™»π™Ύπ™ΏπšŠπšπš˜πš–
πš…π™°π™»πš„π™΄πš’πš—πš
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
πšπ™΄π™»π™Ύπ™Ώβˆˆ[=,β‰ ,<,β‰₯,>,≀]
Purpose

Enforce for all sequences of variables πšŸπšŠπš› 1 ,πšŸπšŠπš› 2 ,...,πšŸπšŠπš› i (1≀i≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|) of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection to have (πšŸπšŠπš› 1 +πšŸπšŠπš› 2 +...+πšŸπšŠπš› i ) πšπ™΄π™»π™Ύπ™Ώ πš…π™°π™»πš„π™΄.

Example
πšŸπšŠπš›-0,πšŸπšŠπš›-0,πšŸπšŠπš›-1,πšŸπšŠπš›-2,πšŸπšŠπš›-0,πšŸπšŠπš›-0,πšŸπšŠπš›--3,<,4

The πšŠπš›πš’πšπš‘_πšœπš•πš’πšπš’πš—πš constraint holds since all the following seven inequalities hold:

  • 0<4,

  • 0+0<4,

  • 0+0+1<4,

  • 0+0+1+2<4,

  • 0+0+1+2+0<4,

  • 0+0+1+2+0+0<4,

  • 0+0+1+2+0+0-3<4.

Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
See also

common keyword: πšœπšžπš–_πšŒπšπš›Β (arithmetic constraint).

part of system of constraints: πšŠπš›πš’πšπš‘.

used in graph description: πšŠπš›πš’πšπš‘.

Keywords

characteristic of a constraint: hypergraph, automaton, automaton with counters.

combinatorial object: sequence.

constraint type: arithmetic constraint, decomposition, sliding sequence constraint.

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚

Arc generator
𝑃𝐴𝑇𝐻_1β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—

Arc arity
*
Arc constraint(s)
πšŠπš›πš’πšπš‘(πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—,πšπ™΄π™»π™Ύπ™Ώ,πš…π™°π™»πš„π™΄)
Graph property(ies)
𝐍𝐀𝐑𝐂=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|

Automaton

FigureΒ 5.26.1 depicts the automaton associated with the πšŠπš›πš’πšπš‘_πšœπš•πš’πšπš’πš—πš constraint. To each item of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a signature variable πš‚ i that is equal to 0.

Figure 5.26.1. Automaton of the πšŠπš›πš’πšπš‘_πšœπš•πš’πšπš’πš—πš constraint
ctrs/arith_sliding2
Figure 5.26.2. Hypergraph of the reformulation corresponding to the automaton of the πšŠπš›πš’πšπš‘_πšœπš•πš’πšπš’πš—πš constraint
ctrs/arith_sliding3