2026-08-21T18:34:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27461 2026-08-21T14:42:41Z ddc:004 open_access

Regular Grammars as Effective Representations of Recognizable Sets of Series-Parallel Graphs Bozga, Marius Iosif, Radu Zuleger, Florian Series-parallel graphs Regular grammars Recognizability Decision problems 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marius Bozga and Radu Iosif and Florian Zuleger 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.79 urn:nbn:de:0030-drops-274614 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.79 eng https://creativecommons.org/licenses/by/4.0/legalcode