10,613 research outputs found
Characterising Memory in Infinite Games
No full textThis paper is concerned with games of infinite duration played over potentially infinite graphs. Recently, Ohlmann (TheoretiCS 2023) presented a characterisation of objectives admitting optimal positional strategies, by means of universal graphs: an objective is positional if and only if it admits well-ordered monotone universal graphs. We extend Ohlmann’s characterisation to encompass (finite or infinite) memory upper bounds.
We prove that objectives admitting optimal strategies with ε-memory less than m (a memory that cannot be updated when reading an ε-edge) are exactly those which admit well-founded monotone universal graphs whose antichains have size bounded by m. We also give a characterisation of chromatic memory by means of appropriate universal structures. Our results apply to finite as well as infinite memory bounds (for instance, to objectives with finite but unbounded memory, or with countable memory strategies).
We illustrate the applicability of our framework by carrying out a few case studies, we provide examples witnessing limitations of our approach, and we discuss general closure properties which follow from our results
Positionality in Σ⁰₂ and a Completeness Result
No full textWe study the existence of positional strategies for the protagonist in infinite duration games over arbitrary game graphs. We prove that prefix-independent objectives in Σ⁰₂ which are positional and admit a (strongly) neutral letter are exactly those that are recognised by history-deterministic monotone co-Büchi automata over countable ordinals. This generalises a criterion proposed by [Kopczyński, ICALP 2006] and gives an alternative proof of closure under union for these objectives, which was known from [Ohlmann, TheoretiCS 2023].
We then give two applications of our result. First, we prove that the mean-payoff objective is positional over arbitrary game graphs. Second, we establish the following completeness result: for any objective W which is prefix-independent, admits a (weakly) neutral letter, and is positional over finite game graphs, there is an objective W' which is equivalent to W over finite game graphs and positional over arbitrary game graphs
A technique to speed up symmetric attractor-based algorithms for parity games
No full textThe classic McNaughton-Zielonka algorithm for solving parity games has excellent performance in practice, but its worst-case asymptotic complexity is worse than that of the state-of-the-art algorithms. This work pinpoints the mechanism that is responsible for this relative underperformance and proposes a new technique that eliminates it. The culprit is the wasteful manner in which the results obtained from recursive calls are indiscriminately discarded by the algorithm whenever subgames on which the algorithm is run change. Our new technique is based on firstly enhancing the algorithm to compute attractor decompositions of subgames instead of just winning strategies on them, and then on making it carefully use attractor decompositions computed in prior recursive calls to reduce the size of subgames on which further recursive calls are made. We illustrate the new technique on the classic example of the recursive McNaughton-Zielonka algorithm, but it can be applied to other symmetric attractor-based algorithms that were inspired by it, such as the quasi-polynomial versions of the McNaughton-Zielonka algorithm based on universal trees
Characterizing Positionality in Games of Infinite Duration over Infinite Graphs
No full textWe study turn-based quantitative games of infinite duration opposing twoantagonistic players and played over graphs. This model is widely accepted asproviding the adequate framework for formalizing the synthesis question forreactive systems. This important application motivates the question of strategycomplexity: which valuations (or payoff functions) admit optimal positionalstrategies (without memory)? Valuations for which both players have optimalpositional strategies have been characterized by Gimbert and Zielonka forfinite graphs and by Colcombet and Niwi\'nski for infinite graphs. However, forreactive synthesis, existence of optimal positional strategies for the opponent(which models an antagonistic environment) is irrelevant. Despite this fact,not much is known about valuations for which the protagonist admits optimalpositional strategies, regardless of the opponent. In this work, wecharacterize valuations which admit such strategies over infinite game graphs.Our characterization uses the vocabulary of universal graphs, which has alsoproved useful in understanding recent breakthrough results regarding thecomplexity of parity games. More precisely, we show that a valuation admittinguniversal graphs which are monotone and well-ordered is positional over allgame graphs, and -- more surprisingly -- that the converse is also true forvaluations admitting neutral colors. We prove the applicability and elegance ofthe framework by unifying a number of known positionality results, proving newones, and establishing closure under lexicographical products. Finally, wediscuss a class of prefix-independent positional objectives which is closedunder countable unions.Comment: 51 pages, 20 figure
Positionality in {\Sigma}_0^2 and a completeness result
No full textWe study the existence of positional strategies for the protagonist in
infinite duration games over arbitrary game graphs. We prove that
prefix-independent objectives in {\Sigma}_0^2 which are positional and admit a
(strongly) neutral letter are exactly those that are recognised by
history-deterministic monotone co-B\"uchi automata over countable ordinals.
This generalises a criterion proposed by [Kopczy\'nski, ICALP 2006] and gives
an alternative proof of closure under union for these objectives, which was
known from [Ohlmann, TheoretiCS 2023].
We then give two applications of our result. First, we prove that the
mean-payoff objective is positional over arbitrary game graphs. Second, we
establish the following completeness result: for any objective W which is
prefix-independent, admits a (weakly) neutral letter, and is positional over
finite game graphs, there is an objective W' which is equivalent to W over
finite game graphs and positional over arbitrary game graphs
Canonical Decompositions in Monadically Stable and Bounded Shrubdepth Graph Classes
No full textWe use model-theoretic tools originating from stability theory to derive a result we call the Finitary Substitute Lemma, which intuitively says the following. Suppose we work in a stable graph class , and using a first-order formula φ with parameters we are able to define, in every graph G ∈ , a relation R that satisfies some hereditary first-order assertion ψ. Then we are able to find a first-order formula φ' that has the same property, but additionally is finitary: there is finite bound k ∈ ℕ such that in every graph G ∈ , different choices of parameters give only at most k different relations R that can be defined using φ'.
We use the Finitary Substitute Lemma to derive two corollaries about the existence of certain canonical decompositions in classes of well-structured graphs.
- We prove that in the Splitter game, which characterizes nowhere dense graph classes, and in the Flipper game, which characterizes monadically stable graph classes, there is a winning strategy for Splitter, respectively Flipper, that can be defined in first-order logic from the game history. Thus, the strategy is canonical.
- We show that for any fixed graph class of bounded shrubdepth, there is an (n²)-time algorithm that given an n-vertex graph G ∈ , computes in an isomorphism-invariant way a structure H of bounded treedepth in which G can be interpreted. A corollary of this result is an (n²)-time isomorphism test and canonization algorithm for any fixed class of bounded shrubdepth
Characterising memory in infinite games
No full textThis paper is concerned with games of infinite duration played over potentially infinite graphs. Recently, Ohlmann (LICS 2022) presented a characterisation of objectives admitting optimal positional strategies, by means of universal graphs: an objective is positional if and only if it admits well-ordered monotone universal graphs. We extend Ohlmann's characterisation to encompass (finite or infinite) memory upper bounds. We prove that objectives admitting optimal strategies with -memory less than (a memory that cannot be updated when reading an -edge) are exactly those which admit well-founded monotone universal graphs whose antichains have size bounded by . We also give a characterisation of chromatic memory by means of appropriate universal structures. Our results apply to finite as well as infinite memory bounds (for instance, to objectives with finite but unbounded memory, or with countable memory strategies). We illustrate the applicability of our framework by carrying out a few case studies, we provide examples witnessing limitations of our approach, and we discuss general closure properties which follow from our results
“Enquête sur l’auteur. Entretien avec Pierre Bayard”
No full textInternational audience05/04/2019 “Enquête sur l’auteur. Entretien avec Pierre Bayard” [“Investigation into the Author. Interview with Pierre Bayard”], event for bachelor’s and master’s students in French and comparative literature, Lorraine University
Is There Market Power in the French Comte Cheese Market?
No full textAn NEIO approach is used to measure seller market power in the French Comté cheese market, characterised by government-approved supply control. The estimation is performed on quarterly data at the wholesale stage over the period 1985-2005. Three different elasticity shifters are included in the demand specification, and the supply equation accounts for the existence of the European dairy quota policy. The market power estimate is small and statistically insignificant. Monopoly is rejected, as well as weak forms of Cournot oligopoly. Results appear to be robust to the choice of functional form, and suggest little effect of the supply control scheme on consumer prices.Supply control, NEIO, protected designation of origin, Marketing,
The aesthetics of Pierre Boulez
No full textTo enable the reader to find references as quickly and easily as possible, I have grouped all references together in the bibliography in alphabetical order. Texts by the same author are distinguished first by year and second, if there are several texts from the same year, by letter. Interviews and writing collaborations (including published correspondence) involving Boulez are also ordered alphabetically. The year given at the beginning of each bibliographical entry is, in the majority of cases, the year in which the text was first published (not necessarily the year of the edition cited). For all writings written by Boulez, I have provided the original title under which the text in question was first published (usually in French). Many articles have subsequently been translated into English and therefore I have decided to provide page references for both versions. For all texts by writers other than Boulez, I have cited the version of the text I have used. Wherever possible, I have cited the existing English translations of texts originally written in French. However, on many occasions I have considered it necessary to make alterations to the published translations. This is particularly applicable to Boulez on Music Today (1971) and Orientations (1986), both of which display an often heavy-handed and rather inaccurate approach to the task of translating specific concepts employed by Boulez. In contrast. Stocktakings of an Apprenticeship (1991) has required only occasional minor amendments. All changes to the published English translations are acknowledged in the corresponding footnote. None of the material m this thesis has previously been submitted for a degree in this or any other University. The copyright of this thesis rests with the author. No quotation from it should be published without prior written consent and information from it should be acknowledged. I have received permission to exceed the word limit from the Graduate School Committee at the University of Durham
- …
