Iterating Non-Aggregative Structure Compositions
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911201070415872 |
|---|---|
| author | Bozga, Marius Iosif, Radu Zuleger, Florian |
| author_facet | Bozga, Marius Iosif, Radu Zuleger, Florian |
| contents | 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 of formal graph
languages is built, relies on aggregative compositions that behave
like disjoint union, except for a set of well-marked interface
vertices from both sides, that are joined. The same style of
composition has been considered in the context of relational
structures, that generalize graphs and use constant symbols to label
the interface.
In this paper, we study a non-aggregative composition operation,
called \emph{fusion}, that joins non-deterministically chosen
elements from disjoint structures. The sets of structures obtained
by iteratively applying fusion do not always have bounded
tree-width, even when starting from a tree-width bounded set.
First, we prove that the problem of the existence of a bound on the
tree-width of the closure of a given set under fusion is decidable,
when the input set is described inductively by a finite
\emph{hyperedge-replacement} (HR) grammar, written using the
operations of aggregative composition, forgetting and renaming of
constants. Such sets are usually called \emph{context-free}.
Second, assuming that the closure under fusion of a context-free set
has bounded tree-width, we show that it is the language of an
effectively constructible HR grammar. A possible application of the
latter result is the possiblity of checking whether all structures
from a non-aggregatively closed set having bounded tree-width
satisfy a given monadic second order logic formula. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_06019 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Iterating Non-Aggregative Structure Compositions Bozga, Marius Iosif, Radu Zuleger, Florian Formal Languages and Automata Theory 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 of formal graph languages is built, relies on aggregative compositions that behave like disjoint union, except for a set of well-marked interface vertices from both sides, that are joined. The same style of composition has been considered in the context of relational structures, that generalize graphs and use constant symbols to label the interface. In this paper, we study a non-aggregative composition operation, called \emph{fusion}, that joins non-deterministically chosen elements from disjoint structures. The sets of structures obtained by iteratively applying fusion do not always have bounded tree-width, even when starting from a tree-width bounded set. First, we prove that the problem of the existence of a bound on the tree-width of the closure of a given set under fusion is decidable, when the input set is described inductively by a finite \emph{hyperedge-replacement} (HR) grammar, written using the operations of aggregative composition, forgetting and renaming of constants. Such sets are usually called \emph{context-free}. Second, assuming that the closure under fusion of a context-free set has bounded tree-width, we show that it is the language of an effectively constructible HR grammar. A possible application of the latter result is the possiblity of checking whether all structures from a non-aggregatively closed set having bounded tree-width satisfy a given monadic second order logic formula. |
| title | Iterating Non-Aggregative Structure Compositions |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2510.06019 |