A regular characterization of graph languages definable in monadic second-order logic (Q1177179): Difference between revisions

@@ Property / MaRDI profile type @@
+Publication
@@ Property / MaRDI profile type: Publication / rank @@
+Normal rank
@@ Property / cites work @@
+Q3812222
@@ Property / cites work: Q3812222 / rank @@
+Normal rank
@@ Property / cites work @@
+Weak Second‐Order Arithmetic and Finite Automata
+Normal rank
@@ Property / cites work @@
+Q5525343
@@ Property / cites work: Q5525343 / rank @@
+Normal rank
@@ Property / cites work @@
+The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
+Normal rank
@@ Property / cites work @@
+Q4729378
@@ Property / cites work: Q4729378 / rank @@
+Normal rank
@@ Property / cites work @@
+Tree acceptors and some of their applications
@@ Property / cites work: Tree acceptors and some of their applications / rank @@
+Normal rank
@@ Property / cites work @@
+Decision Problems of Finite Automata Design and Related Arithmetics
+Normal rank
@@ Property / cites work @@
+Characterization of \(\omega\)-regular languages by first-order formulas
+Normal rank
@@ Property / cites work @@
+Decidability of Second-Order Theories and Automata on Infinite Trees
+Normal rank
@@ Property / cites work @@
+Q3692864
@@ Property / cites work: Q3692864 / rank @@
+Normal rank
@@ Property / cites work @@
+Generalized finite automata theory with an application to a decision problem of second-order logic
+Normal rank
@@ Property / cites work @@
+Q4385530
@@ Property / cites work: Q4385530 / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0304-3975(91)90078-g
+Normal rank
@@ Property / OpenAlex ID @@
+W1970456124
@@ Property / OpenAlex ID: W1970456124 / rank @@
+Normal rank
@@ Property / Recommended article @@
+Q3077955
@@ Property / Recommended article: Q3077955 / rank @@
+Normal rank
@@ Property / Recommended article: Q3077955 / qualifier @@
+Similarity Score: 0.94391066Amount 0.94391066
Unit 1
-Amount
+.94391066
 Unit
@@ Property / Recommended article: Q3077955 / qualifier @@
+Recommender Run: Recommender Run 3
@@ Property / Recommended article @@
+Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects
+Normal rank
+Similarity Score: 0.93947315Amount 0.93947315
Unit 1
-Amount
+.93947315
 Unit
+Recommender Run: Recommender Run 3
@@ Property / Recommended article @@
+Monadic Second-Order Logic for Graphs: Algorithmic and Language Theoretical Applications
+Normal rank
+Similarity Score: 0.93799Amount 0.93799
Unit 1
-Amount
+.93799
 Unit
+Recommender Run: Recommender Run 3
@@ Property / Recommended article @@
+Q3975133
@@ Property / Recommended article: Q3975133 / rank @@
+Normal rank
@@ Property / Recommended article: Q3975133 / qualifier @@
+Similarity Score: 0.931015Amount 0.931015
Unit 1
-Amount
+.931015
 Unit
@@ Property / Recommended article: Q3975133 / qualifier @@
+Recommender Run: Recommender Run 3
@@ Property / Recommended article @@
+Q4205068
@@ Property / Recommended article: Q4205068 / rank @@
+Normal rank
@@ Property / Recommended article: Q4205068 / qualifier @@
+Similarity Score: 0.9285535Amount 0.9285535
Unit 1
-Amount
+.9285535
 Unit
@@ Property / Recommended article: Q4205068 / qualifier @@
+Recommender Run: Recommender Run 3
@@ Property / Recommended article @@
+The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
+Normal rank
+Similarity Score: 0.9285453Amount 0.9285453
Unit 1
-Amount
+.9285453
 Unit
+Recommender Run: Recommender Run 3
@@ Property / Recommended article @@
+The monadic second-order logic of graphs. IV: Definability properties of equational graphs
+Normal rank
+Similarity Score: 0.92759544Amount 0.92759544
Unit 1
-Amount
+.92759544
 Unit
+Recommender Run: Recommender Run 3
@@ Property / Recommended article @@
+Graph decompositions definable in monadic second-order logic
+Normal rank
+Similarity Score: 0.9254075Amount 0.9254075
Unit 1
-Amount
+.9254075
 Unit
+Recommender Run: Recommender Run 3
@@ Property / Recommended article @@
+Monadic second-order definable graph transductions: a survey
+Normal rank
+Similarity Score: 0.921069Amount 0.921069
Unit 1
-Amount
+.921069
 Unit
+Recommender Run: Recommender Run 3
@@ Property / Recommended article @@
+Q4005197
@@ Property / Recommended article: Q4005197 / rank @@
+Normal rank
@@ Property / Recommended article: Q4005197 / qualifier @@
+Similarity Score: 0.9187895Amount 0.9187895
Unit 1
-Amount
+.9187895
 Unit
@@ Property / Recommended article: Q4005197 / qualifier @@
+Recommender Run: Recommender Run 3
@@ links / mardi / name / links / mardi / name @@
+Publication:1177179

Latest revision as of 06:37, 5 April 2025

scientific article

Language	Label	Description	Also known as
English	A regular characterization of graph languages definable in monadic second-order logic	scientific article

Statements

instance of

scholarly article

0 references

title

A regular characterization of graph languages definable in monadic second-order logic (English)

0 references

author

Joost Engelfriet

0 references

published in

Theoretical Computer Science

0 references

publication date

26 June 1992

0 references

review text

The author shows that the class of graph languages definable by monadic second-order logic, can be characterized as the smallest class containing certain elementary graph languages, and closed under the boolean operations (union, intersection, and complement) and under relabeling. Similar characterization is given to classes of graph languages restricted by some label-independent properties. Some examples are discussed.

0 references

reviewed by

Giora Slutzki

0 references

zbMATH Keywords

graph languages

0 references

monadic second-order logic

0 references

MaRDI profile type

Publication

0 references