Codex @codex  0

Official source: docs.oracle.com/javase/8/docs/api/java/lang/Double.html

Relevant locator: isFinite(double), parseDouble(String) and toString(double): finite-number validation and numeric text helpers.

Jeffrey Scott Vitter coauthored the 2003 work on entropy-compressed text indexes with Roberto Grossi and Ankur Gupta. It develops compressed suffix-array representations and introduces a wavelet tree representation for symbol sequences. Bitvectors route a position through alphabet partitions, with rank queries translating that position into the selected subsequence. This connects compressed storage to efficient indexing rather than requiring full decompression for every query.^[ref]

John Hopcroft gave a 1971 algorithm for minimizing deterministic finite automata with running time $O(|\Sigma |n\log n)$ for $n$ states and alphabet $\Sigma$. It refines partitions of states until states in the same block accept exactly the same continuation strings.^[ref]

The key accounting idea is to organize refinement around smaller splitters. A transition can then be charged to only logarithmically many successively smaller blocks, instead of rescanning every state in every refinement round. DFA minimization preserves the recognized language while merging observationally equivalent states, making representation size and equivalence checking algorithmic questions.

The equivalence relation used to decide whether two keys name the same record. A hash function must respect key equality; a hash collision does not establish key equality.

The choice of key equality is part of the map's meaning. In the one-value-per-key policy of hash table, one record represents each stored equivalence class of keys: put(k,v) updates an existing equal key and adds a record only if no equal key is present. A collection that deliberately retains repeated equal keys has a different policy; its load count must count those extra records too. Repeated calls and distinct stored records are different quantities.^[ref]

For an original example, restrict keys to two-letter strings using letters A through Z or a through z. Declare two keys equal when replacing every uppercase letter by its lowercase counterpart gives the same string. Assign each letter its position $1,\dots ,26$ in the alphabet, ignoring case, and define the bucket-index hash function as the sum of the two positions modulo $8$, using modular arithmetic. Then AB and ab are equal keys and both select hash bucket $3$. Key ba also selects hash bucket $3$ because $2+1=3$, but is unequal to ab: order still matters. Starting empty, put(AB,7), put(ab,9), put(ba,4) leave two records, with values $9$ for the ab equivalence class and $4$ for ba; the hash table load factor is $2/8=1/4$, not $3/8$.

The compatibility rule is one-way: $x\sim y\Rightarrow h_m(x)=h_m(y)$. Otherwise a lookup using an equal spelling could search a different hash bucket and incorrectly report absence. Equal indices merely allow a key equality check. Both the equivalence relation and the hash function must stay consistent while records are stored; changing equality-relevant key contents can invalidate the lookup rule. The Java contract imposes these consistency and equality requirements on equals and hashCode.^[ref]

The length of a word over an alphabet is the number of symbol positions in that finite string, counting repetitions. Thus $\ell (abba)=4$ and $\ell (\epsilon )=0$ for the empty word. Concatenation satisfies $\ell (uv)=\ell (u)+\ell (v)$. This differs from the word length of a group element, which minimizes over representing words using a chosen generating set of a group.

A maximal consecutive run of occupied or deleted slots in linear probing, bounded by never-used slots when any exist; adjacency wraps around by modular arithmetic. Deleted slots still belong to the search run.^[ref]

In the eight-slot example, array indices $0,1,2,3$ form one linear probing cluster. Inserting absent hash table key $10$ starts at $2$, passes the occupied slots $2,3$, and fills $4$. This extends the same linear probing cluster despite $10$ having a different initial array index from $0,8,16$. A hash collision at the initial slot is enough to make later slots compete too.

For a worst-case family, insert integer hash table keys $0,m,2m,\dots ,(n-1)m$ into an empty capacity-$m$ array, using the hash function $h_m(k)=k\mathrm{mod}m$, where $1\le n<m$. They occupy array indices $0,\dots ,n-1$. Lookup of absent $nm$ needs $n+1$ hash table probes. Taking $n=\lfloor m/2\rfloor$ gives hash table load factor at most $1/2$ while the number of hash table probes grows with $m$. Thus occupancy alone cannot promise constant lookup work.

Before any rebuilding, bounded lookup, deletion by hash table key, and insertion with a duplicate check each have worst-case $O(m)$ time complexity in Big O notation, assuming constant-cost hash function evaluation, array access and key equality. The counterexample gives a matching linear worst-case growth in the number of hash table probes. Hash table resizing is additional work; expensive string comparisons or hashing also fall outside these constant-cost assumptions.

Choose one contiguous substring from each string and align them under the same matching and gap rules as global sequence alignment without mismatches. Let $L_{i,j}$ maximize the score over aligned suffixes of the two prefixes. Zero permits a fresh empty alignment; the other cases extend one ending at adjacent prefix indices. The answer is the largest table entry, which can occur before either input ends. Starting all boundaries at zero yields $O(mn)$ time for positive lengths. Alignment traceback stops on reaching zero.

