Revisiting Membership Problems in Subclasses of Rational Relations

Pascal Bergsträßer, Moses Ganardi

Abstract

This paper addresses long-standing open questions in automata theory concerning the membership problem for word relations. The authors provide new algorithms and complexity bounds for determining if a relation from a complex class, such as deterministic rational relations, can be simplified into synchronous or recognizable classes. Key contributions include settling the complexity of testing recognizability for infinite word relations and significantly reducing the complexity for binary deterministic relations from double-exponential to polynomial time.

Introduction

In formal language theory, relations—sets of tuples of words—are categorized into a hierarchy based on the automata that recognize them. While regular languages are well-understood, relations are significantly more complex. The hierarchy typically includes:

  1. Rational (Rat): Recognized by nondeterministic asynchronous multitape automata.
  2. Deterministic Rational (DRat): The deterministic counterpart of Rat.
  3. Synchronous (Sync): Recognized by automata where all heads move at the same speed (also called "automatic relations").
  4. Recognizable (Rec): The simplest class, consisting of finite unions of Cartesian products of regular languages.

The membership problem asks whether a relation $R$ belonging to a class $C_2$ also belongs to a more restricted class $C_1$. Solving this is vital because simpler classes offer superior algorithmic properties, such as decidable equivalence. For nearly two decades, the precise complexity of these tests remained a mystery.

Methodology

The authors depart from traditional "brute force" methods that involve constructing massive representative automata, which often lead to high exponential time complexities. Instead, they utilize three primary strategies:

Pattern Identification

For infinite words ($ω$-words), the problem is reduced to finding an "infinite clique" in a co-equivalence relation. The authors identify a structural witness called a 3-cycles pattern directly within the automaton. The presence of this pattern indicates that the relation cannot be recognizable.

Reduction to Equivalence

For deterministic rational relations (DRat), the authors demonstrate that testing for recognizability is logspace-reducible to the equivalence problem for multitape automata. By leveraging efficient existing algorithms for testing the equivalence of deterministic transducers, they derive significantly faster membership tests.

Bounded Delay Analysis

To decide if a relation is synchronous, the authors analyze the "delay" between the reading heads of the transducer. They prove that a relation is synchronous if and only if it has bounded delay or its components eventually become independent (recognizable).

Key Results

The paper provides a comprehensive landscape of complexity results for both finite and infinite word relations, filling significant gaps in the literature.

Complexity landscape for membership problems in finite and infinite word relations.

Major findings include:

  • $ω$-Recognizability: Testing if an $ω$-synchronous relation is recognizable is NL-complete for deterministic automata (DPAs) and PSPACE-complete for nondeterministic ones (NBAs).
  • Binary DRat Recognizability: The complexity for binary relations ($k=2$) was improved from a double-exponential bound to Polynomial Time (P).
  • $k$-ary DRat Recognizability: For relations with arity $k > 2$, a randomized exponential-time algorithm (coREXP) is provided.
  • Synchronicity Test: The authors present the first algorithm to decide if a DRat is synchronous, running in P for binary relations and $(2k-4)$-exponential time for $k$-ary relations.

Discussion and Future Work

While this work settles several major questions, limitations remain. Membership problems for the broadest class, Rational Relations (Rat), are undecidable. Furthermore, while binary relations saw a massive speedup, the complexity for $k$-ary relations ($k > 2$) remains high, suggesting an inherent exponential gap for higher arities. Finally, several membership questions for deterministic rational relations over infinite words ($ω$-DRat) remain open, providing a clear roadmap for future research in automata theory.

Summary updated

BibTeX
@inproceedings{bergstraer2023revisiting,
  author = {Pascal Bergsträßer and Moses Ganardi},
  title = {{Revisiting Membership Problems in Subclasses of Rational Relations}},
  booktitle = {LICS},
  year = {2023},
  doi = {10.1109/lics56636.2023.10175722},
}
Figure