{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreignrepcnem6qf7y7scor7neyvfnmfd3qzibcn4viltjxdi7e6v5ye",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mkkzplt4vnp2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.24151v1",
  "publishedAt": "2026-04-28T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Marius Bozga",
    "Radu Iosif",
    "Florian Zuleger"
  ],
  "textContent": "**Authors:** Marius Bozga, Radu Iosif, Florian Zuleger\n\nSeries-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.",
  "title": "Regular Grammars as Effective Representations of Recognizable Sets of Series-Parallel Graphs"
}