⚡ electrical engineering

Decentralized Decision-Making for Finite-State Systems over Finite Alphabets is Undecidable

This paper demonstrates that decentralized decision-making for finite-state systems becomes undecidable under finite communication alphabets when using non-monotone fusion rules like XOR, contrasting with classical results that rely on monotone rules.

Original authors: Xiang Yin

Published 2026-06-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Xiang Yin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: A Game of "Yes or No" with a Twist

Imagine a large, complex machine (like a factory robot or a traffic system) that is being watched by two separate security guards. These guards cannot talk to each other; they can only see parts of the machine.

Guard 1 sees a specific set of lights.
Guard 2 sees a different set of lights.
The Boss sits in a control room. He cannot see the machine directly. He only receives a single "Yes" or "No" signal from each guard.
The Goal: The Boss needs to know if the machine is currently doing something "Good" (following the rules) or "Bad" (breaking the rules).

The Boss has a special rule for combining the guards' answers. He uses a logic gate called XOR (Exclusive OR).

If Guard 1 says "Yes" and Guard 2 says "No," the Boss says "Good."
If Guard 1 says "No" and Guard 2 says "Yes," the Boss says "Good."
If they both say "Yes" OR they both say "No," the Boss says "Bad."

The Question: Can we program the guards to look at their lights and send the right "Yes/No" signals so that the Boss always knows exactly when the machine is doing the "Good" thing?

The Paper's Main Discovery: The "Impossible Puzzle"

For decades, researchers thought that if you gave the guards simple rules (like "If either of you sees a red light, say 'Stop'"), they could always figure out how to program the guards to solve the problem.

This paper proves that is not true.

The author, Xiang Yin, shows that if you use the XOR rule (where the Boss needs the guards to disagree to say "Good"), it becomes mathematically impossible to know if a solution exists. No computer, no matter how powerful, can ever solve this puzzle for every possible machine.

The Analogy: The "Word Swap" Game

How did the author prove this? He turned the machine problem into a famous, unsolvable word game called the Thue Word Problem.

Imagine you have a set of magical rules for swapping letters in a word:

Rule 1: You can swap "AB" with "BA".
Rule 2: You can swap "C" with "BB".

You start with the word "ABC".

You can turn it into "BAC" (swapping AB).
You can turn that into "BABB" (swapping C).

The Question: Can you turn the word "ABC" into the word "BABB" using these rules?

In the world of math, this is a known impossible problem. There is no general method to answer "Yes" or "No" for every possible word and every possible set of rules.

The Connection:
The author built a "machine" (the finite-state system) that acts exactly like this word game.

The Identity Branch: The machine generates words that look the same to both guards. This forces the guards to agree (send the same signal) so the Boss says "Bad" (because XOR needs them to disagree). This establishes a baseline "truth."
The Rewrite Branch: The machine generates words where the guards see different versions of the same word (like "ABC" vs. "BABB"). The rules of the machine force the guards to agree again. This means the "truth" of the word must stay the same even after the swap.
The Marked Branch: The machine generates a specific "Good" scenario (the target word). Here, the Boss needs the guards to disagree.

The Trap:
If the two words in the word game are actually equivalent (you can turn one into the other), the rules of the machine force the guards to agree. But the "Good" scenario requires them to disagree. This creates a contradiction.
If they are not equivalent, the guards can be programmed to disagree.

Because the "Word Swap" game is unsolvable, the "Machine Guard" game is also unsolvable.

Why Does This Happen? (The "Monotone" vs. "Chaotic" Rule)

The paper explains that previous successful methods relied on rules that are Monotone (order-preserving).

AND/OR Rules: If you add more information, the answer doesn't flip-flop wildly. It's like a committee vote: if more people vote "Yes," the result is more likely to be "Yes." This structure allows computers to find a solution.
XOR Rule: This is Non-Monotone. It's like a game of "Rock, Paper, Scissors" logic. If both guards change their minds, the result flips completely. This lack of a stable "order" breaks the mathematical tools we usually use to solve these problems.

What About Other Problems?

The paper shows that this "impossibility" isn't just about the Boss guessing if the machine is working. It spreads to other real-world control problems:

Decentralized Control: Can we program the guards to stop the machine from breaking? (No, not if we use XOR).
Fault Diagnosis: Can the guards tell us if a part has broken? (No).
Fault Prognosis: Can the guards predict a break before it happens? (No).

Summary

The Setup: Two guards watch a machine and send binary (Yes/No) signals to a Boss who uses an XOR rule (needs disagreement to say "Good").
The Result: It is undecidable. There is no algorithm that can tell you if a set of instructions for the guards exists to solve the problem.
The Reason: The XOR rule destroys the mathematical "structure" (monotonicity) that usually allows computers to solve these puzzles. The problem is mathematically equivalent to the unsolvable "Thue Word Problem."
The Takeaway: Even with very simple, restricted communication (just one bit from two people), the choice of how to combine their answers (XOR) can make the entire system impossible to program or analyze.

Technical Summary: Decentralized Decision-Making for Finite-State Systems over Finite Alphabets is Undecidable

1. Problem Formulation

