Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.96) (envelope-from ) id 1w8vTi-0010qc-1i for pgsql-hackers@arkaria.postgresql.org; Sat, 04 Apr 2026 07:31:34 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.96) (envelope-from ) id 1w8vTf-00Faa1-1w for pgsql-hackers@arkaria.postgresql.org; Sat, 04 Apr 2026 07:31:32 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.96) (envelope-from ) id 1w8vTe-00FaZr-3C for pgsql-hackers@lists.postgresql.org; Sat, 04 Apr 2026 07:31:31 +0000 Received: from mail-pj1-x1031.google.com ([2607:f8b0:4864:20::1031]) by makus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.98.2) (envelope-from ) id 1w8vTb-00000000UKY-13CT for pgsql-hackers@postgresql.org; Sat, 04 Apr 2026 07:31:30 +0000 Received: by mail-pj1-x1031.google.com with SMTP id 98e67ed59e1d1-35d99bae2ebso2208924a91.3 for ; Sat, 04 Apr 2026 00:31:27 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1775287886; cv=none; d=google.com; s=arc-20240605; b=At5RTY/YW0+MWFJxlvkETcLzPDLi4GUg9PO+EU5J5B5n2PnWfbL9Ogi+t/jTzd/V8h IpYqw9nE+0fgtZXgbSF6NJMAi7SWdBYJXZKVHLgXFt4DbQYPBXZB0e/Vb86nqG8LRRyv wPbX/yZjQIgiqjj8DPxj5vPO607bGFeSLBqX8brkrsc5zV+ZYUS80XCIwBBYX202Sy3t UzDJ++FknctZMG1eJbT41u8RVql7QaTeF8omWUW8NPIfrAT9bis5Ed5bB93lCUoKcLbm ssPa77I7eqEtn9RnIZ4YSoWi4bEcZNVI3HMcqm7b6eknhKBzDj7frclIpMzoBFBkuawp IkjA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=cc:to:subject:message-id:date:from:reply-to:in-reply-to:references :mime-version:dkim-signature; bh=DUWWo7I+B3nuYZLrulXxsbN9GS2gywfx8fzhftZaIdU=; fh=dN+f8mYVIXDPzSXRzpP+fOHCdXfXCpwH5tMYA7IVLiQ=; b=D+fXrHc/t3BKqJc9goStHeKTwDKJiYl7gj2Bc3Rf5BYMFCf6yA8py0qsf7wnTFN/CO 6SoleGs1pEjnHtnI36umc7NUQLhGm6ZHimUa/LEaERMmwSoJmC70Ht/69RY4UYhirFNg XhKpl8H71zoAsux87kljvWPAjKA0zLTxHeROXyvqHmRgF10foinusnJvQTA6B4e2OG6I dNIJX6Eu8nH8y1xF+Ng9u3ww4+JTknsnhnn2qX2iGUraqmFLP9WHf0rncN8/HlxusmB0 rJSYHcusGXDAJWGEbMOkegrssObJ4KUxeRsaGw0BEYdhMLjAJMhLeEz0bZWJNQcFkDg8 acDQ==; darn=postgresql.org ARC-Authentication-Results: i=1; mx.google.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1775287886; x=1775892686; darn=postgresql.org; h=cc:to:subject:message-id:date:from:reply-to:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=DUWWo7I+B3nuYZLrulXxsbN9GS2gywfx8fzhftZaIdU=; b=Rcf36xgMjIr18r2Vj1FQ9AjuJkhf/YGaTngJn63sp9tvggOHZaH/0iMYX0Tt1kzKdP Gmz9/PZKGv2Q/gQBgTJ/PeJed4Ip/fh2L6udr9QMT8xy/5LxMqC6dW40ie1qP8v1zMTR a7MYv6ai2OqmNHgo5AfGbwRpzJhGbWXIMHLCEwM/IKr6/bLoNb1EsUQCpmCJ7B7A1Wo/ ktquEz0yrAHPZZ+b6DGCBHBP09/5l5IEFB5q5bkn6fqpVsaqSu3hFpxOYi3R2Swm/ybA cwZw1P9k7nFZT++Zilmm57bScU3iA+DB4SPNZXAFmN2Ijq3fu7iRqDF2skziya8VYOc0 F1Gw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1775287886; x=1775892686; h=cc:to:subject:message-id:date:from:reply-to:in-reply-to:references :mime-version:x-gm-gg:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=DUWWo7I+B3nuYZLrulXxsbN9GS2gywfx8fzhftZaIdU=; b=r7gPYpwLCZ8xDP93aAPEeXnoTV80CLyEHRt1xSrZxml4pjg6yiCVUaZXbNaug5/r6o V302AnZ4AeUg6P0ZDiLEjPnN46WTFVHKdZuX3bas7Hx1vzpCoVYUiPrXmburrptcAc92 KOCOgCSXnfAQyRbEUBg7IVM7Z4UOmILXn7F99w5Zus0gmukqFT98cqrEqZunjEysJHiI +uiJXYsoAUGHKVGzzXwEt3VkD/l+4x/kcmPM4jc1Vb1MSu0uKt0yMu8vu94utMk6Bc6y 3E0SGe6QqSfVpMnhUDsYYCzKGnuOh6YP/SbbbFTlsCcS/e1wsyRtVvcTIEDXxQZaG+Na qeqw== X-Forwarded-Encrypted: i=1; AJvYcCUQB344zq+Em1o+9Ol6vjFCxfjAzrIGQ3w74TiS8krngfhm1LTfiVSsm4QFxBoDjuwtDKTZqVMzJLTmrAR3@postgresql.org X-Gm-Message-State: AOJu0YzYArkpsNLhGxgIy5fqRXlVyRftMR+F8cgAqoDBAi6Jl9uSvRtZ MvJeotdfDBhYATalSK9f6XADLZaXDM6fr0q5C2/dRr9w4SaU9yh+Wh7o4LOXstBKfsI4mp9pPnw xzBtE37DkRuQf/qTnbPo7fr+s0YTRjOY= X-Gm-Gg: AeBDietKhLcZyzOHzWjoYIKTGsSJyYuYe7ijRxwic8SeuhH5U/U66KPu4W3tvRwPHc5 JjAuAz1b4jsEE4Mu0q+78o9P6UTLHYOvEceq/jOI/2t1SMeFb3Oj7ubqYSGkR87zyW/dD8e8W2e ZO+xC44AUAhosyY2sqdIOteyQql8ZO79pv1H3+g2ZORcn03uLF/P+InjfiusvnQ6BtyBaXxYljT YGfLS68EG6SjoxGCgG3zzj+HMOQBeADGH5fC8CAj9fAMN0bIUhdgSS9BYs3hJ+rzoWQd8NzoZDx c5uU7jqdyNPWNil9ktfYDLBcpwnhB8iOYWgs6A== X-Received: by 2002:a17:90b:268b:b0:35b:a170:f266 with SMTP id 98e67ed59e1d1-35de68292e6mr5334287a91.13.1775287886035; Sat, 04 Apr 2026 00:31:26 -0700 (PDT) MIME-Version: 1.0 References: <20260322.142326.546998002680149319.ishii@postgresql.org> <20260330.133428.1197197778850463943.ishii@postgresql.org> In-Reply-To: Reply-To: assam258@gmail.com From: Henson Choi Date: Sat, 4 Apr 2026 16:31:13 +0900 X-Gm-Features: AQROBzDz8Ovn1SUKZtoM3VmCs4XTZIHgS-VqqLsL5oRhrT5yrRmkGY1ntCjWeew Message-ID: Subject: Re: Row pattern recognition To: Tatsuo Ishii Cc: zsolt.parragi@percona.com, sjjang112233@gmail.com, vik@postgresfriends.org, er@xs4all.nl, jacob.champion@enterprisedb.com, david.g.johnston@gmail.com, peter@eisentraut.org, pgsql-hackers@postgresql.org Content-Type: multipart/alternative; boundary="000000000000d244b3064e9d6be6" List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --000000000000d244b3064e9d6be6 Content-Type: text/plain; charset="UTF-8" Hi hackers, I'd like to propose an extension to the context absorption optimization for Row Pattern Recognition in the window clause: fixed-length iteration group absorption. This builds on the two-flag absorption design [1] and three-phase execution framework [2], and is a sibling optimization to PREFIX pattern absorption [3]. The existing framework requires group children to have exactly {1,1} quantifiers. This relaxes the constraint to accept any fixed-length quantifier (min == max), allowing patterns like (A B{2})+ and (A (B{2} C){4})+ to benefit from absorption with no runtime changes. PREFIX absorption [3] handles fixed-length elements before the unbounded repetition; this handles fixed-length elements inside the unbounded group. [1] Context absorption design - two-flag approach https://www.postgresql.org/message-id/CAAAe_zCmjDRf9u19xRRbtzq%2B-7ujqadZk0izz0mkef2j%2BWpBBA%40mail.gmail.com [2] Three-phase absorption framework (Match -> Absorb -> Advance) https://www.postgresql.org/message-id/CAAAe_zAGLOF_qporKahnL8ajSu_eXZYsJN2M1cEeF5n5GWSNdQ%40mail.gmail.com [3] PREFIX pattern absorption https://www.postgresql.org/message-id/CAAAe_zDq7R8CaDfmh8C%2BH3_639Y5LtJD%2B2Z%3D1txDt%3DvaOr90rQ%40mail.gmail.com [4] FIRST/LAST navigation design note https://www.postgresql.org/message-id/CAAAe_zCUrKGBgZdaazdO_v9QWHsS_1DXuP%3DrLeNhO3iwsHwwbg%40mail.gmail.com Design Note: Fixed-Length Iteration Group Absorption ===================================================== 1. Problem Definition ===================== 1.1 Current Absorption Scope Context absorption currently requires that children of an unbounded group have exactly {1,1} quantifiers. This means only simple patterns like (A B)+ qualify for absorption. Patterns like (A B{2})+ or (A (B{2} C){4})+ are excluded even though each iteration consumes a fixed number of rows. 1.2 The Fixed-Length Constraint The existing {1,1} check is overly restrictive. The actual requirement for absorption is that each iteration of the group consumes a fixed number of rows, so that the count-dominance property holds: an older context always has a repeat count >= any newer context at the same element. Any group where all children have min == max (recursively) satisfies this property, regardless of nesting depth or quantifier values. 2. Relationship to the Existing Framework ========================================== 2.1 Position in the Three-Phase Execution Model The Match -> Absorb -> Advance model [2] is preserved as-is. This optimization only changes compile-time eligibility analysis in the two-flag framework [1]; the Absorb phase logic is unchanged. 2.2 Prerequisites The same four prerequisites as existing absorption apply: 1. Greedy quantifier -- the outer group must be greedy. 2. SKIP TO PAST LAST ROW -- prior matches suppress subsequent start points. 3. UNBOUNDED FOLLOWING -- all contexts see the same future rows. 4. Shared DEFINE evaluation -- all contexts produce the same DEFINE result for a given row [4]. 2.3 Extension of the Dominance Order The existing dominance condition is unchanged: C_old and C_new are in the absorbable region of the same element, and C_old.counts >= C_new.counts. The only change is which patterns are recognized as having an absorbable region. The runtime count comparison works identically regardless of the step size per iteration. 3. Correctness Argument ======================== A fixed-length quantifier (min == max) is semantically equivalent to repeating the element that many times. Therefore any pattern with fixed-length children can be conceptually unrolled to {1,1} elements: (A B{2})+ -> (A B B)+ (A (B{2} C){4})+ -> (A B B C B B C B B C B B C)+ ((A{2} B{3}){2})+ -> (A A B B B A A B B B)+ The unrolled form contains only {1,1} VARs inside the unbounded group, which is exactly the existing Case 2 that is already proven correct for absorption. This optimization recognizes fixed-length groups at compile time without actually unrolling them. The runtime behavior is identical to the unrolled form: each iteration consumes a fixed number of rows, count-dominance holds, and absorption proceeds unchanged. 4. Compile-Time Analysis ========================= 4.1 Change to isUnboundedStart() Currently, Case 2 in isUnboundedStart() requires all children of an unbounded group to be simple {1,1} VARs. The relaxation: - VAR children: accept min == max (any value) - BEGIN children (nested subgroups): recursively verify that all descendants have min == max, including the subgroup's own END quantifier - ALT children: reject (unchanged) The check follows the existing depth-based traversal of the flat element array. 4.2 Flat Array Example Pattern: (A (B{2} C){4})+ [0] BEGIN depth=0 min=1 max=INF <- outer group [1] A depth=1 min=1 max=1 <- 1==1 OK [2] BEGIN depth=1 min=4 max=4 <- subgroup [3] B depth=2 min=2 max=2 <- 2==2 OK [4] C depth=2 min=1 max=1 <- 1==1 OK [5] END depth=1 min=4 max=4 <- 4==4 OK [6] END depth=0 min=1 max=INF <- unbounded, greedy Verification traverses [1]-[5] confirming min==max at every level. [6] is the outer END: unbounded and greedy, so absorption applies. 4.3 Runtime: No Changes The runtime absorption logic (nfa_try_absorb_context, nfa_states_covered) and flag assignment (RPR_ELEM_ABSORBABLE, RPR_ELEM_ABSORBABLE_BRANCH) require no changes. 5. Worked Example ================== Pattern: (A B{2})+ Step size = 1 + 2 = 3. Data: rows match in repeating A, B, B cycle. Contexts that fail A at B-rows die immediately (omitted). Row Data C_old C_new Active r0 A A - 1 r1 B B(cnt=1) - 1 r2 B B(cnt=2)->END - 1 count=1, loops r3 A A A 2 r4 B B(cnt=1) B(cnt=1) 2 r5 B B(cnt=2)->END B(cnt=2)->END 2 count=2 count=1 absorb: 2 >= 1 -> C_new absorbed C_old loops 1 r6 A A A 2 r7 B B(cnt=1) B(cnt=1) 2 r8 B B(cnt=2)->END B(cnt=2)->END 2 count=3 count=1 absorb: 3 >= 1 -> C_new absorbed C_old loops 1 Absorption occurs at END (the ABSORBABLE judgment point), where both contexts synchronize after completing one full iteration. The older context has a strictly higher group count and absorbs the newer one. Between END points, both contexts progress in lockstep at the same pattern positions. Maximum concurrent contexts during this phase = 2. Overall complexity remains O(n). 6. Non-Qualifying Patterns =========================== Patterns where any child has min != max do NOT qualify: (A B+ C)+ -- B+ has min=1, max=INF -> NOT fixed (A B{2,5})+ -- B has min=2, max=5 -> NOT fixed (A B?)+ -- B? has min=0, max=1 -> NOT fixed These patterns have variable step sizes per iteration, so count-dominance is not guaranteed. They remain non-absorbable under this optimization. --000000000000d244b3064e9d6be6 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi hackers,


