Episciences.org
Not a member yet
6707 research outputs found
Sort by
Transcribing Medieval Manuscripts for Machine Learning
No full textThis article focuses on the transcription of medieval manuscripts. Whereasproblems of transcription have long interested medievalists, few workableoptions in the era of printed editions were available besides normalisation.The automation of this process, known as handwritten text recognition (HTR),has made new kinds of digital text creation possible, but also has foregroundedthe necessity of theorising transcription in our scholarly practices. Wereflect here on different notions of transcription against the backdrop ofchanging text technologies. Moreover, drawing on our own research on medievalLatin Bibles, we present general guidelines for customizing transcriptionschemes, arguing that they must be designed with specific research questionsand scholarly end use in mind. Since we are particularly interested in thescribal contribution to the production of codices, our transcription guidelinesaim to capture abbreviations and orthographic variation between differenttextual witnesses for downstream machine learning tasks. In the final sectionof the article, we discuss a few examples of how the HTR-created transcriptionsallow us to address new questions at scale in medieval manuscripts, such astextual variance across witnesses, the prediction of a change in scribal handswithin a single manuscript as well as the profiling of individual and regionalscribal characteristics
Fully Abstract Encodings of -Calculus in HOcore through Abstract Machines
No full textWe present fully abstract encodings of the call-by-name and call-by-value-calculus into HOcore, a minimal higher-order process calculus with noname restriction. We consider several equivalences on the -calculusside -- normal-form bisimilarity, applicative bisimilarity, and contextualequivalence -- that we internalize into abstract machines in order to provefull abstraction of the encodings. We also demonstrate that this techniquescales to the -calculus, i.e., a standard extension of the-calculus with control operators
On the Metric Temporal Logic for Continuous Stochastic Processes
No full textIn this paper, we prove measurability of event for which a generalcontinuous-time stochastic process satisfies continuous-time Metric TemporalLogic (MTL) formula. Continuous-time MTL can define temporal constrains forphysical system in natural way. Then there are several researches that dealwith probability of continuous MTL semantics for stochastic processes. However,proving measurability for such events is by no means an obvious task, eventhough it is essential. The difficulty comes from the semantics of "untiloperator", which is defined by logical sum of uncountably many propositions.Given the difficulty involved in proving the measurability of such an eventusing classical measure-theoretic methods, we employ a theorem from stochasticanalysis. This theorem is utilized to prove the measurability of hitting timesfor stochastic processes, and it stands as a profound result within the theoryof capacity. Next, we provide an example that illustrates the failure ofprobability approximation when discretizing the continuous semantics of MTLformulas with respect to time. Additionally, we prove that the probability ofthe discretized semantics converges to that of the continuous semantics when weimpose restrictions on diamond operators to prevent nesting
Constrained inhomogeneous spherical equations: average-case hardness
No full textIn this paper we analyze computational properties of the Diophantine problem(and its search variant) for spherical equations (and its variants) over the class of finite metabelian groups, where and is prime. We prove that the problem of finding solutions for certainconstrained spherical equations is computationally hard on average (assumingthat some lattice approximation problem is hard in the worst case).Comment: Published in the journal of Groups, Complexity, Cryptolog
Elementary fractal geometry. 4. Automata-generated topological spaces
No full textFinite automata were used to determine multiple addresses in number systemsand to find topological properties of self-affine tiles and finite typefractals. We join these two lines of research by axiomatically definingautomata which generate topological spaces. Simple examples show the potentialof the concept. Spaces generated by automata are topologically self-similar.Two basic algorithms are outlined. The first one determines automata for all-tuples of equivalent addresses from the automaton for double addresses. Thesecond one constructs finite topological spaces which approximate the generatedspace. Finally, we discuss the realization of automata-generated spaces asself-similar sets.Comment: 33 pages, 14 figure
Approximate Distance Sensitivity Oracles in Subquadratic Space
No full textAn -edge fault-tolerant distance sensitive oracle (-DSO) with stretch is a data structure that preprocesses a given undirected,unweighted graph with vertices and edges, and a positive integer. When queried with a pair of vertices and a set of at most edges, it returns a -approximation of the --distance in . We study -DSOs that take subquadratic space. Thorup and Zwick [JACM 2005]showed that this is only possible for . We present, for anyconstant and , and any , a randomized -DSO with stretch that w.h.p. takesspace and has an query time. The time to build theoracle is \widetilde{O}(mn^{2-\frac{\alpha}{f+1}}) \cdot O(\logn/\varepsilon)^{f+1}. We also give an improved construction for graphs withdiameter at most . For any positive integer , we devise an -DSO withstretch that w.h.p. takes space and has query time, with a preprocessing time of. Chechik, Cohen, Fiat, and Kaplan [SODA 2017] devised an -DSO with stretch and preprocessing time , albeitwith a super-quadratic space requirement. We show how to reduce theirpreprocessing time to .Comment: The is the arXiv version of the eponymous paper that appeared first at STOC 2023 and then was extended to a journal version, published in TheoretiC
A Practical Algorithm with Performance Guarantees for the Art Gallery Problem
No full textGiven a closed simple polygon , we say two points see each other ifthe segment is fully contained in . The art gallery problem seeks aminimum size set of guards that sees completely. The onlycurrently correct algorithm to solve the art gallery problem exactly usesalgebraic methods and is attributed to Sharir. As the art gallery problem isER-complete, it seems unlikely to avoid algebraic methods, without additionalassumptions. In this paper, we introduce the notion of vision stability. Inorder to describe vision stability consider an enhanced guard that can see"around the corner" by an angle of or a diminished guard whose visionis by an angle of "blocked" by reflex vertices. A polygon hasvision stability if the optimal number of enhanced guards to guard is the same as the optimal number of diminished guards to guard . We willargue that most relevant polygons are vision stable. We describe a one-shotvision stable algorithm that computes an optimal guard set for visionstablepolygons using polynomial time and solving one integer program. It guaranteesto find the optimal solution for every vision stable polygon. We implemented aniterative visionstable algorithm and show its practical performance is slower,but comparable with other state of the art algorithms. Our iterative algorithmis inspired and follows closely the one-shot algorithm. It delays several stepsand only computes them when deemed necessary. Given a chord of a polygon,we denote by the number of vertices visible from . The chord-width ofa polygon is the maximum over all possible chords . The set of visionstable polygons admits an FPT algorithm when parametrized by the chord-width.Furthermore, the one-shot algorithm runs in FPT time, when parameterized by thenumber of reflex vertices.Comment: 59 pages main body, 23 figure
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds
No full textWe pose the fine-grained hardness hypothesis that the textbook algorithm forthe NFA Acceptance problem is optimal up to subpolynomial factors, even fordense NFAs and fixed alphabets. We show that this barrier appears in many variations throughout thealgorithmic literature by introducing a framework of Colored Walk problems.These yield fine-grained equivalent formulations of the NFA Acceptance problemas problems concerning detection of an --walk with a prescribed colorsequence in a given edge- or node-colored graph. For NFA Acceptance on sparseNFAs (or equivalently, Colored Walk in sparse graphs), a tight lower boundunder the Strong Exponential Time Hypothesis has been rediscovered severaltimes in recent years. We show that our hardness hypothesis, which concernsdense NFAs, has several interesting implications: - It gives a tight lower bound for Context-Free Language Reachability. Thisproves conditional optimality for the class of 2NPDA-complete problems,explaining the cubic bottleneck of interprocedural program analysis. - It gives a tight lower bound for the Word Breakproblem on strings of length and dictionaries of total size . - It implies the popular OMv hypothesis. Since the NFA acceptance problem isa static (i.e., non-dynamic) problem, this provides a static reason for thehardness of many dynamic problems. Thus, a proof of the NFA Acceptance hypothesis would resolve severalinteresting barriers. Conversely, a refutation of the NFA Acceptance hypothesismay lead the way to attacking the current barriers observed for Context-FreeLanguage Reachability, the Word Break problem and the growing list of dynamicproblems proven hard under the OMv hypothesis.Comment: 35 pages, TheoretiCS journal versio
On Generalizations of Pairwise Compatibility Graphs
No full textA graph is a pairwise compatibility graph (PCG) if there exists anedge-weighted tree and an interval , such that each leaf of the tree is avertex of the graph, and there is an edge in if and only ifthe weight of the path in the tree connecting and lies within theinterval . Originating in phylogenetics, PCGs are closely connected toimportant graph classes like leaf-powers and multi-threshold graphs, widelyapplied in bioinformatics, especially in understanding evolutionary processes.In this paper we introduce two natural generalizations of the PCG class, namely-OR-PCG and -AND-PCG, which are the classes of graphs that can beexpressed as union and intersection, respectively, of PCGs. These classescan be also described using the concepts of the covering number and theintersection dimension of a graph in relation to the PCG class. We investigatehow the classes of OR-PCG and AND-PCG are related to PCGs, -interval-PCGsand other graph classes known in the literature. In particular, we provideupper bounds on the minimum for which an arbitrary graph belongs to-interval-PCGs, -OR-PCG or -AND-PCG classes. For particular graphclasses we improve these general bounds. Moreover, we show that, for everyinteger , there exists a bipartite graph that is not in the-interval-PCGs class, proving that there is no finite for which the-interval-PCG class contains all the graphs. This answers an open questionof Ahmed and Rahman from 2017. Finally, using a Ramsey theory argument, we showthat for any , there exists graphs that are not in -AND-PCG, and graphsthat are not in -OR-PCG
Completeness Theorems for Kleene algebra with tests and top
No full textWe prove two completeness results for Kleene algebra with tests and a topelement, with respect to guarded string languages and binary relations. Whilethe equational theories of those two classes of models coincide over thesignature of Kleene algebra, this is no longer the case when we consider anadditional constant ``top'' for the full element. Indeed, the full relationsatisfies more laws than the full language, and we show that those additionallaws can all be derived from a single additional axiom. We recover that the twoequational theories coincide if we slightly generalise the notion of relationalmodel, allowing sub-algebras of relations where top is a greatest element butnot necessarily the full relation. We use models of closed languages andreductions in order to prove our completeness results, which are relative toany axiomatisation of the algebra of regular events. For one of ourconstructions, we extend the concept of finite monoid recognisability toguarded-string languages; this device makes it possible to obtain a PSpacealgorithm for the equational theory of binary relations