scientific article; zbMATH DE number 4049104

zbMATH Open0643.68111MaRDI QIDQ3785993FDOQ3785993

Authors: Ijsbrand Jan Aalbersberg, Joost Engelfriet, Grzegorz Rozenberg 

Publication date: 1987

Title of this publication is not available (Why is that?)

Recommendations

• The complexity of regular DNLC graph languages
• Towards a theory of complexity of regular languages
• Descriptional complexity of regular languages
• Descriptional complexity of bounded regular languages
• Descriptional complexity of bounded regular languages
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• scientific article; zbMATH DE number 3843141
• scientific article; zbMATH DE number 7315105
• Complexity of suffix-free regular languages
• Complexity of suffix-free regular languages

zbMATH Keywords

NP-completemembership problemlinear orderingcomponent-boundeddegree-boundedNLC graph grammarsNLOGRegular directed node-label controlled graph grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Cited In (4)

• Power properties of NLC graph grammars with a polynomial membership problem
• On limitations of structured (deterministic) DNNFs
• The complexity of regular DNLC graph languages
• On the membership problem for regular DNLC grammars

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3785993)