1 citations · 1 across the 12 of their papers we have counts for
5 papers · 1 filter
Regular Grammars as Effective Representations of Recognizable Sets of Series-Parallel Graphs
Marius Bozga, Radu Iosif, Florian Zuleger
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…
Regular Grammars for Sets of Graphs of Tree-Width 2
Marius Bozga, Radu Iosif, Florian Zuleger
Regular word grammars are restricted context-free grammars that define all the recognizable languages of words. This paper generalizes regular grammars from words to certain classe…
Tree-Verifiable Graph Grammars
Mark Chimes, Radu Iosif, Florian Zuleger
Hyperedge-Replacement grammars (HR) have been introduced by Courcelle in order to extend the notion of context-free sets from words and trees to graphs of bounded tree-width. While…
Characterizations of Monadic Second Order Definable Context-Free Sets of Graphs
Radu Iosif, Florian Zuleger
We give a characterization of the sets of graphs that are both definable in Counting Monadic Second Order Logic (CMSO) and context-free, i.e., least solutions of Hyperedge-Replacem…
The Polynomial Complexity of Vector Addition Systems with States
Florian Zuleger
Vector addition systems are an important model in theoretical computer science and have been used in a variety of areas. In this paper, we consider vector addition systems with sta…