Episciences.org
Not a member yet
6707 research outputs found
Sort by
Absent Subsequences in Words
No full textAn absent factor of a string is a string which does not occur as acontiguous substring (a.k.a. factor) inside . We extend this well-studiednotion and define absent subsequences: a string is an absent subsequence ofa string if does not occur as subsequence (a.k.a. scattered factor)inside . Of particular interest to us are minimal absent subsequences, i.e.,absent subsequences whose every subsequence is not absent, and shortest absentsubsequences, i.e., absent subsequences of minimal length. We show a series ofcombinatorial and algorithmic results regarding these two notions. Forinstance: we give combinatorial characterisations of the sets of minimal and,respectively, shortest absent subsequences in a word, as well as compactrepresentations of these sets; we show how we can test efficiently if a stringis a shortest or minimal absent subsequence in a word, and we give efficientalgorithms computing the lexicographically smallest absent subsequence of eachkind; also, we show how a data structure for answering shortest absentsubsequence-queries for the factors of a given string can be efficientlycomputed.Comment: An extended abstract appeared in the proceedings of the 15th International Conference on Reachability Problems RP202
Bears with Hats and Independence Polynomials
No full textConsider the following hat guessing game. A bear sits on each vertex of agraph , and a demon puts on each bear a hat colored by one of colors.Each bear sees only the hat colors of his neighbors. Based on this informationonly, each bear has to guess colors and he guesses correctly if his hatcolor is included in his guesses. The bears win if at least one bear guessescorrectly for any hat arrangement. We introduce a new parameter - fractional hat chromatic number ,arising from the hat guessing game. The parameter is related to thehat chromatic number which has been studied before. We present a surprisingconnection between the hat guessing game and the independence polynomial ofgraphs. This connection allows us to compute the fractional hat chromaticnumber of chordal graphs in polynomial time, to bound fractional hat chromaticnumber by a function of maximum degree of , and to compute the exact valueof of cliques, paths, and cycles
Contribution to the recent history of archaeology by using some digital humanities methods and techniques applied to field recording documents of an archaeological site excavated in 1970s
No full textThis article presents the results of an archaeological archive research. Field recording documents from the Rivaux site in France, which was excavated from the 1970s to the 1990s, were exploited. After digitising a set of field notebook pages, the author developed an application, called Archeotext, which allows transcribing and georeferencing these documents. Some of the results obtained show new ways of exploiting this type of archive by using certain methods and techniques of the digital humanities
An axiomatization for the universal theory of the Heisenberg group
No full textThe Heisenberg group, here denoted , is the group of all upperunitriangular matrices with entries in the ring of integers. A.G.Myasnikov posed the question of whether or not the universal theory of , inthe language of , is axiomatized, when the models are restricted to-groups, by the quasi-identities true in together with the assertionthat the centralizers of noncentral elements be abelian. Based on earlierpublished partial results we here give a complete proof of a slightly strongerresult.Comment: 13 pages. Published in journal of Groups, Complexity, Cryptolog
A Hofmann-Mislove theorem for -well-filtered spaces
No full textThe Hofmann-Mislove theorem states that in a sober space, the nonempty Scottopen filters of its open set lattice correspond bijectively to its compactssaturated sets. In this paper, the concept of -well-filtered spaces isintroduced. We show that a retract of a -well-filtered space is-well-filtered and a locally Lindel\"{o}f and -well-filtered -space iscountably sober. In particular, we obtain a Hofmann-Mislove theorem for-well-filtered spaces
A regularity criterion in multiplier spaces to Navier-Stokes equations via the gradient of one velocity component
No full textIn this paper, we study regularity of weak solutions to the incompressibleNavier-Stokes equations in . The main goal is toestablish the regularity criterion via the gradient of one velocity componentin multiplier spaces.Comment: 9 pages. arXiv admin note: text overlap with arXiv:2005.1401
Reachability In Simple Neural Networks
No full textWe investigate the complexity of the reachability problem for (deep) neuralnetworks: does it compute valid output given some valid input? It was recentlyclaimed that the problem is NP-complete for general neural networks andspecifications over the input/output dimension given by conjunctions of linearinequalities. We recapitulate the proof and repair some flaws in the originalupper and lower bound proofs. Motivated by the general result, we show thatNP-hardness already holds for restricted classes of simple specifications andneural networks. Allowing for a single hidden layer and an output dimension ofone as well as neural networks with just one negative, zero and one positiveweight or bias is sufficient to ensure NP-hardness. Additionally, we give athorough discussion and outlook of possible extensions for this direction ofresearch on neural network verification.Comment: arXiv admin note: substantial text overlap with arXiv:2108.1317
Graded Differential Categories and Graded Differential Linear Logic
No full textIn Linear Logic (), the exponential modality brings forth adistinction between non-linear proofs and linear proofs, where linear meansusing an argument exactly once. Differential Linear Logic () isan extension of Linear Logic which includes additional rules for whichencode differentiation and the ability of linearizing proofs. On the otherhand, Graded Linear Logic () is a variation of Linear Logic insuch a way that is now indexed over a semiring . This -grading allowsfor non-linear proofs of degree , such that the linear proofs are ofdegree . There has been recent interest in combining these twovariations of together and developing Graded Differential LinearLogic (). In this paper we present a sequent calculus for, as well as introduce its categorical semantics, which we callgraded differential categories, using both coderelictions and derivingtransformations. We prove that symmetric powers always give graded differentialcategories, and provide other examples of graded differential categories. Wealso discuss graded versions of (monoidal) coalgebra modalities, additivebialgebra modalities, and the Seely isomorphisms, as well as theirimplementations in the sequent calculus of .Comment: In the proceedings of MFPS2023. Removed appendix from previous version to respect page limit. Minor corrections: the previous statement of one of our examples was incorrect, we thank Flavien Breuvart for explaining this to us. This has now been fixed. The rest of the paper remains unchange
Homomorphically Full Oriented Graphs
No full textHomomorphically full graphs are those for which every homomorphic image isisomorphic to a subgraph. We extend the definition of homomorphically full tooriented graphs in two different ways. For the first of these, we show thathomomorphically full oriented graphs arise as quasi-transitive orientations ofhomomorphically full graphs. This in turn yields an efficient recognition andconstruction algorithms for these homomorphically full oriented graphs. For thesecond one, we show that the related recognition problem is GI-hard, and thatthe problem of deciding if a graph admits a homomorphically full orientation isNP-complete. In doing so we show the problem of deciding if two given orientedcliques are isomorphic is GI-complete
Continuous Positional Payoffs
No full textWhat payoffs are positionally determined for deterministic two-playerantagonistic games on finite directed graphs? In this paper we study thisquestion for payoffs that are continuous. The main reason why continuouspositionally determined payoffs are interesting is that they include themulti-discounted payoffs. We show that for continuous payoffs, positional determinacy is equivalent toa simple property called prefix-monotonicity. We provide three proofs of it,using three major techniques of establishing positional determinacy --inductive technique, fixed point technique and strategy improvement technique.A combination of these approaches provides us with better understanding of thestructure of continuous positionally determined payoffs as well as with somealgorithmic results