Abstrakt. Vi presenterar en ny algoritm för modellkontroll av svag monadisk logik i andra ordningen på induktiva strukturer, en klass av strukturer med begränsad kliquebredd. Vår algoritm manipulerar formler direkt och kontrollerar dem på strukturen av intresse, vilket undviker både användningen av automata och behovet av att tolka strukturen i binärt träd. Utöver algoritmen ger vi ett nytt bevis på att svagt MSO är decibelt på induktiva strukturer som följer Shelahs kompositionsmetod. Genom att generalisera denna bevisteknik, får vi möjlighet att fatta beslut om svag MSO förlängd med den obegränsade kvantifiern på binärträdet, som var öppen tidigare.
Slutligen utvecklade Ganzow och Kaiser REF ett nytt beslutsförfarande för den svaga monadiska andra ordningens logik om induktiva strukturer inom deras verktyg T.
New Algorithm for Weak Monadic Second-Order Logic on Inductive Structures
{'venue': 'CSL', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}