Flerdimensionella medel-payoff- och energispel utgör den matematiska grunden för den kvantitativa studien av reaktiva system, och spelar en central roll i den framväxande kvantitativa teorin om verifiering och syntes. I detta arbete studerar vi strategisyntesen problem för spel med sådana flerdimensionella mål tillsammans med en paritet villkor, ett kanoniskt sätt att uttrycka vanliga förhållanden. Medan i allmänhet, de vinnande strategierna i sådana spel kan kräva oändligt minne, för syntes det mest relevanta problemet är byggandet av en ändlig-minne vinnande strategi (om man finns). Våra viktigaste bidrag är följande: För det första visar vi en tight exponentiellt bunden (matchande övre och nedre gränser) på det minne som krävs för finita-minne vinnande strategier i både flerdimensionella genomsnittliga payoff och energispel tillsammans med paritetsmål. Detta förbättrar avsevärt den tredubbla exponentiella övre gränsen för multienergispel (utan paritet) som kan härledas från resultat i litteratur för spel på vektor tilläggssystem med tillstånd. För det andra presenterar vi en optimal symbolisk och inkrementell algoritm för att beräkna en finit-minne vinnande strategi (om man finns) i sådana spel. Slutligen ger vi en fullständig karakterisering av när ändligt minne av strategier kan bytas bort mot slumpmässighet. I synnerhet visar vi att för en dimension medel-payoff paritet spel, randomiserade minneslösa strategier är lika kraftfulla som deras rena finita-minne motsvarigheter. Våra bidrag I detta arbete ger vi en utökad presentation av resultaten av Chatterjee et al. [21], den första studien av flerdimensionella energi- och medellönemål i kombination med paritetsmål. Sammanlänkning av paritetsmål med flerdimensionella kvantitativa mål hade aldrig tidigare övervägts [21]. Eftersom vi betraktar syntesen av finita-minne strategier, följer det av resultaten av Chatterjee et al. [19] att både problemen (flerdimensionell energi med paritet och flerdimensionella medelvärden med paritet) är likvärdiga. Våra huvudsakliga resultat för finit-minne strategisyntes för flerdimensionella energi paritetsspel är följande. i) Optimala minnesgränser. Vi visar först att minnet av exponentiell storlek är tillräckligt i flerdimensionella energi paritetsspel. Vårt resultat är en betydande förbättring jämfört med det resultat som kan erhållas naivt från de resultat som är kända i litteratur som ger en trippel exponentiellt bunden, även när det gäller flerdimensionella energispel utan paritet. För det andra visar vi en matchande lägre gräns genom att presentera en familj av spel grafer där exponentiellt minne är nödvändigt i flerdimensionella energispel (utan paritet), även när alla övergångsvikter tillhör {−1, 0, +1}. Således etablerar vi optimala minnesgränser för det finita-minnet strategisyntesproblem. ii) Symbolisk och inkrementell algoritm. Vi presenterar en symbolisk algoritm (i betydelsen Doyen och Raskin [25], dvs. med hjälp av en kompakt antikedje representation av uppsättningar genom deras minimala element) för att beräkna en finit-minne vinnande strategi, om man existerar, för flerdimensionella energi paritet spel. Vår algoritm är parameteriserad av det spektrum av energinivåer som ska beaktas under dess utförande. Så, vi kan använda det i en inkrementell strategi: först, vi söker efter ändliga-minne vinnande strategier med ett litet intervall, och öka intervallet endast när det är nödvändigt. Vi etablerar också en gräns på det maximala intervallet för att överväga som garanterar fullständigheten av den stegvisa tillvägagångssätt. I värsta fall kräver algoritmen exponentiellt lång tid. Eftersom exponentiellt storleksminne krävs (och även beslutsproblemet är coNP-fullständigt [19], kan det värsta fallet exponentiellt bundet anses vara optimalt. Dessutom, eftersom vår algoritm är symbolisk och inkrementell, i de flesta relevanta problem i praktiken, förväntas den vara effektiv. iii) Randomiserade strategier. Vi överväger också när (rena) finita-minnesstrategier kan handlas bort för konceptuellt mycket enklare randomiserade strategier. Vi visar att för energimål är randomisering inte till hjälp (eftersom energimål är liknande i andemening med säkerhetsmål), även med endast en spelare, inte heller är det för två-spelare flerdimensionella medel-pay-off mål. Men randomiserade minneslösa strategier räcker för en spelare flerdimensionella genomsnittliga-payoff paritetsspel. För det viktiga specialfallet av medel-payoff paritet mål (konjunktur av en enda medel-payoff och paritet mål), visar vi att i spel, finita-minne strategier kan handlas bort för randomiserade minneslösa strategier. Relaterade arbeten Detta dokument förlänger de resultat som presenterades i föregående konferensversion [21] och ger en fullständig presentation av de tekniska detaljerna. Spel med ett enda genomsnittligt vinstmål har studerats i [27, 45], och spel med ett enda energimål i [15]; deras likvärdighet fastställdes i [10]. Endimensionella medel-payoff paritet spel problem 123 132 K. Chatterjee et al. har studerats i [20] : en exponentiell algoritm gavs för att avgöra om det finns en vinnande strategi (som i allmänhet visade sig kräva oändligt minne); och en förbättrad algoritm presenterades i [11]. Endimensionell energi paritet spel problem har undersökts i [16]: det visades att avgöra förekomsten av en vinnande strategi är i NP  på coNP, och en exponentiell algoritm gavs. Det visades också i [16] att det för endimensionella energiparitetsmål är tillräckligt med finita-minnesstrategier med exponentiellt minne, och att beslutsproblemet för medel-betal-paritetsmål kan reduceras till energiparitetsmål. Spel på VASS med flera olika vinnande mål har studerats i [12], och från resultaten av Brázdil et al. [12] Det följer att i flerdimensionella energispel, vinnande strategier med ändligt minne är tillräckliga (och en trippel exponentiellt bunden på minnet kan härledas från resultaten). Komplexiteten av flerdimensionell energi och medel-payoff spel studerades i [19, 43]. Det visades i [19] att i allmänhet, vinnande strategier i flerdimensionella medel-payoff spel kräver oändligt minne, medan för flerdimensionella energispel, ändliga-minnesstrategier är tillräckliga. Dessutom, för finit-minne strategier, de multi-dimensionella medel-payoff och energispel sammanfaller, och optimal beräknings komplexitet för att avgöra förekomsten av en vinnande strategi fastställdes som coNP-fullständig [19, 43]. Flerdimensionella medel-payoff spel med oändliga minnes strategier studerades i [43], och optimala computational komplexitet resultat fastställdes. Olika beslutsproblem över flerdimensionella energispel studerades i [30]. Vi anser två spelare spelstrukturer och betecknar de två spelarna med P 1 och P 2. Multiviktiga tvåspelarstrukturer En flerviktig tvåspelarstruktur är en tuple G = (S 1, S 2, s init, E, k, w) där (i) S 1 och S 2 resp. betecknar de ändliga uppsättningar av stater som hör till P 1 och P 2, med S 1  på S 2 = ∅; (ii) s init S = S 1 är det ursprungliga tillståndet; (iii) E  på S × S är uppsättningen av kanter s.t. För alla s S, finns det s S s.t. (s, s ) E; (iv) k  till N är dimensionerna på viktvektorerna; och (v) w : E → Z k är multiviktig märkningsfunktion. Spelstrukturen G är en spelare om S 2 = ∅. Ett spel i G är en oändlig sekvens av tillstånd π = s 0 s 1 s 2... s.t. s 0 = s init och för alla i ≥ 0, vi har (s i, s i+1 ) E. Prefixet upp till n-th läget π = s 0 s 1... s n..... är den ändliga sekvensen π(n) = s 0 s 1... s n. Låt först (π(n))) och Last (π(n)) resp. betecknar s 0 och s n, de första och sista tillstånden i π(n). Ett prefix π(n) tillhör P i, i  ska {1, 2}, om Sista (π(n))  och S i. Uppsättningen av pjäser med G betecknas av Plays(G) och motsvarande uppsättning prefix betecknas med Prefs(G). Den uppsättning prefix som tillhör P i betecknas med Prefs i (G). Energinivåvektorn för en sekvens av tillstånd w(s i, s i+1 ) och medel-payoff vektorn för ett spel π = s 0 s 1.... är MP(π) = lim inf n→❌ 1 n EL(π(n)). Paritet En spelstruktur G utökas med en prioriterad funktion p : S → N till strukturen G p = (S 1, S 2, s init, E, k, w, p). Med tanke på ett spel π = s 0 s 1 s 2..., Vi definierar Inf (π) = {s  på grund av att det är ett spel som är lika med 1 s 2,....................................................................................................................................... s n = s}, den uppsättning tillstånd som visas oändligt ofta längs π. Likheten i ett spel π definieras som Par(π) = min { p(s). s  på Inf(π)}. I följande definitioner betecknar vi alla spel med G p utan förlust av allmängiltighet. Strategier Eftersom en ändlig uppsättning A, en sannolikhetsfördelning på A är en funktion p : A → [0, 1] s.t. a till A p(a) = 1. Vi betecknar uppsättningen sannolikhetsfördelningar på A av D( A).
I REF studeras energispel, som är spel på räknare system och målet med spelet är att spela för alltid utan någon räknare som går under noll utöver tillfredsställande paritet villkor på kontroll stater som besöks oändligt ofta.
Strategy synthesis for multi-dimensional quantitative objectives
{'venue': 'Acta Informatica', 'journal': 'Acta Informatica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}