Abstrakt. Ong har visat att problemet med kontroll av modal mu-calculus-modellen (likvärdigt är problemet med att acceptera alternerande paritetsträd (APT)) för eventuelltinfinita rankade träd som genereras av ordnings-n-rekursionssystem är helt och hållet n-EXPTIME. Vi överväger två underklasser av APT och undersöker komplexiteten i respektive acceptansproblem. De viktigaste resultaten är att för APT med en enda prioritering är problemet fortfarande n-EXPTIME komplett, medan för APT med en diskontiv övergångsfunktion är problemet (n- 1)-EXPTIME fullständigt. Denna studie motiverades av Kobayashis senaste arbete som visar att resursanvändningsverifieringen av funktionella program kan reduceras till modellkontroll av rekursionsprogram. Som ett program visar vi att resursanvändningsverifieringsproblemet är komplett (n − 1)-EXPTIME.
Reachability problem för callby-name program är ett exempel på högre ordning modellkontroll, och (n-1)-EXPTIME komplett för order-n program REF.
Complexity of Model Checking Recursion Schemes for Fragments of the Modal Mu-Calculus
{'venue': 'LMCS 7 (4:9) 2011', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}