Nondeterministic operations on finite relational structures

DOI10.1016/S0304-3975(97)00263-6MaRDI QIDQ1276248zbMATH OpenFDO

Authors Klaus Barthelmann

Publication date 20 January 1999

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

Full work available at URL https://doi.org/10.1016/S0304-3975(97)00263-6

zbMATH Keywords

context-free setformal languagehypergraphmonadic second-order logicmultivalued operationstransducer

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Formal languages and automata (68Q45)

Review text

Based on the introduction to universal algebra for language theory by \textit{B. Courcelle} [Theor. Comput. Sci. 163, 1-54 (1996; Zbl 0874.68170)], this expository article focuses on multivalued operations, which seem to be adequate for the handling of inductive sets of evaluations. In this framework, every transduction definable in counting monadic second-order logic is a bottom-up transduction on term representations.

Recommendations

• Uniform and nonuniform recognizability.
• scientific article; zbMATH DE number 1696755
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• An application of the matrix representation of transductions

Cites work

• A mathematical investigation of propagating graph 0L systems
• Algebraic automata and context-free sets
• Automata in general algebras
• Basic notions of universal algebra for language theory and graph grammars
• Bottom-up and top-down tree transformations— a comparison
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Graph expressions and graph rewritings
• Handbook of Graph Grammars and Computing by Graph Transformation
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 17539 (Why is no real title available?)
• scientific article; zbMATH DE number 3615891 (Why is no real title available?)
• scientific article; zbMATH DE number 1231486 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• scientific article; zbMATH DE number 965 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 809155 (Why is no real title available?)
• scientific article; zbMATH DE number 1456950 (Why is no real title available?)
• Minimal acyclic forbidden minors for the family of graphs with bounded path-width
• Monadic second-order definable graph transductions: a survey
• Monadic second-order evaluations on tree-decomposable graphs
• 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
• The monadic second-order logic of graphs. VIII: Orientations
• The monadic second-order logic of graphs. X: Linear orderings
• The structure of the models of decidable monadic theories of graphs
• The use of tree transducers to compute translations between graph algebras

Cited in

(1)

• Finite-State Map-Reduce Computation and Relational Algebra Queries

This page was built for publication: Nondeterministic operations on finite relational structures

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