I detta dokument föreslår vi en induktiv strategi för att visa sig vara positiv nästan säker på att probabilistisk omskrivning avslutas inom ramen för den innersta strategin. Vi utvidgar till det probabilistiska fallet en teknik som vi föreslog för att avsluta vanliga omskrivning under strategier. Induktionsprincipen består i att anta att termer som är mindre än utgångspunkterna för en induktionsbeställning är positivt nästan säkert avslutande. Beviset är utvecklat för att generera bevisträd, modellera omskrivning träd, alternativt tillämpa abstraktion steg, uttrycka tillämpningen av induktionshypotesen, och begränsa steg, simulera möjliga omskrivning steg efter abstraktion. Denna teknik kan automatiseras helt, särskilt för att skriva om system på konstanter, mycket användbart för att modellera probabilistiska protokoll.  Kategorier och ämnesdeskriptorer F.3.1 [LOGISK OCH VÄRDEN AV PROGRAMS Nyckelord Abstraction, Restriktion, Begränsande, Sannolikhet, Uppsägning Tillstånd att göra digitala eller hårda kopior av hela eller delar av detta verk för personligt bruk eller klassrumsbruk beviljas utan avgift förutsatt att kopior inte görs eller distribueras för vinst eller kommersiell fördel och att kopior bär detta meddelande och den fullständiga citeringen på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift.  Probabilistisk omskrivning har nyligen införts för att modellera system, där probabilistiska och icke-deterministiska fenomen kombineras [7]. Många modeller av system, formalismer eller tekniker har redan berikats med sannolikheter, men de flesta av dem är begränsade till ändliga tillståndssystem. Låt oss citera automatiska modeller [11, 42] Omskrivning gör det möjligt att uttrycka komplexa relationer på oändliga uppsättningar av stater på ett ändligt sätt, förutsatt att de är räknebara. Omskrivning ger också en trevlig programmering paradigm: den regelbaserade formalismen gör det enkelt att skriva program på ett deklarativt sätt och den underliggande algebraiska semantik möjliggör automatiserade eller semi-automatable korrekthet bevis på programmen. Regelbaserade programmeringsspråk och -miljöer används nu för alla typer av tillämpningar. Låt i samband med probabilistisk omskrivning, problemet med uppsägning naturligt uppstår och i [4], begreppen enkel nästan säker uppsägning och positiv nästan säker (PAS i korthet) uppsägning har föreslagits, liksom en metod som bygger på tolkningar på reals för att säkerställa den andra egendomen. Det första termineringsbegreppet uttrycker att sannolikheten för att en viss omskrivning ska upphöra är 1; det andra, starkare och mer användbart ur praktisk synvinkel, uttrycker att den genomsnittliga längden på derivatationerna från en term är ändlig. Sedan, i [5], omskrivning strategier har övervägts, och tillräckliga kriterier, fortfarande baserat på tolkningar på reals, har getts för PAS uppsägning under strategier. Här försöker vi gå ett steg längre. I det tidigare citerade dokumentet definierade de berörda strategierna sig själva med sannolikheter, vilket uttryckte förhållandet mellan valet av en regel w.r.t och en annan. Vi hanterar här PAS terminering problem för positionsstrategier, definieras av positionen för redexes i de termer som ska skrivas om, med hjälp av en induktiv strategi som vi föreslog för att bevisa avslutande av icke-probabilistiska omskrivning under den innersta [14], de yttersta [15] och lokala strategier [13]. I den här artikeln anpassar vi vår induktiva teknik till det probabilistiska fallet, undersöker hur den då fungerar och ger en klass av system som den är av intresse för. Vi fokuserar här på den innersta strategin, som består i att alltid skriva om på lägsta möjliga positioner. Denna strategi används i stor utsträckning i programplaneringen. Det används ofta som en inbyggd mekanism vid utvärderingen av regelbaserade eller funktionella språk. Dessutom, för icke-överlappande eller lokalt sammanflätade overlay-system [21], eller system som uppfyller kritiska toppförhållanden [22], är den innersta termineringen likvärdig med standard terminering (dvs. uppsägning för standardomskrivning, som består i omskrivning utan någon strategi). Observera att som bevisas i [26], vänster mest inre uppsägning och innersta uppsägning av omskrivning är likvärdiga. En formalism har nyligen föreslagits för att utvidga processen med begränsningshantering med probabilistiska möjligheter som tillämpas på själva omskrivningsreglerna [16, 35, 36, 34, 37]. Detta är, enligt vår kunskap, förutom de tidigare citerade verken om ELAN, Tom och Maude, det enda försöket att formalisera probabilistiska övergångar med hjälp av regelbaserade språk. Lägg märke till att dessa dokument inte fokuserar på tekniker för att bevisa att sådana system avslutas. Det finns andra arbeten om avslutande med sannolikheter, men i samband med samtidiga program [40, 39]. De hanterar nästan säker uppsägning, medan vi hanterar positiv nästan säker uppsägning. Grundtanken i vårt tillvägagångssätt är följande: Vi introducerar begreppet innersta PAS (IPAS i kort) terminering för en sikt, och antar, för varje term t av en markterm algebra, att termerna mindre än t för en induktionsbeställning är IPAS terminering. Vi försöker sedan dra slutsatsen att t också är IPAS-avslutande. Principen för vår induktiva metod ligger i en dubbel mekanism som gör det möjligt att generera bevisträd, som genom en lyftmekanism representerar omskrivningen av marktermer: abstraktion och förträngning. Papperet är uppbyggt på följande sätt: I avsnitt 2 presenteras bakgrunden. Avsnitt 3 ägnas åt definitioner av probabilistisk omskrivning. I avsnitt 4 definieras materialet för vår induktiva teknik i det probabilistiska fallet. Avsnitt 5 ger algoritmen generera bevisträd och IPAS avslutande resultat för ändliga bevisträd. Slutligen, Avsnitt 6 presenterar en generalisering till en given klass av oändliga bevisträd. Vi antar att läsaren är bekant med de grundläggande definitioner och anmärkningar av termen omskrivning ges till exempel i [1, 12, 41]. T (F, X ) är den uppsättning termer som byggts från en given ändlig uppsättning F funktionssymboler f som har arity n  på N, och en uppsättning X av variabler betecknade x, y... T (F) är uppsättningen av marktermer (utan variabler). Symbolerna för arity 0 är också termer som kallas konstanter. Positioner i en term representeras som sekvenser av heltal. Den tomma sekvensen betecknar den översta positionen. Låt p och p vara två positioner. Position p sägs vara (en strikt) prefix av p (och p suffix av p) om p = pλ, där λ är en (icke-tomma) sekvens av heltal. För en position p av en term t, vi noterar t på delterm av t på position p, och t [s]p den term som erhålls i att ersätta med s delterm på position p in t. En ersättning är en tilldelning från X till T (F, X ), skriftlig σ = (x = t,. .., y = u). Det unikt sträcker sig till en endomorfism av T (F, X ). Resultatet av att tillämpa σ på en term t  ska T (F, X ) är skrivet σ(t) eller σt. Domänen för σ, betecknad Dom(σ) är den finita undergruppen av X sådan att σx = x. En instantiering eller marksubstitution är ett uppdrag från X till T (F). Id betecknar identitetssubstitutionen. Sammansättningen av substitutioner σ1 följt av σ2 betecknas σ2σ1. En uppsättning R av skriva om regler eller skriva om system (RS i korthet) på T (F, X ) är en uppsättning par av termer av T (F, X ), betecknade l → r, sådan att V ar (r) V ar (l). Med tanke på ett omskrivningssystem R kallas en funktionssymbol i F en konstruktör iff som inte förekommer i R högst upp på en vänster sida av regeln, och kallas annars en definierad funktionssymbol. Den uppsättning konstruktörer av F för R som betecknas CR, och uppsättningen av definierade funktionssymboler DR (R utelämnas när det inte finns någon tvetydighet). I det här dokumentet tar vi bara hänsyn till finita uppsättningar funktionssymboler och omskrivningsregler. Den skrivande relationen som induceras av R betecknas med → R (→ om det inte finns någon tvetydighet på R), och definieras av s → t if det finns en substitution σ och en position p i s sådan att s påp = σl för någon regel l → r av R, och t = s [σr]p. Detta är skrivet s → R p,l→r,σ t där p, l → r, σ eller R kan utelämnas; s påp kallas redex. Den innersta omskrivningsrelationen består i att alltid skriva om på lägsta möjliga positioner. Låt R vara ett omskrivningssystem på T (F, X ). En term t begränsas till t, vid icke-variabel position p, med hjälp av omskrivningsregeln l → r av R och substitutionen σ, när σ är en mest allmän unifier av t på p och l, och t = σ(t[r]p). Detta betecknas t R p,l→r,σ t där p, l → r, σ eller R kan utelämnas. Det antas alltid att det inte finns någon skillnad mellan regeln och termen, d.v.s. att V ar(l) och V ar(t) = ∅. En beställning på T (F, X ) sägs vara noetherian iff det finns ingen oändligt minskande kedja för denna beställning. Det är monoton iff för varje par av termer t, t av T (F, X ), För F och X ändlig, om är monoton och har subterm egendom, då är det noetherian [27]. Om dessutom är stabil under substitution (för någon substitution σ, någon par av termer t, t. T (F, X ), t t innebär σt σt ), då kallas det en förenkling beställning. A RS R (inrest) avslutas om och endast om varje (inre) härledning av det omskrivningsförhållande som induceras av R är ändlig. För alla termer t av T (F), t (inrest) avslutas om och endast om varje (inre) omskrivning härledd från t är ändlig. En σ-algebra på en uppsättning är en uppsättning undergrupper av  och som innehåller den tomma uppsättningen, och är stabil genom räknabar union och komplettering. I synnerhet, uppsättningen av undergrupper är en naturlig σ-algebra för alla räkningsbara uppsättning. Ett mätbart utrymme är en uppsättning med en σ-algebra på. En sannolikhet är en funktion P från en σ-algebra till [0, 1], som är anmärkningsvärt additiv, och sådan att P ( ska) = 1. En trilling ( ska, σ, P ) kallas en sannolikhet utrymme. För mer information, se [23]. En stokastisk sekvens på en uppsättning A är en familj (Xi) i-N, av slumpmässiga variabler definieras på vissa fasta sannolikhetsutrymme (-, σ, P ) med värden på A. [4] Med tanke på några räknebara uppsättningen S noterar vi Dist(S) för uppsättningen sannolikhetsfördelningar på S: μ  på Dist(S) är en funktion S → [0, 1] som uppfyller P i och med att μ(i) = 1. Ett probabilistiskt abstrakt reduktionssystem (PARS) är ett par A = (A, →) som består av en räknebar uppsättning A och ett förhållande → och A × Dist(A). Ett tillstånd en A med ingen μ sådan att en → μ sägs terminal. 168 En historia är en ändlig sekvens a0a1 · · · en av elementen i tillståndsrymden A. Det är icke-terminal om en är lika bra. En historia uttrycker utvecklingen av en PARS. Ovanstående definition förutsätter att strategierna måste vara deterministiska. En härledning av A är då en stokastisk sekvens där de icke-deterministiska valen ges av någon politik, och de probabilistiska valen styrs av motsvarande fördelningar. • och för alla t / A: Om en härledning är sådan att πn =  på vissa n, sedan π n =  till nästan säkert för alla n ≥ n. En sådan härledning sägs vara avslutande. Om k är det största heltal för vilket π k =  på, då π k kallas en normal form (av π0). En icke-avslutande härledning är sådan att πn  på A (πn = ) för alla n. Följande definition generaliseras från [5] till en kategori av politik 0. Definition 4 (PAS-uppsägning). En PARS A = (A, →) kommer att sägas positivt nästan säkert (PAS) avsluta (under en klass av strategier 0) om för alla politikområden  och för alla stater en A, det genomsnittliga antalet minskning steg (medellängden av derivatationerna) för att nå en normal form från en under politik., betecknad av T [a,  och], är ändlig. Ett probabilistiskt omskrivningssystem är en ändlig uppsättning R av probabilistiska omskrivningsregler. Ett probabilistiskt abstrakt reduktionssystem (T (F, X ), →R) över uppsättningen termer T (F, X ) är associerad till ett probabilistiskt omskrivningssystem där →R definieras enligt följande. Till exempel, med probabilistic rewrite regel {f (x, y) → g(a) : 1/2 : 1/2} vars högra sida betecknar fördelningen med värdet 1/2 på g(a) och värdet 1/2 på y, f (b, c) skriver om till g(a) med sannolikhet 1/2, till c med sannolikhet 1/2 och f (b, g(a)) skriver om till g(a) med sannolikhet 1. Den mest probabilistiska omskrivningen består i att alltid tillämpa ovanstående definition på lägsta möjliga positioner i termer som ska skrivas om. Ett probabilistiskt rewrite system R är innersta positivt nästan säkert (IPAS) som avslutas om den tillhörande PARS är PAS som avslutas under klass 0Inn av policyer som motsvarar den innersta rewriting derivation. En term t på vilken ingen regel av R gäller sägs vara i normal form för R. Om en sådan term t är på a(n) (inre) omskrivning derivatation av en term u, då t kallas (inre) normal form av u, och noteras u↓. Till varje omskrivning härledd t0, t1,. .., tn = t0↓ motsvarar en härledning π0, π1,. ., πn, πn+1............................................................ ... där πi =  till i > n. För att bevisa att ett probabilistic rewrite system på T (F) är IPS terminering, introducerar vi en lokal uppfattning om IPS terminering på villkor, och bevisa denna egenskap för varje term av T (F). För att bevisa att en term t av T (F) är IPAS avslutande, vi fortsätter genom induktion på T (F) med en noeterisk beställning, antar egenskapen för varje t sådan att t t. För att motivera icke-tomhet av T (F) och en grund för induktion, antar vi att F innehåller minst en konstruktör konstant. Den huvudsakliga intuitionen är att observera probabilistiska rewriting härleder från en markterm t (F) som är någon instans av ett mönster g(x1,. .., xm) T (F, X ), för vissa definierade funktionssymbol g  på D, och variabler x1,. ....................................................................... Bevisa egendom IPAS uppsägning på marken villkor innebär att bevisa att varje grund instans av mönster g(x1,. .., xm) är IPAS avslutande. Omskrivning derivat simuleras, med hjälp av en lyftmekanism, av ett bevisträd utvecklat från g(x1,. ., xm) på T (F, X ), för varje g D, genom att alternativt använda två huvudbegrepp, nämligen förträngning och abstraktion. Mer exakt, begränsar schemat omskrivning möjligheter termer. Abstraktion simulerar minskningen av subtermer i derivatationerna tills dessa subtermer blir normala former. Det uttrycker tillämpningen av induktionshypotesen på dessa subtermer: om de är IPAS avslutande, med ett genomsnittligt antal minskning steg, de skriva om till en normal form. Schemat av mark rewriting derivatations uppnås genom begränsningar. Noderna av de utvecklade bevisträden består av en aktuell term av T (F, X ), och en uppsättning marksubstitutioner som representeras av en begränsning gradvis byggd längs de successiva abstraktion och förträngning steg. Varje nod i ett abstrakt träd schemalägger en uppsättning marktermer: alla grundfall av den nuvarande termen, som är lösningar av tvånget. Begränsningen består i själva verket av två typer av formler: att beställa begränsningar, som ska motivera giltigheten av de induktiva stegen, och abstraktion begränsningar kombinerade 169 till att begränsa substitutioner, som effektivt definierar relevanta uppsättningar av marktermer. För en term t T (F, X ) som förekommer i ett bevisträd utfärdat från en referensterm t ref = g(x1,. ., xm), • För det första, marken fall av vissa subtermer t på t (karakteriseras av den begränsning som är förknippad med t) antas vara IPAS avslutande, genom induktion hypotes, om inte ref  på grund av induktion beställning och för varje lösning av begränsningen i samband med t. De ersätts i t med abstraktion variabler Xj representerar respektive någon av sina normala former, implicit motsvarar en av de normala former de har vid omskrivning enligt någon policy  och OEM Inn. Resonemang genom induktion tillåter oss att bara anta existensen av de normala formerna utan att uttryckligen beräkna dem. Om grundfallen för den resulterande termen är IPS-avslutande (antingen om induktionshypotesen kan tillämpas på dem, eller om de kan bevisas IPS-avslutande på annat sätt, kommer vi att presentera senare), då är grundfallen för den ursprungliga termen IPS-avslutande. Denna teknik är inspirerad av den som vi föreslog för att bevisa att icke-probabilistiska omskrivningssystem har avbrutits i det innersta. Vi introducerar nu några koncept för att formalisera och automatisera det. Induktionsbeställningen begränsas längs med beviset av skillnader mellan termer som måste vara jämförbara, varje gång induktionshypotesen används i abstraktionsmekanismen. Denna beställning är inte definierat a priori, men bara måste verifiera ojämlikhet i formen t > u1,. .., um, ackumuleras längs bevis, och som kallas order begränsningar. För att fastställa bevisen för induktiva uppsägningar räcker det alltså med att avgöra om beställningsbegränsningarna är tillfredsställande. Tillfredsställandet av en begränsningsförbindelse C av denna form är oavgjort. Men ett tillräckligt villkor för en beställning P på T (F, X ) för att tillfredsställa C är att t P t för varje begränsning t > t av C, och P är stabil under substitution. Förenklingsbeställningar uppfyller ett sådant villkor. Så i praktiken är det tillräckligt att hitta en förenkling beställning P sådan att t P t för varje begränsning t > t av C. Beställningen P, definieras på T (F, X ), kan sedan ses som en förlängning av induktionsbeställning på T (F). För bekvämlighetens skull kommer P också att skrivas. Att lösa beställningsbegränsningar för att hitta förenklingsbeställningar är ett välkänt problem. Det enklaste sättet och ett automatiserat sätt att gå vidare är att testa enkla befintliga beställningar som subterm order, Recursive Path Ordering, eller Lexicographic Path Ordering. Detta är ofta tillräckligt för de begränsningar som beaktas här: tack vare kraften i induktion, de är ofta enklare än för terminering metoder direkt med beställning för orientering om skrivregler. Om dessa enkla beställningar inte är tillräckligt kraftfulla, kan automatiska lösare som Cime 1 ge tillräckliga polynomiska beställningar. Att abstrakt en term t på positioner i1,. .., ip, där t på j är tänkt att ha en normal form t påj ↓, ersätter vi t påj med abstraktion variabler Xj som representerar respektive någon av deras möjliga normala former för någon politik  på 0 inn. Låt oss definiera dessa speciella variabler mer formellt.
Uppsägning i samband med omskrivningssystem utvecklade Gnaedig REF ett bevissystem för positiva a.s.
Induction for positive almost sure termination
{'venue': "PPDP '07", 'journal': None, 'mag_field_of_study': ['Computer Science']}