Basic notions of universal algebra for language theory and graph grammars

DOI10.1016/0304-3975(95)00145-XMaRDI QIDQ671349zbMATH OpenFDO

Authors Bruno Courcelle

Publication date 27 February 1997

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

Full work available at URL https://doi.org/10.1016/0304-3975(95)00145-X

zbMATH Keywords

context-free languagesequational subsetsgraph grammarsrecognizable subsets of general algebrasregular languages

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On algebra of languages representable by vertex-labeled graphs
• scientific article; zbMATH DE number 3854429
• scientific article; zbMATH DE number 871246
• scientific article; zbMATH DE number 5005936

Cites work

• Algebraic automata and context-free sets
• An algebraic theory of graph reduction
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• Asynchronous mappings and asynchronous cellular automata
• Commutative Regular Equations and Parikh's Theorem
• Easy multiplications. I: The realm of Kleene's theorem
• Easy problems for tree-decomposable graphs
• Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
• Fixed point theorems and semantics: A folk tale
• Graph expressions and graph rewritings
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 3888893 (Why is no real title available?)
• scientific article; zbMATH DE number 3972168 (Why is no real title available?)
• scientific article; zbMATH DE number 3738924 (Why is no real title available?)
• scientific article; zbMATH DE number 44213 (Why is no real title available?)
• scientific article; zbMATH DE number 51770 (Why is no real title available?)
• scientific article; zbMATH DE number 108365 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3615891 (Why is no real title available?)
• scientific article; zbMATH DE number 475416 (Why is no real title available?)
• scientific article; zbMATH DE number 475417 (Why is no real title available?)
• scientific article; zbMATH DE number 475615 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• scientific article; zbMATH DE number 1142316 (Why is no real title available?)
• scientific article; zbMATH DE number 1142319 (Why is no real title available?)
• scientific article; zbMATH DE number 1142323 (Why is no real title available?)
• scientific article; zbMATH DE number 3334182 (Why is no real title available?)
• scientific article; zbMATH DE number 3019695 (Why is no real title available?)
• Hyperedge replacement: grammars and languages
• Initial Algebra Semantics and Continuous Algebras
• IO and OI. II
• Monadic second-order evaluations on tree-decomposable graphs
• Notes on finite asynchronous automata
• On generalized language equations
• On the existence of minimum asynchronous automata and on the equivalence problem for unambiguous regular trace languages
• Recognizable sets of graphs: equivalent definitions and closure properties
• Structural properties of context-free sets of graphs generated by vertex replacement
• The IO- and OI-hierarchies
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• Tools for proving inductive equalities, relative completeness, and \(\omega\)-completeness
• Two Families of Languages Related to ALGOL
• Un théorème de duplication pour les forets algébriques

Cited in

(17)

• Treewidth and logical definability of graph products
• Nondeterministic operations on finite relational structures
• Rationality in algebras with a series operation
• The rank-width of edge-coloured graphs
• Algebraic recognizability of regular tree languages
• Recognizability, hypergraph operations, and logical types
• The recognizability of sets of graphs is a robust property
• Equational weighted tree transformations with discounting
• A Term-Graph Syntax for Algebras over Multisets
• Generalized Disjunctive Languages and Universal Algebra
• Graph decompositions for cartesian products
• scientific article; zbMATH DE number 4087643 (Why is no real title available?)
• scientific article; zbMATH DE number 1062291 (Why is no real title available?)
• GETGRATS: a summary of scientific results (with annotated bibliography)
• Equational tree transformations
• Equational weighted tree transformations
• Definable transductions and weighted logics for texts

Describes a project that uses

Uses Software

• ALGOL 60

This page was built for publication: Basic notions of universal algebra for language theory and graph grammars

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