I'd like to propose an extensio= n to the context absorption
optimization for Row Pattern Recognition in = the window clause:
fixed-length iteration group absorption. This builds = on the
two-flag absorption design [1] and three-phase execution
frame= work [2], and is a sibling optimization to PREFIX pattern
absorption [3]= .

The existing framework requires group children to have exactly
= {1,1} quantifiers. This relaxes the constraint to accept any
fixed-lengt= h quantifier (min =3D=3D max), allowing patterns like
(A B{2})+ and (A (= B{2} C){4})+ to benefit from absorption
with no runtime changes.

= PREFIX absorption [3] handles fixed-length elements before
the unbounded= repetition; this handles fixed-length elements
inside the unbounded gro= up.


[1] Context absorption design - two-flag approach
https://www.postgresql.org/message= -id/CAAAe_zCmjDRf9u19xRRbtzq%2B-7ujqadZk0izz0mkef2j%2BWpBBA%40mail.gmail.co= m
[2] Three-phase absorption framework (Match -> Absorb -> Adv= ance)
https://www.postgresql= .org/message-id/CAAAe_zAGLOF_qporKahnL8ajSu_eXZYsJN2M1cEeF5n5GWSNdQ%40mail.= gmail.com
[3] PREFIX pattern absorption
https://www.postgresql.org/message-id/CAAAe_zDq7= R8CaDfmh8C%2BH3_639Y5LtJD%2B2Z%3D1txDt%3DvaOr90rQ%40mail.gmail.com
[= 4] FIRST/LAST navigation design note
https://www.postgresql.org/message-id/CAAAe_zCUrKGBgZdaazdO_v9QW= HsS_1DXuP%3DrLeNhO3iwsHwwbg%40mail.gmail.com


