Episciences.org
Not a member yet
6707 research outputs found
Sort by
Playing Safe, Ten Years Later
No full textWe consider two-player games over graphs and give tight bounds on the memorysize of strategies ensuring safety objectives. More specifically, we show thatthe minimal number of memory states of a strategy ensuring a safety objectiveis given by the size of the maximal antichain of left quotients with respect tolanguage inclusion. This result holds for all safety objectives without anyregularity assumptions. We give several applications of this general principle.In particular, we characterize the exact memory requirements for the opponentin generalized reachability games, and we prove the existence of positionalstrategies in games with counters
Discovering Process Models With Long-Term Dependencies While Providing Guarantees and Filtering Infrequent Behavior Patterns
No full textIn process discovery, the goal is to find, for a given event log, the modeldescribing the underlying process. While process models can be represented in avariety of ways, Petri nets form a theoretically well-explored descriptionlanguage and are therefore often used. In this paper, we extend the eST-Minerprocess discovery algorithm. The eST-Miner computes a set of Petri net placeswhich are considered to be fitting with respect to a certain fraction of thebehavior described by the given event log as indicated by a given noisethreshold. It evaluates all possible candidate places using token-based replay.The set of replayable traces is determined for each place in isolation, i.e.,these sets do not need to be consistent. This allows the algorithm to abstractfrom infrequent behavioral patterns occurring only in some traces. However,when combining places into a Petri net by connecting them to the correspondinguniquely labeled transitions, the resulting net can replay exactly those tracesfrom the event log that are allowed by the combination of all inserted places.Thus, inserting places one-by-one without considering their combined effect mayresult in deadlocks and low fitness of the Petri net. In this paper, we exploreadaptions of the eST-Miner, that aim to select a subset of places such that theresulting Petri net guarantees a definable minimal fitness while maintaininghigh precision with respect to the input event log. Furthermore, current placeevaluation techniques tend to block the execution of infrequent activitylabels. Thus, a refined place fitness metric is introduced and thoroughlyinvestigated. In our experiments we use real and artificial event logs toevaluate and compare the impact of the various place selection strategies andplace fitness evaluation metrics on the returned Petri net.Comment: Fundamenta Informaticae, Petri Nets Special Issue 202
Linear Programs with Conjunctive Database Queries
No full textIn this paper, we study the problem of optimizing a linear program whosevariables are the answers to a conjunctive query. For this we propose thelanguage LP(CQ) for specifying linear programs whose constraints and objectivefunctions depend on the answer sets of conjunctive queries. We contribute anefficient algorithm for solving programs in a fragment of LP(CQ). The naturalapproach constructs a linear program having as many variables as there areelements in the answer set of the queries. Our approach constructs a linearprogram having the same optimal value but fewer variables. This is done byexploiting the structure of the conjunctive queries using generalized hypertreedecompositions of small width to factorize elements of the answer set together.We illustrate the various applications of LP(CQ) programs on three examples:optimizing deliveries of resources, minimizing noise for differential privacy,and computing the s-measure of patterns in graphs as needed for data mining
Proofs as stateful programs: A first-order logic with abstract Hoare triples, and an interpretation into an imperative language
No full textWe introduce an extension of first-order logic that comes equipped withadditional predicates for reasoning about an abstract state. Sequents in thelogic comprise a main formula together with pre- and postconditions in thestyle of Hoare logic, and the axioms and rules of the logic ensure that theassertions about the state compose in the correct way. The main result of thepaper is a realizability interpretation of our logic that extracts programsinto a mixed functional/imperative language. All programs expressible in thislanguage act on the state in a sequential manner, and we make this intuitionprecise by interpreting them in a semantic metatheory using the state monad.Our basic framework is very general, and our intention is that it can beinstantiated and extended in a variety of different ways. We outline in detailone such extension: A monadic version of Heyting arithmetic with a wellfoundedwhile rule, and conclude by outlining several other directions for future work
Étude archéologique diachronique de la carrière de l’Estel sud: La Bégude Reymond, Route du Pont du Gard, à Vers-Pont du Gard (30)
No full textLa carrière de l’Estel sud à Vers-Pont du Gard est située sur la rive gauche d’un méandre concave du Gardon, à 500 mètres environ à l’aval du Pont du Gard, ouvrage majeur de l’aqueduc de Nîmes construit au milieu du Ier siècle de notre ère. La carrière est reconnue pour avoir livré les blocs de grand appareil que l’on observe dans la construction du pont aqueduc. Située dans le lit majeur de la rivière, elle est abandonnée à la fin du chantier antique et le site est alors comblé et nivelé par les dépôts de crues. L’exploitation de la pierre de taille n’est rouverte qu’au XVIIIe siècle, lors de la construction du pont routier accolé à l’aval du premier étage d’arches du pont antique. Les stratégies de prévention et protection contre le risque fluvial adoptées dès l’Antiquité en raison de l’identité environnementale de la carrière, avaient préservé les traces diachroniques de l’évolution du paysage et de l’exploitation de la pierre de taille depuis l’Antiquité. Dans ce cadre, la fouille archéologique de la carrière a apporté une large vision des savoirs et des savoir-faire des carriers et des constructeurs depuis cette même période
On Robustness for the Skolem, Positivity and Ultimate Positivity Problems
No full textThe Skolem problem is a long-standing open problem in linear dynamicalsystems: can a linear recurrence sequence (LRS) ever reach 0 from a giveninitial configuration? Similarly, the positivity problem asks whether the LRSstays positive from an initial configuration. Deciding Skolem (or positivity)has been open for half a century: the best known decidability results are forLRS with special properties (e.g., low order recurrences). But these problemsare easier for "uninitialized" variants, where the initial configuration is notfixed but can vary arbitrarily: checking if there is an initial configurationfrom which the LRS stays positive can be decided in polynomial time (Tiwari in2004, Braverman in 2006). In this paper, we consider problems that lie betweenthe initialized and uninitialized variants. More precisely, we ask if 0 (resp.negative numbers) can be avoided from every initial configuration in aneighborhood of a given initial configuration. This can be considered as arobust variant of the Skolem (resp. positivity) problem. We show that theseproblems lie at the frontier of decidability: if the neighbourhood is given aspart of the input, then robust Skolem and robust positivity are Diophantinehard, i.e., solving either would entail major breakthroughs in Diophantineapproximations, as happens for (non-robust) positivity. However, if one askswhether such a neighbourhood exists, then the problems turn out to be decidablewith PSPACE complexity. Our techniques also allow us to tackle robustness forultimate positivity, which asks whether there is a bound on the number of stepsafter which the LRS remains positive. There are two variants depending onwhether we ask for a "uniform" bound on this number of steps. For thenon-uniform variant, when the neighbourhood is open, the problem turns out tobe tractable, even when the neighbourhood is given as input
Closeness and Residual Closeness of Harary Graphs
No full textAnalysis of a network in terms of vulnerability is one of the mostsignificant problems. Graph theory serves as a valuable tool for solvingcomplex network problems, and there exist numerous graph-theoretic parametersto analyze the system's stability. Among these parameters, the closenessparameter stands out as one of the most commonly used vulnerability metrics.Its definition has evolved to enhance the ease of formulation and applicabilityto disconnected structures. Furthermore, based on the closeness parameter,vertex residual closeness, which is a newer and more sensitive parametercompared to other existing parameters, has been introduced as a new graphvulnerability index by Dangalchev. In this study, the outcomes of the closenessand vertex residual closeness parameters in Harary Graphs have been examined.Harary Graphs are well-known constructs that are distinguished by having vertices that are -connected with the least possible number of edges.Comment: 23 pages preprin
Foundations of probability-raising causality in Markov decision processes
No full textThis work introduces a novel cause-effect relation in Markov decisionprocesses using the probability-raising principle. Initially, sets of states ascauses and effects are considered, which is subsequently extended to regularpath properties as effects and then as causes. The paper lays the mathematicalfoundations and analyzes the algorithmic properties of these cause-effectrelations. This includes algorithms for checking cause conditions given aneffect and deciding the existence of probability-raising causes. As thedefinition allows for sub-optimal coverage properties, quality measures forcauses inspired by concepts of statistical analysis are studied. These includerecall, coverage ratio and f-score. The computational complexity for findingoptimal causes with respect to these measures is analyzed.Comment: arXiv admin note: substantial text overlap with arXiv:2201.0876
Quand les schémas logistiques mondiaux questionnent le rôle de l’État-stratège. Retour sur France Logistique 2025
No full textThe positioning of States in global value chains has become a highly important competitive factor. Logistics and transportation constitute therefore an important lever for strategical action by states. In light of these issues, this article intends to report on the national logistics strategy, “France Logistique 2025”, whose roadmap was presented in March 2016. Beyond the deconstruction of its content and process, the objective here is to enrich the reflection about the strategist-state role and the missions in the definition and implementation of a policy, which cuts naturally across activity sectors and territories.Le positionnement des États au sein des global value chains est devenu un enjeu majeur de compétitivité. La logistique et le transport constituent, dans ce cadre, de véritables leviers d’action stratégique des États. Au regard de ces enjeux, l’article propose de dresser un bilan de la stratégie logistique nationale, France Logistique 2025, dont la feuille de route a été présentée en mars 2016. Au-delà d’en déconstruire le contenu et le processus, l’objectif est ici d’enrichir aussi la réflexion sur le rôle et les missions de l’État-stratège dans la définition et le déploiement d’une politique par nature transversale aux secteurs d’activité et aux territoires
A -first Whitehead Lemma for Jordan algebras
No full textWe compute -derivations of simple Jordan algebras with values inirreducible bimodules. They turn out to be either ordinary derivations (), or scalar multiples of the identity map (). This canbe considered as a generalization of the "First Whitehead Lemma" for Jordanalgebras which claims that all such ordinary derivations are inner. The proofamounts to simple calculations in matrix algebras, or, in the case of Jordanalgebras of a symmetric bilinear form, to more elaborated calculations inClifford algebras.Comment: 13 pages; v3: final version formatted for the publicatio