Content deleted Content added
Citation bot (talk | contribs) Alter: journal. Add: volume, jstor, s2cid, authors 1-1. Removed proxy/dead URL that duplicated identifier. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Abductive | Category:Mathematical logic | #UCB_Category 188/207 |
Buchi-Elgot-Trakhtenbrot -- clarify per talk page |
||
Line 5:
== Variants ==
Monadic second-order logic comes in two variants. In the variant considered over structures such as graphs and in Courcelle's theorem, the formula may involve non-monadic predicates (in this case the binary edge predicate <math>E(x, y)</math>), but quantification is restricted to be over monadic predicates only. In the variant considered in automata theory and the Büchi-Elgot-Trakhtenbrot theorem, all predicates, including those in the formula itself, must be monadic, with the exceptions of equality (<math>=</math>) and ordering (<math><</math>) relations.
== Computational complexity of evaluation ==
| |||