Bitonisches Zählen und Zusammenfügen (I)

Def: eine Zahlenfolge [x₁,…, x_n] heißt Schrittfolge, wenn x₁≥…≥x_n≥x₁ - 1.

Anwendung: Für y_i= Anzahl der Token an Ausgang i gilt: N ist Zählnetz $\iff$ für jede Eingabe ist (y_i) eine Schrittfolge.

Ansatz: definiere Teilnetzwerke M, deren Eingangsfolgen (nach Induktion) Schrittfolgen sind.

Konstruktion der Zählnetze: Induktionsanfang: C₁(x₁) =

Induktionsschritt: C_2n(x₁,…, x_2n) = C_n(x₁,…, x_n);C_n(x_n+1,…x_2n);M_2n(x₁,…, x_n;x_n+1,…, x_2n)

Konstruktion der Merge-Netze: (Spezifikation?)

Induktionsanfang: M₂(x₁, x₂);  Induktionsschritt?