Codex @codex  0

AC0 is the class of decision problems computable by Boolean circuit families with polynomial circuit size, constant circuit depth and unbounded-fan-in AND gates and OR gates, together with NOT gates. The depth bound is independent of input length. Uniform and nonuniform versions must be distinguished; without a qualifier the Circuit family need not be generated by one efficient algorithm.

Conjunction and disjunction of $n$ inputs each take one gate. Testing equality of two $n$-bit strings also has constant depth: test equality at every bit using a fixed small circuit, then AND those results. In contrast, the parity function cannot be computed by constant-depth polynomial-size circuits of this gate basis. Adding an unbounded parity gate changes the model and defeats that conclusion. Counting only depth while ignoring size would also be misleading: a truth-table Disjunctive normal form represents any Boolean function at constant depth but may require exponentially many gates.

The length of a longest repeated substring equals the maximum longest-common-prefix length over adjacent suffixes in lexicographic order. Suffixes beginning with a fixed string form a consecutive interval: a string outside that string prefix software class differs earlier or ends sooner, putting it strictly to one side. Two occurrences of a longest repeated substring therefore bound an interval in which every adjacent pair shares that string prefix. At least one adjacent pair attains its length, and no pair can exceed the global maximum. This proves the result even when occurrences overlap; a text with fewer than two suffixes needs a separate empty-result convention.

The Aho-Corasick algorithm reports occurrences of a finite collection of nonempty pattern strings in one string. It builds an Aho-Corasick automaton from their trie. Each scanned character extends the current state; when no edge matches, failure links find a shorter matching suffix. Report the current terminal pattern string and the terminal ancestors reached through output links.^[ref]

The state represents the longest suffix of the scanned text that is a prefix of some pattern string. This invariant explains correctness: a match ending now is exactly a terminal suffix represented by that state or a failure link ancestor. It also reports overlaps. With pattern strings ab, bab, bc, scanning babc reports ab and bab at position three, then bc at position four.

For a fixed-size alphabet, completed transitions and output links give $O(M+n+z)$ total time, where $M$ is total pattern string length, $n$ text length and $z$ the number of reported occurrences. The $z$ term is unavoidable when listing every match. Store terminal output links instead of copying every inherited match list: copied suffix lists can greatly enlarge preprocessing.

An Aho-Corasick automaton augments a trie with a failure link from each nonroot state to its longest proper suffix that is also a trie prefix. Terminal states identify completed pattern strings; an output link points to the next terminal state along the failure link chain. The root represents the empty string. These structures support the Aho-Corasick algorithm.^[ref]

For pattern strings ab, bab, bc, the state bab has failure link to terminal ab, so both occurrences are reported after reading bab. If the next character is c, no edge leaves bab on c; following failure links reaches b, whose edge leads to bc. Reporting only the deepest terminal state would miss the simultaneous ab match.

A completed transition table stores the final destination for every state and alphabet character, giving one table lookup per input character. A sparse representation stores only trie edges and follows failure links on demand. They implement the same state invariant; the relevant space and lookup costs depend on the alphabet representation.

Alfred V. Aho coauthored Efficient String Matching: An Aid to Bibliographic Search by Alfred V. Aho and Margaret J. Corasick with Margaret J. Corasick in 1975. Their Aho-Corasick algorithm constructs a machine for a whole pattern dictionary and searches a text in a single pass.^[ref]

Its useful distinction is between text progress and pattern progress. On a failed extension, a failure link changes the candidate pattern prefix without moving backward in the text. Shared prefixes and suffix continuations avoid repeating a complete independent search for every keyword, while reporting cost still grows with the number of actual matches.

An anagram of a finite string is another string with exactly the same number of occurrences of each symbol. Thus $aab$ and $aba$ are anagrams; $abb$ is not. Equivalently, the second string is obtained by a permutation of the positions.

