Episciences.org
Not a member yet
6707 research outputs found
Sort by
Decision Questions for Probabilistic Automata on Small Alphabets
No full textWe study the emptiness and -reachability problems for unary andbinary Probabilistic Finite Automata (PFA) and characterise the complexity ofthese problems in terms of the degree of ambiguity of the automaton and thesize of its alphabet. Our main result is that emptiness and-reachability are solvable in EXPTIME for polynomially ambiguous unaryPFA and if, in addition, the transition matrix is binary, we show they are inNP. In contrast to the Skolem-hardness of the -reachability andemptiness problems for exponentially ambiguous unary PFA, we show that theseproblems are NP-hard even for finitely ambiguous unary PFA. For binarypolynomially ambiguous PFA with fixed and commuting transition matrices, weprove NP-hardness of the -reachability (dimension 9), nonstrictemptiness (dimension 37) and strict emptiness (dimension 40) problems
Facets of Random Symmetric Edge Polytopes, Degree Sequences, and Clustering
No full textSymmetric edge polytopes are lattice polytopes associated with finite simplegraphs that are of interest in both theory and applications. We investigate thefacet structure of symmetric edge polytopes for various models of randomgraphs. For an Erd\H{o}s-Renyi random graph, we identify a thresholdprobability at which with high probability the symmetric edge polytope sharesmany facet-supporting hyperplanes with that of a complete graph. We alsoinvestigate the relationship between the average local clustering, also knownas the Watts-Strogatz clustering coefficient, and the number of facets forgraphs with either a fixed number of edges or a fixed degree sequence. We usewell-known Markov Chain Monte Carlo sampling methods to generate empiricalevidence that for a fixed degree sequence, higher average local clustering in aconnected graph corresponds to higher facet numbers in the associated symmetricedge polytope
A characterization of rich c-partite (c > 7) tournaments without (c + 2)-cycles
No full textLet c be an integer. A c-partite tournament is an orientation of a completec-partite graph. A c-partite tournament is rich if it is strong, and eachpartite set has at least two vertices. In 1996, Guo and Volkmann characterizedthe structure of all rich c-partite tournaments without (c + 1)-cycles, whichsolved a problem by Bondy. They also put forward a problem that what thestructure of rich c-partite tournaments without (c + k)-cycles for some k>1 is.In this paper, we answer the question of Guo and Volkmann for k = 2
Toposes of Topological Monoid Actions
No full textWe demonstrate that categories of continuous actions of topological monoidson discrete spaces are Grothendieck toposes. We exhibit properties of thesetoposes, giving a solution to the corresponding Morita-equivalence problem. Wecharacterize these toposes in terms of their canonical points. We identifynatural classes of representatives with good topological properties, `powdermonoids' and then `complete monoids', for the Morita-equivalence classes oftopological monoids. Finally, we show that the construction of these toposescan be made (2-)functorial by considering geometric morphisms induced bycontinuous semigroup homomorphisms.Comment: 58 pages. Final version appearing in Compositionality. Project under the INdAM Doctoral Programme in Mathematics and/or Applications Cofunded by Marie Sklodowska-Curie Actions, INdAM-DP-COFUND-2015, grant number 71348
Rook placements in and and associated coadjoint orbits
No full textLet be a maximal nilpotent subalgebra of a simple complex Liealgebra with root system . A subset of the set of positiveroots is called a rook placement if it consists of roots with pairwisenon-positive scalar products. To each rook placement and each map from to the set of nonzero complex numbers one cannaturally assign the coadjoint orbit in the dual space. By definition, is the orbit of ,where is the sum of root covectors multiplied by, . (In fact, almost all coadjoint orbits studied atthe moment have such a form for certain and .) It follows from theresults of Andr\`e that if and are distinct maps from to then and do notcoincide for classical root systems . We prove that this is true if is of type , or if is of type and is orthogonal.Comment: 16 pages, 4 figure
Fast Symbolic Algorithms for Omega-Regular Games under Strong Transition Fairness
No full textWe consider fixpoint algorithms for two-player games on graphs with-regular winning conditions, where the environment is constrained by astrong transition fairness assumption. Strong transition fairness is a widelyoccurring special case of strong fairness, which requires that any execution isstrongly fair with respect to a specified set of live edges: whenever thesource vertex of a live edge is visited infinitely often along a play, the edgeitself is traversed infinitely often along the play as well. We show that,surprisingly, strong transition fairness retains the algorithmiccharacteristics of the fixpoint algorithms for -regular games -- thenew algorithms have the same alternation depth as the classical algorithms butinvoke a new type of predecessor operator. For Rabin games with pairs, thecomplexity of the new algorithm is symbolic steps, which isindependent of the number of live edges in the strong transition fairnessassumption. Further, we show that GR(1) specifications with strong transitionfairness assumptions can be solved with a 3-nested fixpoint algorithm, same asthe usual algorithm. In contrast, strong fairness necessarily requiresincreasing the alternation depth depending on the number of fairnessassumptions. We get symbolic algorithms for (generalized) Rabin, parity andGR(1) objectives under strong transition fairness assumptions as well as adirect symbolic algorithm for qualitative winning in stochastic-regular games that runs in symbolic steps, improvingthe state of the art. Finally, we have implemented a BDD-based synthesis enginebased on our algorithm. We show on a set of synthetic and real benchmarks thatour algorithm is scalable, parallelizable, and outperforms previous algorithmsby orders of magnitude
Homogeneous non-split superstrings of odd dimension 4
No full textLet be the holomorphic line bundle of degree on the projective line. Here, the tuples for which there does not exists homogeneous non-split supermanifolds associated with the vector bundle are classified. \\For many types of the remaining tuples, there are listed cocycles that determine homogeneous non-split supermanifolds. \\Proofs follow the lines indicated in the paper Bunegina V.A., Onishchik A.L., Homogeneous supermanifolds associated with the complex projective line.neous supermanifolds associated with the complex projective line. J. Math. Sci. V. 82 (1996)3503--3527
Exactly Hittable Interval Graphs
No full textGiven a set system , where is a set of elements and is a set of subsets of, an exact hitting set is a subset of such that each subset in contains exactly one element in. We refer to a set system as exactly hittable if it has an exacthitting set. In this paper, we study interval graphs which have intersectionmodels that are exactly hittable. We refer to these interval graphs as exactlyhittable interval graphs (EHIG). We present a forbidden structurecharacterization for EHIG. We also show that the class of proper intervalgraphs is a strict subclass of EHIG. Finally, we give an algorithm that runs inpolynomial time to recognize graphs belonging to the class of EHIG.Comment: 22 pages. arXiv admin note: text overlap with arXiv:1707.0507
HistText: An Application for leveraging large-scale historical textbases
No full textThis paper introduces HistText, a pioneering tool devised to facilitate large-scale data mining in historical documents, specifically targeting Chinese sources. Developed in response to the challenges posed by the massive Modern China Textual Database, HistText emerges as a solution to efficiently extract and visualize valuable insights from billions of words spread across millions of documents. With a user-friendly interface, advanced text analysis techniques, and powerful data visualization capabilities, HistText offers a robust platform for digital humanities research. This paper explores the rationale behind HistText, underscores its key features, and provides a comprehensive guide for its effective utilization, thus highlighting its potential to substantially enhance the realm of computational humanities
The exponential logic of sequentialization
No full textLinear logic has provided new perspectives on proof-theory, denotationalsemantics and the study of programming languages. One of its main successes areproof-nets, canonical representations of proofs that lie at the intersectionbetween logic and graph theory. In the case of the minimalist proof-system ofmultiplicative linear logic without units (MLL), these two aspects arecompletely fused: proof-nets for this system are graphs satisfying acorrectness criterion that can be fully expressed in the language of graphs. For more expressive logical systems (containing logical constants,quantifiers and exponential modalities), this is not completely the case. Thepurely graphical approach of proof-nets deprives them of any sequentialstructure that is crucial to represent the order in which arguments arepresented, which is necessary for these extensions. Rebuilding this order ofpresentation - sequentializing the graph - is thus a requirement for a graph tobe logical. Presentations and study of the artifacts ensuring thatsequentialization can be done, such as boxes or jumps, are an integral part ofresearches on linear logic. Jumps, extensively studied by Faggian and di Giamberardino, can expressintermediate degrees of sequentialization between a sequent calculus proof anda fully desequentialized proof-net. We propose to analyze the logical strengthof jumps by internalizing them in an extention of MLL where axioms on aspecific formula, the jumping formula, introduce constrains on the possiblesequentializations. The jumping formula needs to be treated non-linearly, whichwe do either axiomatically, or by embedding it in a very controlled fragment ofmultiplicative-exponential linear logic, uncovering the exponential logic ofsequentialization.Comment: 17 pages, submitted to MFPS 202