Skip to content

Intersection Non-Emptiness Problem

The decision problem asking whether a finite list of deterministic finite automata accepts at least one common string, a PSPACE-complete problem when the number of automata is part of the input.

Version
v1 · 2026-09-28 · History
Domain-specific #
10118
Domain group
Applied Sciences & Engineering
Origin domain
Computer Science & Software Engineering
Subdomains
Automata Theory, Computational Complexity → Computer Science & Software Engineering
Aliases
Finite Automata Intersection Problem, Common Word Problem

Core Idea

The problem converts conjunction of regular-language constraints into reachability. Every input symbol advances all automata, and success occurs only when the resulting state tuple is jointly accepting.

Finite automata are individually simple, yet the combined state space grows multiplicatively. That succinctly represented explosion explains why the general decision problem occupies PSPACE.

Structural Signature

Sig role-phrases:

  • Finite DFA list — Supplies all constraints whose conjunction is tested. It is input family. Counterfactual: One automaton gives ordinary language nonemptiness.
  • Common alphabet — Defines shared symbols and synchronized transitions. It is symbol domain. Counterfactual: Alphabet mismatches need explicit completion or translation.
  • Product-state tuple — Tracks one current state per automaton. It is combined state. Counterfactual: Explicit enumeration can be exponential in k.
  • Synchronized transition — Applies each input symbol to every component. It is dynamics. Counterfactual: Independent symbol choices would test a different problem.
  • Joint accepting condition — Requires every component state to accept simultaneously. It is goal test. Counterfactual: Union acceptance would require only one component.
  • Reachability search — Determines whether a joint accepting tuple is accessible from starts. It is decision method. Counterfactual: Polynomial space can search without storing the full product.

What It Is Not

  • Pairwise overlap does not guarantee total overlap.
  • It is not the union non-emptiness problem.
  • PSPACE-completeness assumes the automata list is part of the input.
  • An explicit product is conceptually useful but need not be stored in full.
  • Closest near-miss. Pairwise nonempty intersections do not imply the total intersection is nonempty; the defining witness must satisfy every automaton simultaneously.

Scope of Application

  • Formal verification. Checks simultaneous regular constraints.
  • String constraint solving. Tests existence of a common satisfying word.
  • Automata theory. Illustrates complexity under intersection.
  • Complexity reductions. Provides a canonical PSPACE-complete target.

Clarity

State automaton model, common alphabet, completeness conventions, number of automata, input encoding, acceptance condition, whether k is fixed, decision versus witness output, and complexity measure.

Manages Complexity

Conjunction appears harmless at the language level while multiplying state dimensions. On-demand reachability preserves polynomial memory but cannot erase the combinatorial search implied by the compact input.

Abstract Reasoning

  1. Normalize alphabets and DFA transition conventions.
  2. Form the conceptual product start tuple and joint acceptance rule.
  3. Search synchronized reachable tuples without necessarily storing the full product.
  4. If successful, recover a common word from predecessor information or a second pass.
  5. State complexity under the exact automaton and input-parameter assumptions.

Knowledge Transfer

Synchronized-product reasoning transfers to concurrent verification and constraint conjunction, but PSPACE classification depends on representation and variable family size. Other automata may change decidability or complexity.

Examples

Canonical

Three DFAs encode independent formatting constraints; a product search finds a reachable tuple where all three states accept, and the path label is one common witness string.

Mapped back: inputs → three DFAs; symbols → synchronized; state → triple; goal → all accepting; output → yes plus witness.

Applied / In Practice

Finding one word accepted by A and B and a different word accepted by B and C does not solve the three-way problem because neither word is shown to satisfy all automata.

Mapped back: pairwise witnesses → different; global witness → absent; verdict → intersection unresolved.

Structural Tensions

T1 — Explicit Product versus Space-Efficient Search. The product provides a clear correctness proof while its state count multiplies exponentially.

Diagnostic: Can reachability be explored on demand without materializing the graph?

T2 — Witness Existence versus Witness Length. A yes instance has a finite common word, but the shortest witness can be very long relative to compact inputs.

Diagnostic: Is decision alone sufficient, or must a witness be generated?

Structural–Framed Character

Intersection Non-Emptiness is structural as joint-acceptance reachability in a synchronized product and framed by automata encoding.

Structural Core vs. Domain Accent

The general pattern is simultaneous constraint satisfaction. Automata theory supplies words, transition systems, product tuples, accepting states, and PSPACE input scaling.

This entry is a kind of Computational problem.

  • Approved decision-problem root. The graph has no parent encoding this common-word question over a variable DFA family.

  • Related — DFA nonemptiness, product automaton, universality, equivalence, and regular-language intersection. They are the single-case, construction, and neighboring decisions.

Relationships to Other Abstractions

Local relationship map for Intersection Non-Emptiness ProblemParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.IntersectionNon-Emptiness ProblemDOMAINDomain-specific abstraction: Computational problem — is a kind ofComputationalproblemDOMAIN

Current abstraction Intersection Non-Emptiness Problem Domain-specific

Parents (1) — more general patterns this builds on

  • Intersection Non-Emptiness Problem is a kind of Computational problem Domain-specific

    Intersection Non-Emptiness Problem is a strict kind of Computational problem: it asks a finite encoded yes/no question about whether automata share an accepted string.

Hierarchy path (1) — routes to 1 parentless root

Neighborhood in Abstraction Space

Intersection Non-Emptiness Problem sits in a crowded region of the domain-specific corpus (32nd percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Formal Systems & Discrete Structures (18 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With

  • DFA nonemptiness. Tell: Asks whether one automaton accepts any word.
  • Union nonemptiness. Tell: Needs acceptance by at least one language.
  • Language equivalence. Tell: Asks whether two languages contain the same words.
  • Pairwise intersection. Tell: Does not establish a witness shared by the whole list.

References

  • Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Intersection_non-emptiness_problem (revision 1357297481).
  • Preserved source candidate: https://doi.org/10.1109/SFCS.1977.16
  • Preserved source candidate: https://doi.org/10.1007/BF00263744
  • Preserved source candidate: https://doi.org/10.1147/rd.32.0114
  • Preserved source candidate: https://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.