Revision as of 06:29, 8 August 2023 edit Citation bot (talk \| contribs) Bots 5,870,213 edits Alter: title, template type. Add: chapter-url, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. \| Use this bot. Report bugs. \| Suggested by Headbomb \| Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox3 \| #UCB_webform_linked 1327/2306 ← Previous edit		Revision as of 06:51, 8 August 2023 edit undo Headbomb (talk \| contribs) Edit filter managers, Autopatrolled, Extended confirmed users, Page movers, File movers, New page reviewers, Pending changes reviewers, Rollbackers, Template editors 473,516 edits m clean up, removed stub tag Tag: AWB Next edit →
Line 34: The satisfiability problem for monadic second-order logic is undecidable in general because this logic subsumes [[first-order logic]]. The monadic second-order theory of the infinite complete [[binary tree]], called [[S2S (mathematics) \| S2S]], is [[decidability (logic)\|decidable]].<ref>{{Cite journal\|last=Rabin\|first=Michael O.\|date=1969\|title=Decidability of Second-Order Theories and Automata on Infinite Trees\|url=https://www.jstor.org/stable/1995086\|journal=[[Transactions of the American Mathematical Society]]\|volume=141\|pages=1–35\|doi=10.2307/1995086\|jstor=1995086\|issn=0002-9947}}</ref> As a consequence of this result, the following theories are decidable: * The monadic second-order theory of trees. * The monadic second-order theory of <math>\mathbb{N}</math> under successor (S1S). Line 55: {{Mathematical logic}} ~~{{Logic-stub}}~~ [[Category:Mathematical logic]]

Monadic second-order logic: Difference between revisions