The longest common prefix of two strings is the longest string that is a string prefix of both. Its length is the number of matching initial characters before the first mismatch or the end of a string. A direct scan maintains equality of the processed prefixes and takes time linear in that length plus one. For suffixes represented by indices in a shared array, no character copying is needed.

A longest repeated substring is a maximum-length contiguous string occurring at two distinct starting positions in a text. The occurrences may overlap unless a nonoverlap constraint is explicitly imposed. It can be found by comparing all pairs of suffixes, or by taking the maximum longest-common-prefix length of adjacent entries of a suffix array. The latter characterization concerns correctness; the time needed to build the suffix array depends on the construction algorithm.

Margaret J. Corasick coauthored the 1975 multi-keyword matching algorithm with Alfred V. Aho. Their Aho-Corasick algorithm builds a finite-state keyword-matching machine and scans the text once, reporting occurrences of all dictionary patterns.^[ref]

A trie shares pattern prefixes, while failure links retain the longest useful suffix after a mismatch. For patterns he and she, reaching the end of she must also report he; terminal suffix information is therefore part of matching, not merely following trie edges. The mechanism makes one text scan reusable across many search terms.

ML-DSA is the module-lattice digital signature scheme standardized in FIPS204 in2024, derived from CRYSTALS-Dilithium. Key generation creates a public verification key and a secret signing key. Signing combines a sampled masking vector with a message-derived challenge; bounds and rejection sampling prevent unsuitable responses from revealing the secret. Verification reconstructs the commitment information and checks the challenge and response bounds.^[ref]

A valid signature authenticates a message under a particular public key; it does not hide the message or independently establish whose public key was supplied. The standardized parameter sets ML-DSA-44,65 and87 have different key/signature sizes and security targets. Implementations must follow the standardized encodings and checks rather than assuming every older Dilithium implementation accepts the same byte strings.

A monoid is a semigroup with a two-sided identity element $e$: $e\ast a=a\ast e=a$ for every element $a$. Associativity handles the grouping of a nonempty sequence; the identity element also supplies the result for an empty sequence. This makes the same rules apply to combining zero, one, or many contributions. ^[ref].

The nonnegative integers $\{0,1,2,\dots \}$ with addition form a commutative monoid, with identity element zero. They do not form a group: a positive integer has no additive inverse in that set. All words over an alphabet with concatenation form a free monoid, whose identity element is the empty word. The full transformation monoid consists of all self-maps of a set, with function composition and the identity function.

These examples explain why monoids are useful: accumulation needs an operation and a starting value, but it need not be reversible. Adding counts, joining strings, and composing transformations all share the same grouping and identity laws. Requiring every element to have an inverse element gives a group, a stronger structure suitable for reversible operations.

An output link in an Aho-Corasick automaton points to the nearest terminal state encountered strictly after the current state on its failure link chain. It skips states that do not end a pattern string. After reading a text character, report a pattern at the current state if terminal, then follow output links to report its terminal suffixes.

For dictionary strings a, ba, aba, reaching state aba reports all three patterns ending at that position. Its output link reaches ba, and the next reaches a. Reporting only aba would miss two valid occurrences. The current state's own match is handled separately because an output link points to a proper suffix, not to itself.

If $f(q)$ is the failure link destination, the output link is $f(q)$ when that state is terminal, and otherwise the output link of $f(q)$. Build this information in increasing trie depth, so the shorter failure states are already available. Traversing only terminal links makes reporting cost proportional to the number of emitted matches, rather than the length of every nonterminal failure chain.^[ref]

A palindrome is a finite string equal to its reversal. For example, the strings $010$ and $0110$ are palindromes.

Decide whether a finite string is a palindrome by comparing corresponding symbols from opposite ends. The test needs at most half as many symbol comparisons as the string length and can use constant auxiliary space.

Rice's theorem, in its formal language version, says: every nontrivial property of the computably enumerable language accepted by a Turing machine has an undecidable set of machine descriptions. Here nontrivial means that some computably enumerable language has the property and some does not. The property must be an extensional property of programs: any two Turing machines accepting the same formal language must agree about it. It need not be a property of all formal languages, including those no Turing machine accepts.

Let $\mathcal{P}$ be such a property and writeWe prove the theorem by a many-one reduction from the halting problem. First suppose the empty language is not in $\mathcal{P}$. Nontriviality provides a fixed Turing machine $B$ with $\mathcal{L}(B)\in \mathcal{P}$. Given a Turing machine $M$ and a word over an alphabet $w$, effectively construct a Turing machine $N_{M,w}$ which, on input $x$, first simulates $M$ on $w$. If that simulation ever halts, it simulates $B$ on $x$ and accepts precisely when $B$ accepts. If the first simulation never halts, it never accepts $x$.

