Den fullt berikade μ-calculus är förlängningen av den propositionella μ-calculus med inversa program, graderade modaliteter och nominella. Även om tillfredsställande i flera expressiva fragment av den fullt anrikade μ-calculus är känd för att vara decidable och EXPTIM-fullständig, har det nyligen bevisats att den fullständiga kalkylen är obestämd. I detta dokument studerar vi fragmenten av de fullt berikade μ-kalculus som erhålls genom att släppa minst en av de ytterligare konstruktionerna. Vi visar att i alla fragment som erhålls på detta sätt är tillfredsställelsen decedable och EXPTIM-fullständig. Således identifierar vi en familj av decibel logik som är maximal (och ojämförlig) i uttryckskraft. Våra resultat uppnås genom att införa två nya automatiserade modeller, som visar att deras tomhet problem är EXPTIM-komplett, och sedan minska tillfredsställelse i relevanta logiker till dessa problem. De automatiserade modellerna vi introducerar är tvåvägsväxande paritetsautomata över oändliga träd (2GAPT) och fullt berikade automata (FEA) över oändliga skogar. De förra är en allmän generalisering av två ojämförliga automatiserade modeller från litteraturen. Den senare sträcker sig alternerande automata på ett liknande sätt som den fullt anrikade μ-calculus utökar standard μ-calculus.
Giltighets-/tillfredställbarhetsproblemet för μ-kalculus är i EXPTIME-fullständig REF.
The Complexity of Enriched Mu-Calculi
{'venue': 'LMCS 4 (3:11) 2008', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}