Regular Grammars as Effective Representations of Recognizable Sets of Series-Parallel Graphs
For researchers in graph theory and automata, this work provides more efficient syntactic representations and algorithms for recognizable sets of bounded-tree-width graphs.
The authors improve the construction of finite recognizer algebras for recognizable sets of series-parallel graphs, reducing the size bound from double-exponential to singly-exponential in the size of a regular grammar. This yields ExpTime-completeness for intersection and language inclusion problems, improving a previous 2ExpTime upper bound.
Series-parallel (SP) graphs are binary edge-labeled graphs with a designated source and target vertex, built using serial and parallel composition. A set of graphs is recognizable if membership depends only on its image under a homomorphism into a finite algebra. For SP-graphs, and more generally, for graphs of bounded tree-width, recognizability coincides with definability in Counting Monadic Second-Order (CMSO) logic. Despite this strong logical characterization, the conciseness and algorithmic effectiveness of syntactic representations of recognizable sets of SP (and bounded-tree-width) graphs remain poorly understood. Building on previously introduced regular grammars for SP-graphs, we show that recognizable sets admit concise and effective syntactic representations. The main contribution is an improved construction of finite recognizer algebras whose size is singly-exponential in the size of a regular grammar, improving upon the previously known double-exponential bound. As a consequence, the problems of intersection and language inclusion for sets represented by regular grammars are shown to be ExpTime-complete, thus improving on a previously known 2ExpTime upper bound.