The Setting
A common superstring of an input list is a word containing every word of as a contiguous substring. Write for this containment, including the empty word . The executable construction builds a tour through substring vertices and returns the symbols appended during that tour. Symbol length measures the output objective; encoded bit length measures computation.
Let be the set of symbols appearing in ✦, and let be the set of contiguous substrings of .✦ The input count instance of a list is the triple consisting of the vertex set , the set of required words, and the alphabet , with and given in (1). (1)✦
Forced Counts
A multiplicity table on a vertex set is a function assigning a nonnegative integer to every word and zero to every word outside . The left and right extension multiplicities and of a multiplicity table at a word are the sums in (2). (2)
For a word and a positive period , the candidate periodic text is the integer-indexed text .✦ A blocking occurrence of a word in a word relative to a text is a starting position with and at which contains , every interior symbol agrees with , and both endpoint symbols disagree with that alignment.✦ Distinct starting positions count separately, including overlapping occurrences. The blocking sum for a word , a text and a multiplicity table is the sum in (3), where is the number of blocking occurrences of in relative to . (3)✦
The maximum periodic constraint is the maximum of over words and positive integers for which , both and are prefixes of starting at zero, , and . The maximum is zero when there are no such choices. Here is an admissible positive period, rather than necessarily the least positive period.
The word multiplicity update of a table is the table given simultaneously at every word by (4); is the indicator of membership in . (4)✦
The forced count of a word is its multiplicity after the count iteration starts at zero and performs one more update than the maximum vertex length.✦ With denoting that maximum, the total forced letter count is in (5). (5)✦
The Executable Tour
The executable count table starts at zero and performs multiplicity updates.✦ A space-bounded update accepts a new value when its encoded size fits its fixed allowance and otherwise keeps the old value.✦ Write for the encoded bit length of , for that of the enumerated vertex list, and for the total input symbol length. The counting allowance is (6). (6)✦
The downward edge word list repeats each vertex according to its downward multiplicity in (7).✦ The counts on the right are the computed table values. (7)✦
An indexed word token in the downward edge word list is a word together with its position in that list as identifier. The suffix request of an indexed word token is the token obtained by retaining its identifier and deleting its word’s first symbol.✦ Greedy prefix matching repeatedly chooses the earliest longest outstanding request and the first available token whose word extends that request as a prefix, using the empty word with identifier zero if none qualifies.✦ It removes the selected tokens and records their pair. The matched identifiers give the successor edges of the computed thread representation.✦
For a collection of indexed word tokens, the thread signature of a token is the list of first symbols at its next successor iterates, starting at that token.✦ Two tokens are compatible when one signature equals the other’s after fewer than successor steps.✦ Each group uses its least compatible index as representative.✦ Aligned indices have identical signatures.✦ For tokens, the group period is the least returning step between one and for its signature, taking zero if none exists✦; its period word is the signature prefix of that length.✦ The exit lengths of its layers are the ranked word lengths among aligned indices at each successor phase.✦ The thread collection environment has the group layer data at every token index, with the least compatible indices as its active groups.✦
A periodic layer consists of a period word and a list of exit lengths.✦ For nonempty , put and .✦ Extend periodically with period , taking the zero function for an empty list, and write this extension as . For a periodic layer with periodic exit-length function and an integer , the exit coordinate is ✦, and the preceding exit is .✦ For an integer-indexed text , its finite text window is the word of symbols at the integer positions from through , and is empty when . The layer contents are the windows for and integers . A periodic layer group has one period word and a list of such exit-length lists.✦ The canonical phase of a periodic layer group is the first phase giving a lexicographically greatest rotation of its period word.
The cyclic shift of a period word by displacement is the word of length read from its periodic text starting at .✦ The periodic text inequality test for period words and displacement compares the windows of length starting at zero in the text of and at in the text of , and accepts when those words differ.✦
The single position passage at phase appends symbols from the preceding exit to the current exit while keeping start , then deletes the first symbol to advance the start to .✦ The periodic segment walk from phase with steps starts at the window from to its preceding exit and follows the single position passages at .✦ The one period layer tour of period word and exit lengths is the periodic segment walk starting at phase zero and taking steps in the periodic text of .✦
A hierarchical path in a vertex set is a finite walk all of whose vertices belong to , whose up steps append one symbol and whose down steps delete the first symbol; a zero-edge path stays at a vertex of .✦ The cost of a hierarchical path is its number of up steps.✦ The written word of a hierarchical path is the word obtained by concatenating precisely its appended symbols, in traversal order.✦ A word is visited by a hierarchical path when is an actual vertex of , including either endpoint.✦ An occurrence within a visited word is ordinary substring containment. A substring graph walk is a finite list of words recording its successive vertices.✦ The graph walk validity test accepts a nonempty vertex list exactly when all its vertices are allowed and each consecutive pair appends one symbol or deletes the first symbol.✦
Walk concatenation omits the repeated junction vertex.✦ Tour splicing inserts a cyclic rotation of one tour at the first shared vertex of the other.✦ Rooting a tour at a word appends from , follows the rotated tour from , and deletes first symbols back to .✦ Rooting a tour at a short word uses the first vertex within the specified length bound, or the initial vertex if none qualifies; an empty vertex list uses the empty word.✦
The successive symbol appending walk for words lists followed by each prefix of , beginning with and ending with .✦ The successive symbol deletion walk for words starts at and successively deletes the first symbols, ending at .✦ The rooted word excursion of a word appends from and then deletes its first symbols until it returns to .✦ The isolated symbol excursion of a word starts at . It handles each symbol in order by appending that symbol and immediately deleting it. Rooted tour concatenation successively concatenates a list of walks, starting with the singleton empty-word tour.✦ Successive tour splicing inserts a list of tours into a starting walk in their listed order.✦
Selected layer saturation of a walk successively splices into it the one period layer tours of the selected layers.✦ Complete layer saturation of a walk successively splices into it the one period layer tour of every layer in a given list.✦ The saturated rooted word tour of a word and selected layers is the selected layer saturation of the rooted word excursion of .✦
The window suffix appending walk from coordinates appends the word to the window word .✦ The window prefix deletion walk for coordinates deletes the prefix word while retaining the word .✦ The window connection walk from to first deletes to start and appends to stop when ; when , it deletes to the empty window at , makes the isolated symbol excursion on , and appends .✦ Successive window connections begin at a specified window and follow the window connection walks between consecutive windows in a given list.✦ Endpoint sum ordering lists windows stably by increasing sum of their two endpoints.✦ The ordered window traversal connects an initial window through a list of windows in endpoint sum order and then to a specified final window.✦
A collection context consists of the allowed vertices, the periodic layer groups with their active indices, and the completion search bound .✦ The walk , closure blocks and layer transfer requests form a collection plan.✦ A closure block specifies its assigned layers and internal walk, possible linking walks, source and target identifiers, overlap word, period and reserve.✦ A transfer request specifies its source group, target layer, source layer indices and overlap record.✦ An overlap record is a displacement together with the start and stop of a half-open overlap interval.✦ The plan budget is the current walk cost plus the reserves of its blocks and requests✦, and an unprocessed group has an allowance of twice its layer count times its period.✦ The remaining collection budget is the current plan budget plus the sum of the allowances of all unprocessed groups.✦
A layer catalogue is a list of layers, each given by a period word and a list of exit lengths✦; the global layer catalogue lists the layers of the collection environment.✦
An overlap record with displacement and interval is valid for source and target period words when , their periodic text windows agree on and , and lies between the target exit coordinates immediately before and at .✦ For target period bound , search bound and phase , the bounded overlap record candidates have displacement with , start with , and stop with .✦
The reserve of an assembled block or request with layers of period is . (8)✦
The group sweep starts with the singleton empty-word tour and no blocks or requests.✦ For a group and an index cutoff, the upper layers are those whose indices are at least the cutoff and below the group layer count.✦ The group sweep processes the first remaining group of minimum period, handles its incoming requests, and completes its remaining upper layers. Each update appends the resulting walk and blocks and replaces the processed requests by the outgoing ones. There is one space-bounded scheduler update per initially active group.✦
The rooted upper layer tour saturates the rooted word excursion of the window from the specified phase to the preceding exit of the top layer, using the selected upper layers.✦
The short words of a layer are its content words whose symbol length is at most its period word length✦; the short layer word test accepts exactly when this list is nonempty.✦ The short word layer tour saturates the rooted excursion of the first short word with that layer, taking the empty word if the list of short words is empty.✦
For lower and upper exit functions, put and . The geometric band walk stays at when ; otherwise it appends to and connects to , where is its displacement multiplier and its period.✦ The saturated band walk is the selected layer saturation of the geometric band walk for the specified boundary layers.✦ Layer band attachment splices the saturated band walk into the current walk, with displacement multiplier equal to the number of selected layers.✦
Let be a layer exit function, a period and an overlap interval, and put . The geometric individual walk connects the overlap window to and then appends to stop .✦ The saturated individual walk is the selected layer saturation of the geometric individual walk, using just the specified layer.✦
For upper exit function , period , layer count and overlap interval , put . The geometric collective walk appends from the overlap window to stop and then connects to .✦ The saturated collective walk is the selected layer saturation of the geometric collective walk for the top selected layer, with layer count equal to the number selected.✦
The upper exit function , layer count , period , overlap interval and phase determine and . The geometric short sweep deletes the overlap prefix to start , appends to stop , and connects to .✦ The saturated short sweep is the selected layer saturation of the geometric short sweep for the specified upper layer, with layer count equal to the number selected.✦
An individual closure block assigns one layer its one period layer tour as internal walk and its saturated individual walk as its sole linking walk.✦ A collective closure block for selected layers has the saturated band walk with displacement multiplier as its internal walk, and the saturated collective walk and saturated short sweep as its linking choices.✦
A layer distribution result consists of a walk, a list of closure blocks and the indices of layers left for transfer.✦ Single layer distribution returns the short word layer tour when a short content word exists; otherwise it creates an individual closure block when the overlap stop is at most the exit at the overlap start plus one period, and leaves the layer for transfer in the remaining case.✦ Multiple layer distribution distributes each selected layer individually, concatenates their rooted tours, and concatenates their block and transfer lists.✦ Overlap record distribution selects the layers at or above its lower boundary. If the overlap stop is at most the exit of that boundary layer at the overlap start plus the selected layer count times the period, it creates a collective block for those layers and distributes the lower layers individually; otherwise it distributes every layer individually.✦
Upper completion parameters specify a layer count, a target index in the layer catalogue and an overlap record.✦ Upper completion candidates range over layer counts from zero through the group layer count, target indices in the supplied list, and bounded overlap records whose displacement bound is the target period word length.✦ An upper completion candidate selecting layers in an -layer group with cutoff , period and phase is admissible when , its overlap record is valid, and its overlap interval contains . It also requires the top preceding exit at to be at most , its difference from the exit at of layer to be at most , and the preceding exit at of every upper layer below to be at most . The foreign periodic text test accepts an upper completion candidate when the periodic text inequality test distinguishes the group word from the selected target word at the recorded displacement.✦ For a supplied target predicate, admissible upper completion selection takes the first candidate satisfying both the upper completion admissibility test and that predicate, using zero for the count, target and overlap record when none qualifies.✦ The solver uses the foreign periodic text test as its target predicate.
The hard case collection plan retains the walk and blocks of overlap record distribution and, when any layers remain unassigned, creates one transfer request containing those layers and the selected overlap record.✦ For remaining upper layers of period at phase , let be the top preceding exit at . Upper layer completion keeps the current walk when , otherwise concatenates the rooted upper layer tour when , uses layer band attachment when the cutoff is positive and minus the exit at immediately below the cutoff is at most , and uses the hard case collection plan in the remaining case.
A host overlap entry specifies a source identifier, a period word, an overlap interval and a required coverage endpoint.✦ A request host entry for a source layer uses the source group as identifier, cyclically shifts its period word by the recorded displacement, and adds that displacement to the overlap endpoints and to the source layer preceding exit at the overlap start.✦ The shifted preceding exit is its required coverage endpoint. The host entry expansion of a request list contains one request host entry for each source layer listed in each request, in request order and then layer order.✦
Request attachment data consist of a period word, a source window and an attachment window.✦ Relative to a base host entry with interval in a host of period , an entry with interval , coverage endpoint and period word length has source window and attachment window .✦
Periodic normalization relative to a base interval shifts an entry interval so that its new start is the least integer at least congruent to modulo the host period, and adds one further host period if its new stop is below . The same displacement cyclically shifts the entry word and translates its coverage endpoint.
For source window , attachment window and period , the shifted window attachment connects to and then to .✦ The periodic request attachment is the shifted window attachment in the periodic text of the request period word, with that word length as period.✦
The host window excursion starts at , appends to stop , traverses the attachment windows in endpoint sum order, and connects the last window to for host period ; an empty list uses as its last window.✦ The rooted host excursion successively splices the periodic request attachments into the host window excursion and roots the result at the first word within its specified length bound.✦
The normalized host tour uses a chosen base entry to set its overlap interval, coverage endpoint and rooting bound, taking the latter as the base period word length, and builds attachment data for entries from other sources.✦ The normalized request tour first normalizes every host entry relative to the chosen base entry using the host word length as period, then forms the normalized host tour.✦ The host request tour candidates take each host overlap entry in turn as the base of a normalized request tour.✦ The saturated host tour candidates apply complete layer saturation to every host request tour candidate, using the host layer and all requested layers.✦
Recipient tour selection takes the first admissible saturated host tour candidate for a target layer and the requests directed to it, using the empty walk when none qualifies.✦ A recipient tour is admissible when it is a valid tour rooted at , visits every content word of its target layer and of all requested source layers, and costs at most twice the target group period plus the sum of the request reserves.✦
The incoming request tour concatenates the selected recipient tours, starting at , for all layers of the group that receive requests.✦ Lower layer preparation returns cutoff zero and the incoming request tour when no layer receives requests. Otherwise it takes the cutoff just above the highest recipient layer and attaches the missing lower layers by a band, using the overlap interval of the first request to that highest layer after translating it by the recorded displacement.
Completion storage sizes are the encoded sizes of the block and request parts of upper layer completion from the empty rooted tour, over every active group and every cutoff from zero through its layer count.✦ Their maximum, with zero for an empty list, is the maximum completion storage.✦
With context, active-index, pending-request and vertex-list encoding lengths , remaining collection budget , active group count and maximum completion storage , the scheduler workspace bound is .✦
For a group with layers and a completion candidate selecting layers, the hard case distribution applies overlap record distribution to the upper layers, with lower boundary , upper boundary , the selected overlap interval and the canonical group phase.✦
Block closure chooses the first admissible action among single block actions and paired block actions, retaining the current walk if none qualifies.✦ A candidate walk must be a valid tour rooted at , preserve every old vertex, and visit all contents of the removed blocks’ layers. Its cost may exceed the old cost by at most the removed blocks’ reserves. For a block and current tour , the single block actions remove and either concatenate with its internal walk rooted at a word of length at most its period, or splice one of its linking walks into .✦ For distinct blocks , the paired actions remove both blocks, splice the internal walk of into a linking walk of , root the result using the period of as length bound, and concatenate it to .✦ Closure performs one space-bounded update per initially remaining block.✦ For closure input encoding length , current walk cost and total remaining block reserve , the closure workspace bound is .✦
Let be the completed collection tour obtained by closing the sweep for the computed context.✦ The executable solver is defined by (9). (9)✦
Bit Complexity
A linearly parsable binary code assigns distinct bit strings to distinct values and admits a prefix scanner taking at most a constant times one plus the consumed code length.✦ The scanner is a bit stack program that consumes one value’s code, leaves the following suffix untouched, and transfers the reversed code to an accumulator, with all private stacks empty initially and finally.
A bit stack program is built from pushes, pops, idle instructions, sequential composition, branches selecting according to whether a designated stack is empty or has top bit zero or one, and loops repeating their body while a designated stack is nonempty. Each push, pop or idle instruction costs one; a branch costs one in addition to its selected execution, sequential executions add their costs, and a loop charges one for each test.✦ Polynomial-time computability means that a fixed such program takes an input code on one initially populated stack to the output code on one populated stack, with instruction count bounded by a polynomial in the input code length.✦ All other stacks are empty initially and finally.
The Claim
Theorem 1. Let the symbols have a linearly parsable binary code and a total order whose comparison predicate on encoded pairs is polynomial-time computable. The solver has a bit stack implementation and a polynomial satisfying (10) for every finite input list of encoded bit length , where denotes the chosen binary encoding and denotes the instruction count of on its encoded input. (10)✦ For every finite input list , with its forced letter count , (11)✦ Let be a hierarchical path from to in any vertex set. Then (12)✦ If visits a word , then (13)✦
What Is Checked
The solver assertions (10) and (11) concern finite input lists and their input count instances, with the coding and comparison assumption for the time bound; the path assertions (12) and (13) concern arbitrary hierarchical paths in a vertex set, with their specified initial word and actual vertex visitation.