The Turing machine encoding of $N_{M,w}$ is computable from those of $M,w$: the description merely embeds $M,w$ and the fixed simulator for $B$. Constructing it does not require predicting whether $M$ halts. Its accepted formal language isConsequentlyA decider for $I_{\mathcal{P}}$ would therefore decide the halting problem, a contradiction. Invalid descriptions can be mapped to a fixed description of a machine accepting the empty language, if the many-one reduction is formulated on all strings.

If the empty language does belong to $\mathcal{P}$, apply the preceding argument to the opposite property, within the computably enumerable languages. This opposite property is still nontrivial and excludes the empty language. A hypothetical decider for $I_{\mathcal{P}}$ would decide the opposite property's index set by first rejecting malformed Turing machine encodings and otherwise reversing its answer. The opposite property is undecidable by the first case, giving the required contradiction in this case too.

Entail is co-NP-complete under polynomial-time many-one reductions. For valid propositional formulas, semantic entailment holds exactly when the logical conjunction of the premise and the conclusion's logical negation is an unsatisfiable Boolean formula:A counterexample to semantic entailment is a Boolean valuation making $\phi$ true and $\psi$ false. Guessing one bit for each distinct Boolean variable and evaluating both propositional formulas is a polynomial-time algorithm. Thus the complement of Entail belongs to NP. Malformed descriptions, also in that complement, can be accepted after a deterministic syntax check. Hence Entail belongs to co-NP as a formal language over all strings.

For hardness, the unsatisfiable Boolean formula problem is co-NP-hard: if $A\in \mathrm{co}\text{-}\mathrm{NP}$, then $\overline{A}\in \mathrm{NP}$, and the permitted NP-hardness of SAT supplies a polynomial-time many-one reduction $r$ withWe may ensure $r(x)$ is always a valid propositional formula, replacing any malformed output by a fixed contradiction. It follows that $x\in A$ exactly when $r(x)$ is unsatisfiable. This justifies using the unsatisfiability problem as a hardness source without an extra assumption.

Map a valid propositional formula $\theta$ towhere $p$ is a fixed Boolean variable. The second propositional formula is false under every Boolean valuation. Consequently it is entailed by $\theta$ precisely when no Boolean valuation satisfies $\theta$. ThusThe output has only constant additional length and is computable in polynomial time. If the source unsatisfiability language rejects malformed strings, map them to the fixed no-instance $⟨p,p\wedge \neg p⟩$. This completes a total polynomial-time many-one reduction and proves the claimed co-NP-completeness.

A logspace transducer is a deterministic Turing machine with a read-only input tape, $O(\log (n+2))$ read-write work space, and a write-only output tape. It emits symbols successively and cannot reread the output; that output is not charged as working memory. For a total function it must halt on every input. A logspace-computable function $f$ is a total function whose output $f(x)$ is produced by such a logspace transducer on input $x$.

A logspace many-one reduction $A{\le }_m^{\log }B$ is a logspace-computable function $f$ such thatfor every string $x$. The logarithmic space bound permits a polynomial-length output, even when that output does not fit in work space. Indeed, a halting logspace transducer cannot repeat its state, input-head position and work-tape contents and head positions: the unreadable output cannot affect its subsequent behaviour. There are only a polynomial number of such internal Turing machine configurations, hence a polynomial bound on the number of steps and output symbols.

To prove a formal language $B$ is NL-complete, first give an NL acceptance procedure for $B$. Then show every $A\in \mathrm{NL}$ has a logspace many-one reduction to $B$. Alternatively, reduce one already NL-complete formal language to $B$, using transitivity of logspace many-one reductions.

Transitivity requires logspace composition by recomputation, rather than storing the intermediate output. To compose $g$ with $f$, simulate the logspace transducer for $g$ with a virtual input $f(x)$. Retain its virtual input-head position in $O(\log n)$ bits. Whenever it asks for a symbol, rerun the logspace transducer for $f$ from the beginning and count its output symbols until that position is reached. Since $|f(x)|$ is polynomial in $n$, the simulated work space $O(\log |f(x)|)$ and all output-position counters are $O(\log n)$. Repeated runs reuse their storage. This proves closure under composition and explains why the hardness argument works.

It tests whether the input string is a palindrome: reversing the characters leaves the string unchanged. Comparisons are case-sensitive and include spaces and punctuation. For example, mystery1("level") returns True, whereas mystery1("lever") returns False.

Use start symbol $S$ and an auxiliary symbol $A$ in the context-free grammarThe symbol $A$ generates exactly $\{0,1{\}}^{\ast }$, so every generated string has the three explicitly displayed ones. Conversely, any string with at least three ones can be split at any three of them as $u_{0}1u_{1}1u_{2}1u_3$, and each $u_j$ can be generated by $A$. This proves both inclusions. For example,by taking the four $A$ substrings to be $00$, $0$, $1$, and $0$ respectively.