6 papers
Robust Algebraic Theories of Triangle Graphs
Marius Bozga, Radu Iosif, Florian Zuleger
Triangle graphs are graphs of tree-width at most three in which every edge belongs to a triangle. This class encompasses well-known graph families such as Apollonian networks. We a…
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…
Iterating Non-Aggregative Structure Compositions
Marius Bozga, Radu Iosif, Florian Zuleger
An aggregative composition is a binary operation obeying the principle that the whole is determined by the sum of its parts. The development of graph algebras, on which the theory…
Counting Abstraction for the Verification of Structured Parameterized Networks
Marius Bozga, Radu Iosif, Arnaud Sangnier +1
We consider the verification of parameterized networks of replicated processes whose architecture is described by hyperedge-replacement graph grammars. Due to the undecidability of…
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…
The Treewidth Boundedness Problem for an Inductive Separation Logic of Relations
Marius Bozga, Lucas Bueri, Radu Iosif +1
The treewidth boundedness problem for a logic asks for the existence of an upper bound on the treewidth of the models of a given formula in that logic. This problem is found to be…