sequenceover

Sequenceover is a term used in mathematics and computer science to denote a sequence whose elements are drawn from a specified set, typically called an alphabet. More formally, let S be a set. A finite sequence over S of length n is a function from the index set {1, ..., n} to S, and is commonly written as (a1, a2, ..., an) with ai in S. An infinite sequence over S is a function from the natural numbers to S and is written (a1, a2, a3, ...).

Notation and concepts: The set of all finite sequences over S is denoted S*, and the set of all infinite sequences over S is Sω. When S is an alphabet, sequences over S are often called words, strings, or simply sequences. The phrase sequence over is widely used in formal language theory and combinatorics.

Examples: A sequence over {0,1} of length 5 is 01001. An infinite sequence over {a,b} could be (a, b, a, a, b, ...).

Applications: Sequences over an alphabet underpin formal language theory, automata theory, coding theory, and cryptography. They also underpin data encoding and many string-processing algorithms. In programming, strings are treated as sequences over a character set and support operations such as concatenation, indexing, and slicing.

Variants: Finite versus infinite sequences; prefixes, substrings, and subsequences are common derived notions. See also: word over an alphabet, formal language, automaton, string, alphabet.