2013/02/28 by Bastien Maubert, Sophie Pinchinat, Laura Bozzelli
Computer Science · Mathematics · #Algorithm #Arithmetic #Binary number #Binary relation #Computer science #Data mining #Discrete mathematics #Equivalence (formal languages) #Equivalence relation #Formal language #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Mathematics #Multi-Agent Systems and Negotiation #Observational equivalence #Relation (database) #Theoretical computer science #cs.CC #cs.GT #cs.LO
paper · pdf · doi:10.4204/eptcs.112.17
published as EPTCS 112, 2013, pp. 115-122 · In Proceedings SR 2013, arXiv:1303.0071
openalex publication_date 2013/02/28 · arxiv created 2013/03/04 · arxiv updated 2013/03/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We investigate uniformity properties of strategies. These properties involve sets of plays in order to express useful constraints on strategies that are not μ-calculus definable. Typically, we can state that a strategy is observation-based. We propose a formal language to specify uniformity properties, interpreted over two-player turn-based arenas equipped with a binary relation between plays. This way, we capture e.g. games with winning conditions expressible in epistemic temporal logic, whose underlying equivalence relation between plays reflects the observational capabilities of agents (for example, synchronous perfect recall). Our framework naturally generalizes many other situations from the literature. We establish that the problem of synthesizing strategies under uniformity constraints based on regular binary relations between plays is non-elementary complete.