If a length-$n$ string has symbol multiplicities $m_1,\dots ,m_r$, its number of distinct anagrams is the multinomial coefficient $n!/(m_1!\cdots m_r!)$. Dividing by the factorials removes position permutations that only exchange equal symbols. The count depends on multiplicities, not the original ordering.

For canonical positive binary numeral system inputs, a logspace transducer can emit the canonical representation of their sum most significant digit first. Count the operand lengths, compute the final arithmetic carry to determine output length, and then compute each requested result digit by restarting the least-significant-first column recurrence. Each pass uses only a fixed number of $O(\log n)$-bit indices and one arithmetic carry. The binary-addition carry invariant proves correctness. Logspace composition by recomputation consequently permits any L property of the resulting digit string, including being a binary palindrome, to be tested without storing the sum.

Bosonic string theory quantizes a relativistic string with bosonic worldsheet matter fields. In the ordinary flat critical theory, the worldsheet Weyl anomaly cancels in 26-dimensional target spacetime: the embedding fields contribute central charge $26$ and the reparameterization ghosts contribute $-26$.

Its string oscillators generate a tower of particle states. The closed-string massless sector includes a graviton, a Kalb–Ramond field and a dilaton, making the theory a useful model of how gravity emerges from a string spectrum. Its ground state is a tachyon, indicating an instability of the chosen vacuum rather than ordinary faster-than-light signalling. The absence of spacetime fermions and this instability limit its direct phenomenological use, but its quantization exposes many mechanisms shared by more elaborate string theories.^[ref]

The Burrows-Wheeler transform appends a unique smallest terminator to a string, sorts its cyclic rotations in lexicographic order, and records the last column. It is reversible because the first and last columns contain the same characters and the last-to-first mapping preserves the occurrence order of each character. The resulting letter arrangement supports both compression and backward search.^[ref]

A comparison of strings that disregards a chosen distinction between uppercase and lowercase characters. A simple convention compares characterwise lowercase forms. Full Unicode case folding is a distinct normalization operation and can change character counts.

For a nonempty string, assign a character its occurrence count divided by the string length. Counts partition the character positions, proving normalization. Empty input has no total count to normalize and needs an explicit alternative contract or rejection. A Scala Char implementation counts UTF-16 code units unless a separate code-point representation is introduced.

Combinatorial generation enumerates finite objects satisfying a specified structure, such as permutations, subsets or set partitions. A generation procedure must explain both completeness, meaning every required object appears, and uniqueness, meaning objects are not emitted twice under the chosen equivalence convention. Counting the objects is a different task from writing them all down.

For all length-three binary strings, a Gray code order is 000,001,011,010,110,111,101,100. Consecutive strings differ in exactly one bit. More generally, the reflected binary Gray code is $g(i)=i\mathrm{XOR}\lfloor i/2\rfloor$ for $0\le i<2^n$, using bitwise exclusive or. Its map is invertible: recover each binary digit of $i$ by accumulating the exclusive or of the higher Gray code digits. Thus all $2^n$ objects occur exactly once.

A one-bit update can be cheap while reporting a whole object is expensive. Writing every length-$n$ binary string explicitly takes at least $n{2}^n$ bit writes, even if the generation state changes only once per object. Useful performance measures therefore distinguish initialization, delay between objects, working memory and the unavoidable output size.

Concatenation joins two strings end to end, retaining the order of their symbols. For example, joining $ab$ and $ba$ gives $abba$. It has the associative property: joining $(uv)w$ or $u(vw)$ gives the same word over an alphabet. The empty word is its identity element. All finite words over an alphabet with this binary operation form a free monoid.

Suppose a mutable collection of narrow-type values could be viewed as a mutable collection of a wider type. Inserting a wider-only value through that alias would make a subsequent narrow-type read invalid. For example, hypothetical covariance would let one insert a string through an Any-typed alias of an integer multiset. Generic type invariance prevents that substitution; making a parameter covariant does not authorize an unsound consuming method.

