OATAO är ett open access arkiv som samlar Toulouse forskares arbete och gör det fritt tillgängligt över webben där det är möjligt Abstract. Gossip problem är att planera problem där flera agenter måste dela information (hemligheter) genom telefonsamtal mellan två agenter. I epistemiska skvallerproblem kan målet vara att uppnå kunskap om högre ordning, d.v.s. kunskap om andra agenters kunskap; i detta syfte kommunicerar samtalsagenter inte bara hemligheter, utan även agenters kunskap om hemligheter, agenters kunskap om andra agenters kunskap om hemligheter, etc. Temporala epistemiska skvallerproblem medför dessutom begränsningar i samtalstiderna. Dessa begränsningar är av två slag: antingen föreskriver de att ett samtal mellan två agenter måste göras vid någon tidpunkt, eller så föreskriver de att ett samtal kan göras inom någon möjlig (uppsättning av) intervall. I den icke-temporella versionen, samtal mellan två agenter är antingen alltid möjligt eller alltid omöjligt. Vi undersöker komplexiteten i problemet med planens existens i denna gen-erala miljö. När det gäller den övre gränsen, bevisar vi att det är i NP i det allmänna fallet, och att det är i P när problemet är non-temporal och målet är en positiv epistemisk formel. När det gäller den nedre gränsen, bevisar vi NPfullständighet för två fragment: problem med möjligen neg-ative mål även i icke-temporal fall, och problem med temporal begränsningar även om målet är en uppsättning positiva atomer.
I REF studerades sådana problem vidare i närvaro av tidsbegränsningar, dvs. ett givet samtal kan endast (eller måste) göras inom ett givet tidsintervall.
Temporal Epistemic Gossip Problems
{'venue': 'EUMAS', 'journal': None, 'mag_field_of_study': ['Computer Science']}