Design Note: Fi= xed-Length Iteration Group Absorption
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D


1. Problem D= efinition
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D


1.1 Current Absorption Scope

Context absorption curre= ntly requires that children of an unbounded
group have exactly {1,1} qua= ntifiers. This means only simple patterns
like (A B)+ qualify for absorp= tion.

Patterns like (A B{2})+ or (A (B{2} C){4})+ are excluded even = though
each iteration consumes a fixed number of rows.


1.2 Th= e Fixed-Length Constraint

The existing {1,1} check is overly restric= tive. The actual requirement
for absorption is that each iteration of th= e group consumes a fixed
number of rows, so that the count-dominance pro= perty holds: an older
context always has a repeat count >=3D any newe= r context at the same
element.

Any group where all children have = min =3D=3D max (recursively) satisfies
this property, regardless of nest= ing depth or quantifier values.


2. Relationship to the Existing = Framework
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

<= br>2.1 Position in the Three-Phase Execution Model

The Match -> A= bsorb -> Advance model [2] is preserved as-is. This
optimization only= changes compile-time eligibility analysis in the
two-flag framework [1]= ; the Absorb phase logic is unchanged.


2.2 Prerequisites

= The same four prerequisites as existing absorption apply:

1. Greedy = quantifier -- the outer group must be greedy.
2. SKIP TO PAST LAST ROW -= - prior matches suppress subsequent
=C2=A0 =C2=A0start points.
3. UNB= OUNDED FOLLOWING -- all contexts see the same future rows.
4. Shared DEF= INE evaluation -- all contexts produce the same
=C2=A0 =C2=A0DEFINE resu= lt for a given row [4].


