Episciences.org
Not a member yet
6707 research outputs found
Sort by
Span of a Graph: Keeping the Safety Distance
No full textInspired by Lelek's idea from [Disjoint mappings and the span of spaces,Fund. Math. 55 (1964), 199 -- 214], we introduce the novel notion of the spanof graphs. Using this, we solve the problem of determining the \emph{maximalsafety distance} two players can keep at all times while traversing a graph.Moreover, their moves must be made with respect to certain move rules. For thispurpose, we introduce different variants of a span of a given connected graph.All the variants model the maximum safety distance kept by two players in agraph traversal, where the players may only move with accordance to a specificset of rules, and their goal: visit either all vertices, or all edges. For eachvariant, we show that the solution can be obtained by considering onlyconnected subgraphs of a graph product and the projections to the factors. Wecharacterise graphs in which it is impossible to keep a positive safetydistance at all moments in time. Finally, we present a polynomial timealgorithm that determines the chosen span variant of a given graph.Comment: Discrete Mathematics and Theoretical Computer Science vol. 25:1 #8 (2023
Countdown games, and simulation on (succinct) one-counter nets
No full textWe answer an open complexity question by Hofman, Lasota, Mayr, Totzke (LMCS2016) for simulation preorder on the class of succinct one-counter nets (i.e.,one-counter automata with no zero tests where counter increments and decrementsare integers written in binary); the problem was known to be PSPACE-hard and inEXPSPACE. We show that all relations between bisimulation equivalence andsimulation preorder are EXPSPACE-hard for these nets; simulation preorder isthus EXPSPACE-complete. The result is proven by a reduction from reachabilitygames whose EXPSPACE-completeness in the case of succinct one-counter nets wasshown by Hunter (RP 2015), by using other results. We also provide a directself-contained EXPSPACE-completeness proof for a special case of suchreachability games, namely for a modification of countdown games that wereshown EXPTIME-complete by Jurdzinski, Sproston, Laroussinie (LMCS 2008); in ourmodification the initial counter value is not given but is freely chosen by thefirst player. We also present an alternative proof for the upper bound byHofman et al. In particular, we give a new simplified proof of the belt theoremthat yields a simple graphic presentation of simulation preorder on(non-succinct) one-counter nets and leads to a polynomial-space algorithm(which is trivially extended to an exponential-space algorithm for succinctone-counter nets)
Machine learning and micromechanics as allies to establish composition-property correlations in cement pastes
No full textComposition-property correlations are fundamental to understand cement-based materials behavior and optimize their formulation. Modelling based on fundamental material component constitutes a reliable tool to establish these correlations with the advantage of better exploring formulation space when compared with the often adopted experimental trial-and-error approaches. In this context, Machine Learning (ML) and Micromechanics-Based (MB) methods have been concurrently used for property prediction from material composition. Here, we show that these techniques can be allies for establishing composition-property correlations. We focus on predictions of Ordinary Portland Cement pastes elastic properties, but the outlined strategy can be extended to other cement systems. Various microstructures representations are considered in MB estimates, including multiscale representations and representations with ellipsoidal inclusions. In contrast, ML predictions do not need any a priori assumption on material microstructure. Predictions using ML and MB yield similar accuracy when compared against test datasets (but ML performed much better regarding the error estimated in training datasets). Working as allies, ML can be deployed to evaluate the (lack of) knowledge over the multi-dimensional parametric domains, and micromechanics provides a theoretical background for property data curation and is a tool to make up for missing data in databases
A proof system for graph (non)-isomorphism verification
No full textIn order to apply canonical labelling of graphs and isomorphism checking ininteractive theorem provers, these checking algorithms must either bemechanically verified or their results must be verifiable by independentcheckers. We analyze a state-of-the-art algorithm for canonical labelling ofgraphs (described by McKay and Piperno) and formulate it in terms of a formalproof system. We provide an implementation that can export a proof that theobtained graph is the canonical form of a given graph. Such proofs are thenverified by our independent checker and can be used to confirm that two givengraphs are not isomorphic
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
Nietzsche and Fractal Geometry: a philosophical continuity
No full textThe purpose of this work is to highlight the epistemological proximity between Nietzsche’s philosophy of science and the underlying philosophical principles of fractal geometry, as illustrated in the main work of its creator, French mathematician Benoit Mandelbrot.This work also aims to find the end of this philosophical continuity, finding an important divergence between Nietzsche’s philosophy of risk taking and Mandelbrot’s legacy in risk management
Coalgebras for Bisimulation of Weighted Automata over Semirings
No full textWeighted automata are a generalization of nondeterministic automata thatassociate a weight drawn from a semiring with every transition and everystate. Their behaviours can be formalized either as weighted languageequivalence or weighted bisimulation. In this paper we explore the propertiesof weighted automata in the framework of coalgebras over (i) the category of semimodules over a semiring and -linear maps, and(ii) the category of sets and maps. We show that the behaviouralequivalences defined by the corresponding final coalgebras in these two casescharacterize weighted language equivalence and weighted bisimulation,respectively. These results extend earlier work by Bonchi et al. using thecategory of vector spaces and linear maps as the underlyingmodel for weighted automata with weights drawn from a field . The key stepin our work is generalizing the notions of linear relation and linearbisimulation of Boreale from vector spaces to semimodules using the concept ofthe kernel of a -linear map in the sense of universal algebra. We alsoprovide an abstract procedure for forward partition refinement for computingweighted language equivalence. Since for weighted automata defined oversemirings the problem is undecidable in general, it is guaranteed to halt onlyin special cases. We provide sufficient conditions for the termination of ourprocedure. Although the results are similar to those of Bonchi et al., many ofour proofs are new, especially those about the coalgebra in characterizing weighted language equivalence
Towards Syntactic Epistemic Logic
No full textTraditionally, Epistemic Logic represents epistemic scenarios using a singlemodel. This, however, covers only complete descriptions that specify truthvalues of all assertions. Indeed, many -- and perhaps most -- epistemicdescriptions are not complete. Syntactic Epistemic Logic, SEL, suggests viewingan epistemic situation as a set of syntactic conditions rather than as a model.This allows us to naturally capture incomplete descriptions; we discuss a casestudy in which our proposal is successful. In Epistemic Game Theory, thiscloses the conceptual and technical gap, identified by R. Aumann, between thesyntactic character of game-descriptions and semantic representations of games
On a Theorem of J. Shallit Concerning Fibonacci Partitions
No full textIn this note I prove a~claim on determinants of some special tridiagonalmatrices. Together with my result about Fibonacci partitions(arXiv:math/0307150), this claim allows one to prove one (slightlystrengthened) Shallit's result about such partitions.Comment: 5 pages. The final published versio
On fixed divisors of the values of the minimal polynomials over Z of algebraic numbers
No full textLet be a number field of degree , be its ring of integers, and (resp. ) be the set of elements of ( resp. ) which are primitive over . For any , let be the unique irreducible polynomial in , such that its leading coefficient is positive and . Let , i(K)=\lcm_{\theta\in{A_n}}i(\theta) and \hat{\imath}(K) = \lcm_{\gamma\in{K_n}}i(\gamma). For any , there exists a unique pair , where and is a positive integer such that and for any prime divisor of . In this paper, we study the possible values of when . We introduce and study a new invariant of defined using , when describes . In the last theorem of this paper, we establish a generalisation of a theorem of MacCluer