This paper investigates the fundamental decidability of decentralized decision-making for finite-state transition systems (Discrete-Event Systems or DES) under strict communication constraints. The problem is framed within a general decentralized observation architecture involving:

A Plant: A deterministic finite-state automaton $G = (Q, \Sigma, f, q_0)$ .
Local Agents: Two agents observe the plant through disjoint event sets $\Sigma_{o,1}$ and $\Sigma_{o,2}$ via natural projections $P_1$ and $P_2$ .
Communication: Each agent generates a local decision symbol from a finite alphabet $\Delta$ based solely on its observation history.
Fusion Center: A memoryless fusion center applies a fixed rule $F: \Delta \times \Delta \to \{0, 1\}$ to the pair of local decisions to produce a global binary decision.

The core question, termed the Decentralized Observation Problem with Finite Alphabet, is to determine whether there exist local decision maps $S_i: P_i(L(G)) \to \Delta$ such that the fusion center can exactly reconstruct a given regular specification language $K \subseteq L(G)$ . Specifically, for all $s \in L(G)$ , the condition $s \in K \iff F(S_1(P_1(s)), S_2(P_2(s))) = 1$ must hold.

2. Methodology

The authors establish the undecidability of this problem through a reduction from the Thue word problem, a classical undecidable problem in formal language theory concerning the equivalence of two words under a finite set of bidirectional rewriting rules.

Construction Strategy:
Given an instance of the Thue word problem $(\Gamma, R, \alpha, \beta)$ , the authors construct a specific decentralized observation instance $(G, \Sigma_{o,1}, \Sigma_{o,2}, K, \Delta, F)$ with the following properties:

Restricted Architecture: The communication alphabet is binary ( $\Delta = \{0, 1\}$ ), and the fusion rule is fixed to the exclusive-or (XOR) operator ( $a \oplus b = 1 \iff a \neq b$ ).
Plant Structure: The automaton $G$ $G$ is constructed with three distinct branches:
1. Identity Branch: Generates strings encoding arbitrary words $w \in \Gamma^*$ as paired sequences. This branch forces the two agents to assign identical decision values to the same underlying word $w$ (since the output must be 0 for unmarked strings, and $x \oplus y = 0 \implies x=y$ ). This allows the definition of a global valuation function $C(w)$ .
2. Rewrite Branches: For each rewriting rule $(\ell_j, r_j) \in R$ , the plant generates strings where Agent 1 observes a context containing $\ell_j$ and Agent 2 observes the same context containing $r_j$ . Since these strings are unmarked, the XOR fusion rule forces $C(\dots \ell_j \dots) = C(\dots r_j \dots)$ . This enforces that the valuation $C$ is invariant under Thue rewriting steps.
3. Marked Branch: Generates a unique marked string encoding the specific words $\alpha$ and $\beta$ observed by Agents 1 and 2, respectively. For the fusion output to be 1 (indicating membership in $K$ ), the agents must assign different values: $C(\alpha) \neq C(\beta)$ .

Logical Reduction:
The existence of valid local decision maps implies the existence of a valuation $C$ that is constant on Thue equivalence classes (due to rewrite branches) but distinguishes $\alpha$ and $\beta$ (due to the marked branch). Such a valuation exists if and only if $\alpha \not\equiv_R \beta$ . Since the Thue word problem is undecidable, determining the existence of such maps is also undecidable.

3. Key Contributions and Results

Undecidability under XOR: The paper proves that the decentralized observation problem is undecidable even when the decision alphabet is binary and the fusion rule is fixed to XOR. This holds for a highly restricted information architecture (two agents, finite alphabet, memoryless fusion).
Role of Monotonicity: The results highlight that the decidability of existing architectures (e.g., conjunctive AND or disjunctive OR rules) relies fundamentally on the monotone, order-preserving nature of those fusion rules. The XOR rule is inherently non-monotone, breaking the structural properties that allow for constructive synthesis and decidability in classical settings.
Extension to Control and Diagnosis: The authors demonstrate that the decentralized observation problem can be reduced to:
- Decentralized Supervisory Control: Determining the existence of local supervisors to enforce a specification.
- Decentralized Fault Diagnosis: Determining the existence of local diagnosers to detect faults with bounded delay and no false alarms.
- Decentralized Fault Prognosis: Determining the existence of local prognosticators to predict faults before occurrence.
  Consequently, all these problems are shown to be undecidable under binary decision alphabets and the XOR fusion rule.

4. Significance and Claims

The paper claims to reveal a fundamental limitation in decentralized decision-making architectures. While previous literature has focused on enriching decision alphabets or designing sophisticated fusion rules to enhance expressive power, this work shows that the choice of fusion rule can fundamentally alter the decidability of the synthesis problem itself.

The authors emphasize that their result is strictly stronger than previous undecidability results (e.g., those involving infinite communication alphabets) because undecidability persists even when the communication alphabet is finite (binary) and the fusion rule is fixed. The intrinsic source of undecidability is identified as the decentralized information structure induced by independent observations interacting with non-monotone fusion rules, rather than the size of the communication alphabet.

The paper concludes modestly, noting that while the general problem is undecidable, practical applications with bounded memory at local agents might render the synthesis problem decidable via exhaustive enumeration, suggesting a direction for future research into bounded-synthesis techniques.