2.3 Extension of the Dominance Order
=
The existing dominance condition is unchanged:

=C2=A0 =C2=A0 C_o= ld and C_new are in the absorbable region of the same
=C2=A0 =C2=A0 elem= ent, and C_old.counts >=3D C_new.counts.

The only change is which= patterns are recognized as having an
absorbable region. The runtime cou= nt comparison works identically
regardless of the step size per iteratio= n.


3. Correctness Argument
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D


A fixed-length quantifie= r (min =3D=3D max) is semantically equivalent
to repeating the element t= hat many times. Therefore any pattern
with fixed-length children can be = conceptually unrolled to {1,1}
elements:

=C2=A0 (A B{2})+ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 -> (A B B)+
=C2= =A0 (A (B{2} C){4})+ =C2=A0 =C2=A0-> (A B B C B B C B B C B B C)+
=C2= =A0 ((A{2} B{3}){2})+ =C2=A0 -> (A A B B B A A B B B)+

The= unrolled form contains only {1,1} VARs inside the unbounded
group, whic= h is exactly the existing Case 2 that is already proven
correct for abso= rption.

This optimization recognizes fixed-length groups at compile = time
without actually unrolling them. The runtime behavior is identical<= br>to the unrolled form: each iteration consumes a fixed number of
rows,= count-dominance holds, and absorption proceeds unchanged.