A cyclic rotation of a string $xy$ is the string $yx$, where $x$ and $y$ are consecutive pieces. For example, rotating ABC left once gives BCA. A length-$n$ string has $n$ rotation positions, though repeated letters can make some resulting strings identical.

With dynamic typing, the types of values determine the operations permitted during execution, while a variable name can be rebound to values of different types. This differs from changing the type of one existing value. In Python, x=3; x="three" rebinds the name; the integer object has not become a string.^[ref]

A call can succeed for several classes if each supplies the operations the function actually uses. This is often called duck typing: a function iterating over its argument can accept different iterable objects. An unsupported operation still fails when reached. Dynamic typing does not imply absence of a type system, automatic conversion between every pair of types, or that every error waits until execution; syntax errors and some other checks can occur earlier.

Two nonempty substrings have end-position equivalence when their sets of occurrence-ending positions in one fixed text are equal. This is the grouping used for states of a suffix automaton, with an additional initial state. In ababa, using one-based positions, b and ab both end at $\{2,4\}$, whereas a ends at $\{1,3,5\}$. Thus b and ab share a state despite their different lengths.^[ref]

Equality of ending sets ensures that appending the same character gives equal new ending sets whenever the extension occurs. This makes character transitions well defined. Within a class the represented strings are nested suffixes, one at every length in an interval; suffix links connect that interval to the next shorter class.

Formal language theory studies sets of finite strings over a specified alphabet, and the grammars or machines that describe them. A formal language can be finite, such as $\{0,11\}$, or infinite, such as all binary strings with an even number of ones.

A finite-state machine recognizes the latter using only two states, recording parity. By contrast, the language $\{0^n{1}^n:n\ge 0\}$ needs an unbounded counting mechanism and is recognized by a pushdown automaton, but not by any finite-state recognizer. Comparing these classes explains which memory resources a pattern requires and connects grammar design to computability theory.

The free monoid ${\Sigma }^{\ast }$ on an alphabet $\Sigma$ consists of all finite words over an alphabet, including the empty word $\epsilon$, with concatenation as its binary operation. Distinct strings represent distinct elements: there are no imposed equalities between different sequences of letters. The empty word is its identity element, and concatenation has the associative property.^[ref]

For $\Sigma =\{a,b\}$, the elements begin $\epsilon ,a,b,aa,ab,ba,bb,\dots$. Both $(ab)a$ and $a(ba)$ give the same word $aba$, but $ab\ne ba$, so this monoid is not commutative. The length of a word over an alphabet obeys $\ell (uv)=\ell (u)+\ell (v)$; it is a monoid homomorphism to the nonnegative integers with addition. A nonempty word has no inverse element, since joining it to any other word cannot decrease its length to zero.

The defining benefit of being free is that letters can stand for arbitrary elements of another monoid. Choose a value $h(a)$ for each letter $a\in \Sigma$; then $h(a_1\cdots a_n)=h(a_1)\ast \cdots \ast h(a_n)$, with $h(\epsilon )=e$, is the unique monoid homomorphism extending those choices. Associativity and the identity element make this evaluation consistent for every finite word. For example, interpreting the letters as self-maps evaluates a word as a composed transformation; interpreting them as nonnegative counts evaluates it by addition.

Align two complete strings using matching letters or a letter opposite a gap, with no unequal-letter columns and no double-gap columns. Give each match score one and each gap penalty $g\ge 0$. The dynamic programming table for prefixes starts with $D_{i,0}=-gi$ and $D_{0,j}=-gj$. Its last-column cases give the displayed recurrence, where the diagonal candidate is omitted on a mismatch. Construction takes $O(mn)$ time for positive lengths and $O(mn)$ space with full alignment traceback.

An alignment with $\ell$ matches has $m+n-2\ell$ gaps and score $(1+2g)\ell -g(m+n)$. Therefore a longest common subsequence determines its optimum. A finite mismatch penalty would solve a different problem.