formal-buchi-emptiness-scc

Answer

Approach. By the standard Büchi emptiness theorem: the automaton's language is nonempty ⟺ some reachable accepting SCC is cyclic (size > 1, or a size-1 SCC whose single state has a self-loop). The algorithm is:

1. Reachability (iterative DFS) from the initial states, so unreachable accepting SCCs are ignored.
2. Tarjan SCC decomposition — implemented iteratively with an explicit DFS frame stack ([vertex, next-neighbor-position]), so no recursion-depth blowup on 10⁵ states/10⁶ edges.
3. For each SCC that is reachable and contains an accepting state:
4. size 1 + self-loop ⟹ witness [v, v] (loop forever);
5. size > 1 ⟹ strong connectivity guarantees a cycle through an accepting state; a BFS inside the SCC from the accepting state a finds the shortest path back to a and reconstructs the witness cycle [a, x₁, …, xₖ, a].

from collections import deque

def tarjan_scc(n, adj):
    """Iterative Tarjan SCC decomposition. Returns list of SCCs."""
    idx = [-1] * n; low = [0] * n; on_stack = [False] * n
    stack = []; sccs = []; counter = 0
    for root in range(n):
        if idx[root] != -1:
            continue
        frames = [[root, 0]]                      # [vertex, next neighbour pos]
        idx[root] = low[root] = counter; counter += 1
        stack.append(root); on_stack[root] = True
        while frames:
            node, pos = frames[-1]
            if pos < len(adj[node]):
                w = adj[node][pos]; frames[-1][1] = pos + 1
                if idx[w] == -1:                  # tree edge
                    idx[w] = low[w] = counter; counter += 1
                    stack.append(w); on_stack[w] = True
                    frames.append([w, 0])
                elif on_stack[w]:                 # edge to an ancestor
                    if idx[w] < low[node]: low[node] = idx[w]
            else:
                frames.pop()
                if frames:                        # propagate low-link to parent
                    p = frames[-1][0]
                    if low[node] < low[p]: low[p] = low[node]
                if low[node] == idx[node]:        # SCC root
                    comp = []
                    while True:
                        w = stack.pop(); on_stack[w] = False; comp.append(w)
                        if w == node: break
                    sccs.append(comp)
    return sccs

def find_witness_cycle(scc, adj, a):
    """Shortest cycle a -> ... -> a lying inside `scc` (BFS + parent chain)."""
    scc_set = set(scc); parent = {a: -1}; q = deque([a])
    while q:
        u = q.popleft()
        for w in adj[u]:
            if w not in scc_set: continue
            if w == a:                            # edge u -> a closes the cycle
                path = []
                x = u
                while x != -1:
                    path.append(x); x = parent[x]
                path.reverse()
                return path + [a]
            if w not in parent:
                parent[w] = u; q.append(w)
    return None   # unreachable: strong connectivity guarantees a cycle

def buchi_emptiness(n, adj, accepting, initial):
    """Returns (nonempty, witness). witness is a cycle list (first == last)
    containing an accepting state, or [] if the language is empty."""
    acc = set(accepting); init = set(initial)
    if not init:
        return False, []

    # 1) reachable states (iterative DFS)
    reachable = set(init); dfs = list(init)
    while dfs:
        u = dfs.pop()
        for w in adj[u]:
            if w not in reachable:
                reachable.add(w); dfs.append(w)

    # 2) reachable accepting SCCs
    for scc in tarjan_scc(n, adj):
        acc_node = next((v for v in scc if v in reachable and v in acc), None)
        if acc_node is None:
            continue
        if len(scc) == 1:                        # self-loop on accepting state
            v = scc[0]
            if v in adj[v]:
                return True, [v, v]
            continue
        cycle = find_witness_cycle(scc, adj, acc_node)
        if cycle is not None:
            return True, cycle
    return False, []

Complexity: O(n + m) time (Tarjan + reachability + BFS witness), O(n + m) memory — handles 10⁵ states / 10⁶ edges comfortably with zero recursion.