4. Co= mpile-Time Analysis
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D


4.1 Change to isUnboundedStart()
Currently, Case 2 in isUnboundedStart() requires all children of
an unb= ounded group to be simple {1,1} VARs. The relaxation:

- VAR children= : accept min =3D=3D max (any value)
- BEGIN children (nested subgroups):= recursively verify that all
=C2=A0 descendants have min =3D=3D max, inc= luding the subgroup's own END
=C2=A0 quantifier
- ALT children: r= eject (unchanged)

The check follows the existing depth-based travers= al of the flat
element array.


4.2 Flat Array Example

P= attern: (A (B{2} C){4})+

=C2=A0 [0] BEGIN d= epth=3D0 =C2=A0min=3D1 max=3DINF =C2=A0 <- outer group
=C2=A0 [1] A = =C2=A0 =C2=A0 depth=3D1 =C2=A0min=3D1 max=3D1 =C2=A0 =C2=A0 <- 1=3D=3D1 = OK
=C2=A0 [2] BEGIN depth=3D1 =C2=A0min=3D4 max=3D4 =C2=A0 =C2=A0 <- = subgroup
=C2=A0 [3] B =C2=A0 =C2=A0 depth=3D2 =C2=A0min=3D2 max=3D2 =C2= =A0 =C2=A0 <- 2=3D=3D2 OK
=C2=A0 [4] C =C2=A0 =C2=A0 depth=3D2 =C2=A0= min=3D1 max=3D1 =C2=A0 =C2=A0 <- 1=3D=3D1 OK
=C2=A0 [5] END =C2=A0 de= pth=3D1 =C2=A0min=3D4 max=3D4 =C2=A0 =C2=A0 <- 4=3D=3D4 OK
=C2=A0 [6]= END =C2=A0 depth=3D0 =C2=A0min=3D1 max=3DINF =C2=A0 <- unbounded, greed= y

