interstring

Interstring is a term used in several disciplines to denote a construct that results from interleaving two or more sequences into a single representation. The name derives from inter- and string, signaling a mixed or interwoven sequence. There is no universally fixed definition; meanings vary by field, but the core idea is the same: a single string that encodes multiple source sequences and preserves their internal orders.

In formal language theory and combinatorics, an interstring can describe an encoding of an interleaving (shuffle) of two or more words. An interstring often records, for each symbol, which source string it came from, so that the original sequences can be recovered. This perspective is useful in studying concurrent compositions and the combinatorics of interleavings.

In computer science, interstrings appear in models of concurrency and dataflow as a compact representation of interleaved instruction streams or event traces. They help reason about dependencies, synchronization, and potential race conditions by making the interleaving explicit in a single structure.

In data encoding and communications, interstrings can describe multiplexed data where samples from multiple channels appear alternately in one sequence, with markers indicating the channel for each symbol. They are contrasted with single-channel strings that do not carry source information.

See also: interleaving, shuffle, concurrency, dataflow, multiplexing.