Basic notions of universal algebra for language theory and graph grammars
From MaRDI portal
Publication:671349
DOI10.1016/0304-3975(95)00145-XzbMath0874.68170MaRDI QIDQ671349
Publication date: 27 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
context-free languagesregular languagesgraph grammarsequational subsetsrecognizable subsets of general algebras
Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Applications of universal algebra in computer science (08A70) Grammars and rewriting systems (68Q42)
Related Items
Definable transductions and weighted logics for texts, The rank-width of edge-coloured graphs, Algebraic recognizability of regular tree languages, GETGRATS, Equational tree transformations, Recognizability, hypergraph operations, and logical types, Treewidth and logical definability of graph products, Nondeterministic operations on finite relational structures, Equational Weighted Tree Transformations with Discounting, Equational weighted tree transformations, The recognizability of sets of graphs is a robust property, Rationality in algebras with a series operation, Graph decompositions for cartesian products
Uses Software
Cites Work
- Tools for proving inductive equalities, relative completeness, and \(\omega\)-completeness
- Hyperedge replacement: grammars and languages
- Monadic second-order evaluations on tree-decomposable graphs
- Asynchronous mappings and asynchronous cellular automata
- Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
- Easy multiplications. I: The realm of Kleene's theorem
- An axiomatic definition of context-free rewriting and its application to NLC graph grammars
- On generalized language equations
- The IO- and OI-hierarchies
- Fixed point theorems and semantics: A folk tale
- 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
- Un théorème de duplication pour les forets algébriques
- IO and OI. II
- On the existence of minimum asynchronous automata and on the equivalence problem for unambiguous regular trace languages
- Structural properties of context-free sets of graphs generated by vertex replacement
- Handle-rewriting hypergraph grammars
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Easy problems for tree-decomposable graphs
- Notes on finite asynchronous automata
- Graph expressions and graph rewritings
- Initial Algebra Semantics and Continuous Algebras
- An algebraic theory of graph reduction
- Recognizable sets of graphs: equivalent definitions and closure properties
- Commutative Regular Equations and Parikh's Theorem
- Algebraic automata and context-free sets
- Two Families of Languages Related to ALGOL
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item