Verification traverses [1]-[5] confirming min=3D=3Dmax at e= very
level. [6] is the outer END: unbounded and greedy, so absorptionapplies.


4.3 Runtime: No Changes

The runtime absorption = logic (nfa_try_absorb_context,
nfa_states_covered) and flag assignment (= RPR_ELEM_ABSORBABLE,
RPR_ELEM_ABSORBABLE_BRANCH) require no changes.
=

5. Worked Example
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D


Pattern: (A B{2})+
Step size =3D 1 + 2 =3D 3.
Data: rows match in repeating A, B, B cycle.
Contexts that fail A at B= -rows die immediately (omitted).

Row =C2=A0= Data =C2=A0C_old =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 C_new =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Active
r0 =C2=A0 A =C2=A0 =C2=A0 A =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 - =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A01
r1 =C2=A0 B =C2=A0 =C2=A0 B(cnt=3D1)= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0- =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A01
r2 =C2=A0 B =C2=A0 =C2=A0 B(cnt=3D2)->END =C2=A0 = =C2=A0 - =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A01
=C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0count=3D1, loops
r3 =C2=A0 A =C2=A0 = =C2=A0 A =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 A =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A02
r4 =C2=A0 B =C2=A0 =C2= =A0 B(cnt=3D1) =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0B(cnt=3D1) =C2=A0 =C2=A0 = =C2=A0 =C2=A0 2
r5 =C2=A0 B =C2=A0 =C2=A0 B(cnt=3D2)->END =C2=A0 =C2= =A0 B(cnt=3D2)->END =C2=A0 =C2=A02
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0count=3D2 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0count=3D1
=C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0absorb: 2 >=3D 1 -> C_new absor= bed
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0C_old loops =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A01
r= 6 =C2=A0 A =C2=A0 =C2=A0 A =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 A =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A02
r7 = =C2=A0 B =C2=A0 =C2=A0 B(cnt=3D1) =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0B(cnt= =3D1) =C2=A0 =C2=A0 =C2=A0 =C2=A0 2
r8 =C2=A0 B =C2=A0 =C2=A0 B(cnt=3D2)= ->END =C2=A0 =C2=A0 B(cnt=3D2)->END =C2=A0 =C2=A02
=C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0count=3D3 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0count=3D1
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0absorb: 3 >=3D = 1 -> C_new absorbed
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0C_old lo= ops =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A01

Absorption occurs at END (the ABSORBABLE judgm= ent point),
where both contexts synchronize after completing one fulliteration. The older context has a strictly higher group
count and abso= rbs the newer one.

Between END points, both contexts progress in loc= kstep
at the same pattern positions. Maximum concurrent contexts
duri= ng this phase =3D 2. Overall complexity remains O(n).


6. Non-Qua= lifying Patterns
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D


Patterns where any child has min != =3D max do NOT qualify:

=C2=A0 (A B+ C)+ = =C2=A0 =C2=A0-- B+ has min=3D1, max=3DINF -> NOT fixed
=C2=A0 (A B{2,= 5})+ =C2=A0-- B has min=3D2, max=3D5 -> NOT fixed
=C2=A0 (A B?)+ =C2= =A0 =C2=A0 =C2=A0-- B? has min=3D0, max=3D1 -> NOT fixed

T= hese patterns have variable step sizes per iteration, so
count-dominance= is not guaranteed. They remain non-absorbable
under this optimization.<= br>
--000000000000d244b3064e9d6be6--