scientific article; zbMATH DE number 177441

MaRDI QIDQ4037316zbMATH OpenFDO

Authors Joost Engelfriet

Publication date 18 May 1993

zbMATH Keywords

context-free NCE graph languagesmonadic second-order logictrees

Mathematics Subject Classification ID

Trees (05C05) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Logical description of context-free graph languages
• Regular description of context-free graph languages
• A regular characterization of graph languages definable in monadic second-order logic
• scientific article; zbMATH DE number 17539
• The monadic second-order logic of graphs. VII: Graphs as relational structures

Cited in

(22)

• The monadic second-order logic of graphs. VII: Graphs as relational structures
• Monadic second-order definable graph transductions: a survey
• The monadic second order logic of graphs. VI: On several representations of graphs by relational structures
• Context-free graph languages of bounded degree are generated by apex graph grammars
• Monadic second-order definable text languages
• Logical description of context-free graph languages
• Generating irregular partitionable data structures
• A comparison of tree transductions defined by monadic second order logic and by attribute grammars
• The monadic second-order logic of graphs. VIII: Orientations
• Upper bounds to the clique width of graphs
• Shelah-Stupp's and Muchnik's iterations revisited
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 809155 (Why is no real title available?)
• scientific article; zbMATH DE number 1456961 (Why is no real title available?)
• scientific article; zbMATH DE number 7559390 (Why is no real title available?)
• MSO definable text languages
• Characterization and complexity of uniformly nonprimitive labeled 2-structures
• Regular description of context-free graph languages
• Decidable (ac)counting with Parikh and Muller: adding Presburger arithmetic to monadic second-order logic over tree-interpretable structures
• Rank-decreasing transductions
• Decidability of querying first-order theories via countermodels of finite width
• Weighted tree automata and weighted logics

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 Q4037316)