Recognising \(k\)-connected hypergraphs in cubic time
type: Item
instance of: scholarly article
title: Recognising \(k\)-connected hypergraphs in cubic time
zbMATH Open document ID: 0779.68052
DOI: 10.1016/0304-3975(93)90065-2
published in: Theoretical Computer Science
publication date: 1994-01-19T00:00:00Z
review text: It is known that, in general, the recognition of (hyper)graph languages generated by hyperedge-replacement grammars is an NP-complete problem. A special case is considered that leads to an algorithm running in cubic time. We study hypergraph languages generated by hyperedge-replacement grammars or order \(k\), where order \(k\) means that hyperedges with at most \(k\) incident nodes are used. It is shown that for \(k\)-connected hypergraphs having hyperedges of rank \(k\) only (so-called \(k\)-hypergraphs) the membership problem is devidable in cubic time. This extends the corresponding result for the graph case (that is, for \(k=2\)) given by \textit{W. Vogler} [Lect. Notes Comput. Sci. 532, 676-687 (1991; Zbl 0769.68078)]. The result is based a theorem providing a unique decomposition of \(k\)-connected \(k\)-hypergraphs into components of two different kinds, which is a generalization of a 1937 result by \textit{S. MacLane} [A structural characterization of planar combinatorial graphs, Duke Math. J. 3, 460-472 (1937; Zbl 0017.42702)], who treated the case of biconnected graphs. The decomposition result allows to adapt the well-known algorithm by \textit{Coke}, \textit{Kasami}, and \textit{Younger} for context free string languages recognition to the case of hyperedge-replacement languages. It can be shown [Inf. Proc. Letters 45, 89-94 (1993)] that the restriction to \(k\)-hypergraphs is really necessary (assuming \(P\neq NP\)): There are \(NP\)-complete \(3\)-connected graph languages generated by hyperedge-replacement grammars of order 3.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68N20
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 417384
zbMATH Keywords: graph parsing
zbMATH Keywords: hyperedge-replacement
zbMATH Keywords: hypergraph
zbMATH Keywords: decomposition
author: Frank Drewes
reviewed by: Frank Drewes
MaRDI profile type: Publication
full work available at URL: 0304-3975(93)90065-2
OpenAlex ID: W2040035445
cites work: Q4385531
cites work: The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
cites work: Q3999150
cites work: Counter machines and counter languages
cites work: Q5576254
cites work: Hyperedge replacement: grammars and languages
cites work: Q3774975
cites work: Dividing a Graph into Triconnected Components
cites work: Q5592246
cites work: String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing
cites work: Q3789084
cites work: The complexity of graph languages generated by hyperedge replacement
cites work: Q3795251
cites work: A structural characterization of planar combinatorial graphs
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: Q4037335
cites work: Recognition and parsing of context-free languages in time n3
Recommended article: NP-completeness of \(k\)-connected hyperedge-replacement languages of order \(k\)
Recommended article: Q4037335
Recommended article: Q3795250
Recommended article: Powerful and NP-complete: hypergraph Lambek grammars
Recommended article: Structural properties of context-free sets of graphs generated by vertex replacement
Recommended article: A characterization of the sets of hypertrees generated by hyperedge-replacement graph grammars
Recommended article: Q4694744
Recommended article: Q4852905
Recommended article: Uniform parsing for hyperedge replacement grammars
Recommended article: Q3070891
description: scientific article; zbMATH DE number 417384