Characterization and complexity of uniformly nonprimitive labeled 2-structures

DOI10.1016/0304-3975(94)00272-XzbMath0873.68161MaRDI QIDQ672749

Grzegorz Rozenberg, Andrzej Proskurowski, Tero J.Harju, Joost Engelfriet

Publication date: 28 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

LOGCF algorithmMSO (monadic second-order) definable propertyparallel complexity of the decomposition of 2-structures

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Monadic second-order definable text languages ⋮ Complete edge-colored permutation graphs ⋮ Generalized Fitch graphs. II: Sets of binary relations that are explained by edge-labeled trees ⋮ Automata-based Representations for Infinite Graphs ⋮ Theory of 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 ⋮ Generalized Fitch graphs: edge-labeled graphs that are explained by edge-labeled trees ⋮ Permutations, parenthesis words, and Schröder numbers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Forbidden minors characterization of partial 3-trees
• Theory of 2-structures. I: Clans, basic subclasses, and morphisms
• Theory of 2-structures. II: Representation through labeled tree families
• Primitivity is hereditary for 2-structures
• The method of forced enumeration for nondeterministic automata
• Tree-size bounded alternation
• On uniform circuit complexity
• Complement reducible graphs
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• Angular 2-structures
• Either tournaments or algebras?
• Incremental construction of 2-structures
• Primitive 2-structures with the \((n-2)\)-property
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• On certain polytopes associated with graphs
• Graphs indecomposable with respect to the X-join
• The complexity of graph languages generated by hyperedge replacement
• Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
• Tree acceptors and some of their applications
• Embedding tournaments in simple tournaments
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Steiner trees, partial 2–trees, and minimum IFI networks
• Easy problems for tree-decomposable graphs
• A Fast Algorithm for the Decomposition of Graphs and Posets
• Characterization and Recognition of Partial 3-Trees
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Nondeterministic Space is Closed under Complementation
• Incremental modular decomposition
• Alternation
• The Recognition of Series Parallel Digraphs
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• On the Tape Complexity of Deterministic Context-Free Languages
• Transitiv orientierbare Graphen
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Modules of Coherent Binary Systems
• A Characterization of Comparability Graphs and of Interval Graphs

This page was built for publication: Characterization and complexity of uniformly nonprimitive labeled 2-structures