5.123. elementn

DESCRIPTIONLINKSAUTOMATON
Origin

P. Flener

Constraint

πšŽπš•πšŽπš–πšŽπš—πšπš—(π™Έπ™½π™³π™΄πš‡,πšƒπ™°π™±π™»π™΄,π™΄π™½πšƒπšπ™Έπ™΄πš‚)

Arguments
π™Έπ™½π™³π™΄πš‡πšπšŸπšŠπš›
πšƒπ™°π™±π™»π™΄πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš•πšžπšŽ-πš’πš—πš)
π™΄π™½πšƒπšπ™Έπ™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŽπš—πšπš›πš’-πšπšŸπšŠπš›)
Restrictions
π™Έπ™½π™³π™΄πš‡β‰₯1
π™Έπ™½π™³π™΄πš‡β‰€|πšƒπ™°π™±π™»π™΄|-|π™΄π™½πšƒπšπ™Έπ™΄πš‚|+1
|πšƒπ™°π™±π™»π™΄|β‰₯|π™΄π™½πšƒπšπ™Έπ™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πšƒπ™°π™±π™»π™΄,πšŸπšŠπš•πšžπšŽ)
πš›πšŽπššπšžπš’πš›πšŽπš(π™΄π™½πšƒπšπ™Έπ™΄πš‚,πšŽπš—πšπš›πš’)
Purpose

βˆ€i∈[1,|π™΄π™½πšƒπšπ™Έπ™΄πš‚|]:π™΄π™½πšƒπšπ™Έπ™΄πš‚[i].πšŽπš—πšπš›πš’=πšƒπ™°π™±π™»π™΄[π™Έπ™½π™³π™΄πš‡+i-1].πšŸπšŠπš•πšžπšŽ

Example
3,6,9,2,9,2,9

The πšŽπš•πšŽπš–πšŽπš—πšπš— constraint holds since its third argument π™΄π™½πšƒπšπ™Έπ™΄πš‚=〈2,9βŒͺ is set to the subsequence starting at the third (i.e.,Β π™Έπ™½π™³π™΄πš‡=3) item of the table πšƒπ™°π™±π™»π™΄=〈6,9,2,9βŒͺ.

Typical
|πšƒπ™°π™±π™»π™΄|>1
πš›πšŠπš—πšπšŽ(πšƒπ™°π™±π™»π™΄.πšŸπšŠπš•πšžπšŽ)>1
|π™΄π™½πšƒπšπ™Έπ™΄πš‚|>1
Symmetry

All occurrences of two distinct values in πšƒπ™°π™±π™»π™΄.πšŸπšŠπš•πšžπšŽ or π™΄π™½πšƒπšπ™Έπ™΄πš‚.πšŽπš—πšπš›πš’ can be swapped; all occurrences of a value in πšƒπ™°π™±π™»π™΄.πšŸπšŠπš•πšžπšŽ or π™΄π™½πšƒπšπ™Έπ™΄πš‚.πšŽπš—πšπš›πš’ can be renamed to any unused value.

Usage

The πšŽπš•πšŽπš–πšŽπš—πšπš— constraint is useful for extracting of subsequence of fixed length from a given sequence.

Reformulation

Let I 1 =π™Έπ™½π™³π™΄πš‡,I 2 =π™Έπ™½π™³π™΄πš‡+1,...,I |π™΄π™½πšƒπšπ™Έπ™΄πš‚| =π™Έπ™½π™³π™΄πš‡+|π™΄π™½πšƒπšπ™Έπ™΄πš‚|-1. The πšŽπš•πšŽπš–πšŽπš—πšπš—(π™Έπ™½π™³π™΄πš‡,πšƒπ™°π™±π™»π™΄,βŒ©πšŽπš—πšπš›πš’-E 1 ,πšŽπš—πšπš›πš’-E 2 ,...,πšŽπš—πšπš›πš’-E |π™΄π™½πšƒπšπ™Έπ™΄πš‚| βŒͺ) constraint can be expressed in term of a conjunction of |π™΄π™½πšƒπšπ™Έπ™΄πš‚| πšŽπš•πšŽπš–πšŽπš—πš constraints of the form:

Β Β Β πšŽπš•πšŽπš–πšŽπš—πš(I 1 ,πšƒπ™°π™±π™»π™΄,E 1 ),

Β Β Β πšŽπš•πšŽπš–πšŽπš—πš(I 2 ,πšƒπ™°π™±π™»π™΄,E 2 ),

Β Β Β ...

Β Β Β πšŽπš•πšŽπš–πšŽπš—πš(π™Έπ™½π™³π™΄πš‡+|π™΄π™½πšƒπšπ™Έπ™΄πš‚|-1,πšƒπ™°π™±π™»π™΄,E |π™΄π™½πšƒπšπ™Έπ™΄πš‚| ).

See also

common keyword: πšŽπš•πšŽπš–πšŽπš—πšΒ (data constraint).

Keywords

characteristic of a constraint: automaton, automaton without counters, reified automaton constraint.

constraint network structure: Berge-acyclic constraint network.

constraint type: data constraint, sliding sequence constraint.

filtering: arc-consistency.

modelling: table.

Automaton

FigureΒ 5.123.1 depicts the automaton associated with the πšŽπš•πšŽπš–πšŽπš—πšπš— constraint of the Example slot. Let 𝙸 and 𝙴 k respectively denote the π™Έπ™½π™³π™΄πš‡ argument and the πšŽπš—πšπš›πš’ attribute of the k th item of the π™΄π™½πšƒπšπ™Έπ™΄πš‚ collection. FigureΒ 5.123.2 depicts the reformulation of the πšŽπš•πšŽπš–πšŽπš—πšπš— constraint.

Figure 5.123.1. Automaton of the πšŽπš•πšŽπš–πšŽπš—πšπš— constraint given in the example
ctrs/elementn1
Figure 5.123.2. Hypergraph of the reformulation corresponding to the automaton of the πšŽπš•πšŽπš–πšŽπš—πšπš— constraint
ctrs/elementn2