Revisiting Membership Problems in Subclasses of Rational Relations
Lists
Only you see this
Abstract
We revisit the membership problem for subclasses of rational relations over finite and infinite words: Given a relation R in a class C 2 , does R belong to a smaller class C 1 ? The subclasses of rational relations that we consider are formed by the deterministic rational relations, synchronous (also called automatic or regular) relations, and recognizable relations. For almost all versions of the membership problem, determining the precise complexity or even decidability has remained an open problem for almost two decades. In this paper, we provide improved complexity and new decidability results. (i) Testing whether a synchronous relation over infinite words is recognizable is NL-complete (PSPACE-complete) if the relation is given by a deterministic (nondeterministic) ω-automaton. This fully settles the complexity of this recognizability problem, matching the complexity of the same problem over finite words. (ii) Testing whether a deterministic rational binary relation is recognizable is decidable in polynomial time, which improves a previously known double exponential time upper bound. For relations of higher arity, we present a randomized exponential time algorithm. (iii) We provide the first algorithm to decide whether a deterministic rational relation is synchronous. For binary relations the algorithm even runs in polynomial time.
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},
}| Separating Automatic Relations | arXiv · 2023 |
| Monadic Decomposability of Regular Relations | arXiv · 2019 |
| On Relations Defined by Generalized Finite Automata | Ibm Journal of Research and Development · 1965 |
| On Repetitive Finite Automata with Translucent Words | arXiv · 2025 |
| Languages Ordered by the Subword Order | Fossacs · 2019 |
| The Complexity of Separability for Semilinear Sets and Parikh Automata | arXiv · 2024 |