Theory of 2-structures. I: Clans, basic subclasses, and morphisms
A 2-structure is a pair (D,R), where D is a nonempty finite set and R is an equivalence relation on \(E_ 2(D)=\{(x,y)\); \(x\neq y\), x,y\(\in D\}\). (The notion is a generalization of a graph as well as a restriction of a relational structure.) This is the first part of the paper that develops the theory of 2- structures. Here the notion of a clan is introduced and studied: A subset \(X\subseteq D\) is a clan of a 2-structure (D,R) if for all x,y\(\in X\) and \(z\in D\setminus X\), (z,x)R(z,y) and (x,z)R(y,z). (The notion of a clan corresponds to the notion of a factor in an algebra.) Further, special 2- structures are defined and treated; these are primitive, complete and linear 2-structures. Finally, the notion of a morphism between two 2-structures is introduced and studied. This study leads in Part II to the decomposition theory of 2-structures (cf. the review below).
- Critically indecomposable graphs
- A characterization of set representable labeled partial 2-structures through decompositions
- Angular 2-structures
- Modular decomposition and transitive orientation
- Incremental construction of 2-structures
- Context-free text grammars
- Clans and regions in 2-structures
- Primitive 2-structures with the (n-2)-property
- A k-structure generalization of the theory of 2-structures
- Monadic second-order definable text languages
- PC trees and circular-ones arrangements.
- Linear-time modular decomposition of directed graphs
- An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures
- The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations
- From modular decomposition trees to rooted median graphs
- From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats
- Generalized Fitch graphs. II: Sets of binary relations that are explained by edge-labeled trees
- Explicating logical independence
- Best match graphs and reconciliation of gene trees with species trees
- Generalized Fitch graphs: edge-labeled graphs that are explained by edge-labeled trees
- Complete edge-colored permutation graphs
- Description of the tournaments which are reconstructible from their \(k\)-cycle partial digraphs for \(k\in \{3, 4\}\)
- Primitive bound of a 2-structure
- Decomposition tree of a lexicographic product of binary structures
- scientific article; zbMATH DE number 1300416 (Why is no real title available?)
- scientific article; zbMATH DE number 591000 (Why is no real title available?)
- Dynamic labeled 2-structures
- scientific article; zbMATH DE number 1478125 (Why is no real title available?)
- A tight lower bound for primitivity in k-structures
- Theory of 2-structures
- Drawing graphs with attribute graph grammars
- Group based graph transformations and hierarchical representations of graphs
- Critically twin primitive 2-structures
- Criticality of switching classes of reversible 2-structures labeled by an abelian group
- MSO definable text languages
- NLC\(_{2}\)-decomposition in polynomial time
- Generalized tournament matrices with the same principal minors
- Dynamic labeled 2-structures with variable domains
- Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
- Decomposition of infinite labeled 2-structures
- Modules in Robinson Spaces
- Prime 2-structures
- Linear time algorithms for NP-hard problems restricted to \textsc{GaTEx} graphs
- Characterization and complexity of uniformly nonprimitive labeled 2-structures
- T-structures, T-functions, and texts
- Modules and PQ-trees in Robinson spaces
- Solving NP-hard problems on \textsc{GaTEx} graphs: linear-time algorithms for perfect orderings, cliques, colorings, and independent sets
- Existential MSO over two successors is strictly weaker than over linear orders
- Definable transductions and weighted logics for texts
- Finite metrics in switching classes
- Algorithmic aspects of switch cographs
- Partial (set) 2-structures. I: Basic notions and the representation problems
- Partial (set) 2-structures. II: State spaces of concurrent systems
- Theory of 2-structures. II: Representation through labeled tree families
- Primitivity is hereditary for 2-structures
This page was built for publication: Theory of 2-structures. I: Clans, basic subclasses, and morphisms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q913822)
