The complexity of regular DNLC graph languages

DOI10.1016/0022-0000(90)90004-5zbMath0694.68045OpenAlexW2030288301WikidataQ57402283 ScholiaQ57402283MaRDI QIDQ909473

Joost Engelfriet, Ijsbrand Jan Aalbersberg, Grzegorz Rozenberg

Publication date: 1990

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(90)90004-5

zbMATH Keywords

graph grammarscomplexity of the membership problemdependence graph languagesevent structure languages

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (6)

Complexity of boundary graph languages ⋮ A hierarchy of eNCE families of graph languages ⋮ The complexity of regular DNLC graph languages ⋮ HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting ⋮ HRNCE grammars — A hypergraph generating system with an eNCE way of rewriting ⋮ Separation results for separated apex NLC and NCE graph languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of regular DNLC graph languages
• Traces, dependency graphs and DNLC grammars
• On the membership problem for regular DNLC grammars
• String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing
• The method of forced enumeration for nondeterministic automata
• Theory of traces
• A characterization of context-free string languages by directed node- label controlled graph grammars
• On tape-bounded complexity classes and multihead finite automata
• Parallel concepts in graph theory
• Linear graph grammars: Power and complexity
• Complexity of boundary graph languages
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Nondeterministic Space is Closed under Complementation
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers

This page was built for publication: The complexity of regular DNLC graph languages