waashk/dblp huggingface dataset:
lifting results for categories of algebras. in this paper, we present results that provide an abstract setting for the construction and interpretation of categories of algebras appearing in various semantic examples including those related to scott domains and cartesian closed categories. a methodology is introduced that lifts adjoint pairs on categories with monads to categories whose objects are algebras for these monads. results are achieved by exploiting prior work on kleisli liftings and the existence of key isomorphisms. while applicable to domain theory and the semantics of partiality, the construction at work is considerably more general and is applicable to other settings as well.
cayley continuants. in 1858 cayley considered a particular kind of tridiagonal determinants (or continuants). by a direct inspection of the first cases, he conjectured an identity expressing these determinants in terms of certain other determinants considered by sylvester in 1854. then cayley proved the conjectured identity by induction but, as he wrote, he felt unsatisfied with his proof. the main aim of this paper is to give a straightforward proof of cayley's identity using the method of formal series. moreover we use this method and umbral calculus techniques to obtain several other identities.cayley continuants appear in several contexts and in particular in enumerative combinatorics. mittag-leffler polynomials, meixner polynomials of the first kind, the falling and the raising factorials are just few instances of these continuants. they can be interpreted in terms of weighted permutations. moreover, as we prove in this paper, they also appear in the context of hankel determinants generated by certain catalan-like numbers.
proof-term synthesis on dependent-type systems via explicit substitutions. typed λ-terms are used as a compact and linear representation of proofs in intuitionistic logic. this is possible since the curry-howard isomorphism relates proof-trees with typed λ-terms. the proofs-as-terms principle can be used to verify the validity of a proof by type checking the λ term extracted from the complete proof-tree. in this paper we present a proof synthesis method for dependent-type systems where typed open terms are built incrementally at the same time as proofs are done. this way, every construction step, not just the last one, may be type checked. the method is based on a suitable calculus where substitutions as well as meta-variables are first-class objects. copyright 2001 elsevier science b.v.
selection from read-only memory and sorting with minimum data movement. selecting an element of given rank, for example the median, is a fundamental problem in data organization and the computational complexity of comparison based problems. here, we consider the scenario in which the data resides in an array of read-only memory and hence the elements cannot be moved within the array. under this model, we develop efficient selection algorithms using very little extra space ( ologn extra storage cells). these include an on1+3 worst case algorithm and an onloglogn average case algorithm, both using a constant number of extra storage cells or indices. our algorithms complement the upper bounds for the time-space tradeoffs obtained by munro and paterson [9] and frederickson [4] who developed algorithms for selection in the same model when wlogn 2 extra storage cells are available. we apply our selection algorithms to obtain sorting algorithms that perform the minimum number of data moves on any given array. we also derive upper bounds for time-space tradeoffs for sorting with minimum data movement. &mdash;authors' abstract
the bandwidth minimization problem for cyclic caterpillars with hair length 1 is np-complete. in this paper, we show that the bandwidth minimization problem remains np-complete for cyclic caterpillars with hair length 1. cyclic caterpillars with hair length 1 are graphs in which the removal of all pendant vertices results in a simple cycle.
a priori optimization for the probabilistic maximum independent set problem. we first propose a formal definition for the concept of probabilistic combinatorial optimization problem (under the a priori method). next, we study the complexity of optimally solving probabilistic maximum independent set problem under several a priori optimization strategies as well as the complexity of approximating optimal solutions. for the different strategies studied, we present results about the restriction of probabilistic independent set on bipartite graphs.
functions with local state: regularity and undecidability. we study programs of a finitary ml-like language rmlf with ground-type references. rmlf permits the use of functions with locally declared variables that remain private and persist from one use of the function to the next. using game semantics we show that this leads to undecidability of program equivalence already at second order. we also examine the extent to which this feature can be captured by regular languages. this gives a decidability result for a second-order fragment rmlf- of rmlf, which comprises many examples studied in the literature.
games for complexity of second-order call-by-name programs. we use game semantics to show that program equivalence and program approximation in a second-order fragment of idealized algol are pspace-complete. the result relies on a pspace construction of deterministic finite automata representing strategies defined by second-order programs and is an improvement over the at least exponential space bounds implied by the work of other authors in which extended regular expressions were used.the approach makes it possible to study the contribution of various constructs of the language to the complexity of program equivalence and demonstrates a similarity between call-by-name game semantics and call-by-name interpreters.
exhausting strategies, joker games and full completeness for imll with unit. we present a game description of free symmetric monoidal closed categories, which can also be viewed as a fully complete model for intuitionistic multiplicative linear logic with the tensor unit. we model the unit by a distinguished one-move game called joker. special rules apply to the joker move. proofs are modelled by what we call conditionally exhausting strategies, which are deterministic and total only at positions where no joker move exists in the immediate neighbourhood, and satisfy a kind of teachability condition called p-exhaustion. we use the model to give an analysis of a counting problem in free autonomous categories which generalizes the triple unit problem.
on an interpretation of safe recursion in light affine logic. we introduce a subalgebra bc of bellantoni and cook's safe-recursion function algebra bc. functions of the subalgebra have safe arguments that are non-contractible (i.e non-duplicable). we propose a definition of safe and normal variables in light affine logic (lal), and show that bc- is the largest subalgebra that is interpretable in lal, relative to that definition. though bc- itself is not pf complete, there are extensions of it (by additional schemes for defining functions with safe arguments) that are, and are still interpretable in lal and so preserve pf closure. we focus on one such which is bc- augmented by a definition-by-cases construct and a restricted form of definition-by-recursion scheme over safe arguments. as a corollary we obtain a new proof of the pf completeness of lal.
an efficient algorithm for sequence comparison with block reversals. given two sequences x and y that are strings over some alphabet set, we consider the distance d(x,y) between them defined to be minimum number of character replacements and block (substring) reversals needed to transform x to y (or vice versa). the operations are required to be disjoint. this is the "simplest" sequence comparison problem we know of that allows natural block edit operations. block reversals arise naturally in genomic sequence comparison; they are also of interest in matching music data. we present an algorithm for exactly computing the distance d(x,y); it takes time o(|x|log2|x|), and hence, is near-linear. trivial approach takes quadratic time.
rewriting p systems: improved hierarchies. generally, for proving universality results about rewriting p systems one considers matrix grammars in the strong binary normal form. such grammars contain both matrices with rules used in the appearance checking mode and matrices without appearance checking rules. in the proofs of most of the universality theorems reported in the literature, appearance checking matrices are simulated by using only two membranes, while four membranes are used for simulating matrices without appearance checking rules. thus, a way to improve these theorems is to diminish the number of membranes used for simulating matrices without appearance checking rules. in this paper we address this problem, and give first a general improved result about simulating matrix grammars without appearance checking: three membranes are shown to suffice. this result is then used to improve several universality results from various membrane computing papers, for instance, about p systems with replicated rewriting, with leftmost rewriting, with conditional communication, as well as for hybrid p systems with finite choice.
truncated suffix trees and their application to data compression. the suffix tree is a fundamental data structure in the area of string algorithms and it has been used in many applications including data compression. in this paper we propose a data structure called the truncated suffix tree, which is a truncated version of the suffix tree. we also present two linear-time construction algorithms for truncated suffix trees and two algorithms that delete suffixes from truncated suffix trees.the truncated suffix tree is particularly a useful data structure for lz77 that compresses using a sliding window of a fixed size. our algorithms lead to two implementations of lz77 that maintain sliding windows by truncated suffix trees. we also present a technique of finding the longest match in a sliding window, which is a crucial step in lz77.
a notation for lambda terms: a generalization of environments. a notation for lambda terms is described that is useful in contexts where the intensions of these terms need to be manipulated. the scheme of de bruijn is used for eliminating variable names, thus obviating alpha conversion in comparing terms. a category of terms is provided that can encode other terms together with substitutions to be performed on them. the notion of an environment is used to realize this `delaying'' of substitutions. however, the precise environment mechanism employed here is more complex than the usual one because the ability to examine subterms embedded under abstractions has to be supported. the representation presented permits a beta contraction to be realized via an atomic step that generates a substitution and associated steps that percolate this substitution over the structure of a term. operations on terms are provided that allow for the combination and hence the simultaneous performance of substitutions. our notation eventually provides a basis for efficient realizations of beta reduction and also serves as a means for interleaving steps inherent in this operation with steps in other operations such as higher-order unification. manipulations on our terms are described through a system of rewrite rules whose correspondence to the usual notion of beta reduction is exhibited and exploited in establishing confluence and other similar properties. our notation is similar in spirit to recent proposals deriving from the categorical combinators of curien, and the relationship to these is discussed. refinements to our notation and their use in describing manipulations on lambda terms are considered in a companion paper.
on the one-sided crossing minimization in a bipartite graph with large degrees. given a bipartite graph g = (v, w, e), a 2-layered drawing consists of placing nodes in the first node set v on a straight line l1 and placing nodes in the second node set w on a parallel line l2. for a given ordering of nodes in w on l2, the one-sided crossing minimization problem asks to find an ordering of nodes in v on l1 so that the number of arc crossings is minimized. a well-known lower bound lb on the minimum number of crossings is obtained by summing up min{cuv, cvu} over all node pairs u, v ∈ v, where cuv denotes the number of crossings generated by arcs incident to u and v when u precedes v in an ordering. in this paper, we prove that there always exists a solution whose crossing number is at most (1.2964 + 12/(δ - 4))lb if the minimum degree δ of a node in v is at least 5.
a robust algorithm for bisecting a triconnected graph with two resource sets. given two disjoint subsets t1 and t2 of nodes in a 3-connected graph g = (v,e) with a node set v and an arc set e, where |t1| and |t2| are even numbers, it is known that v can be partitioned into two sets v1 and v2 such that the graphs induced by v1 and v2 are both connected and |v1 ∩ tj| = |v2 ∩ tj| = |tj|/2 holds for each j = 1.2. an o(|v|2 log |v|) time and o(|v| + |e|) space algorithm lbr finding such a bipartition has been proposed based on a geometric argument, where g is embedded m the plane r2 and the node set is bipartitioned by a ham-sandwich cut on the embedding. a naive implementation of the algorithm, however, requires high precision real arithmetic to distinguish two close points in a large set of points on r2. in this paper, we propose an o(|v|2) time and space algorithm to the problem. the new algorithm, which remains to be based on the geometric embedding, can construct a solution purely combinatorially in the sense that it does not require computing actual embedded points in r2 and thereby no longer needs to store any real number for embedded points. although the new algorithm seems to need more space complexity, it can be implemented only with |v| linked lists such that each element stores an integer in [1,|v|].
a graph-theoretic characterization theorem for multiplicative fragment of non-commutative linear logic. it is well known that every proof net of a non-commutative version of mll (multiplicative fragment of commutative linear logic) can be drawn as a plane danos-regnier graph (drawing) satisfying the switching condition of danos-regnier [3]. in this paper, we study the reverse direction; we introduce a system mncll which is logically equivalent to the multiplicative fragment of cyclic linear logic introduced by yetter [9], and show that any plane danos-regnier graph drawing with one terminal edge satisfying the switching condition represents a unique non-commutative proof net (i.e., a proof net of mncll). in the course of proving this, we also give the characterization of the non-commutative proof nets by means of the notion of strong planarity, as well as the notion of a certain long-trip condition, called the stack-condition, of a danos-regnier graph, the latter of which is related to abrusci's balanced long-trip condition [2].
static analysis based on formal models and incremental computation in go programming. computer-go programs have high computational costs for static analysis, even though most intersections of the board remain unchanged by one move. therefore, incremental computation as well as theoretical models are essential features for static analysis. this paper describes some formal models for static analysis, and explores how incremental computation is applied to the static analysis in go programs. the static analysis in this paper includes (1) recognizing blocks and groups of stones and evaluating their properties, (2) determining the life and death of a group by numerical features, (3) finding the numbers of regions enclosed by the groups based on euler's formula, and (4) analysing capturing races (semeai) and sekis based on an abstract description called the semeai graph. several operations on the sets of intersections on the board are used for defining the notions on go boards as well as for describing the analysis methods.
a time-optimal solution for the path cover problem on cographs. we show that the notoriously difficult problem of finding and reporting the smallest number of vertex-disjoint paths that cover the vertices of a graph can be solved time- and work-optimally for cographs. our result implies that for this class of graphs the task of finding a hamiltonian path can be solved time- and work-optimally in parallel.it was open for more than 10 years to find a time- and work-optimal parallel solution for this important problem. our contribution is to offer an optimal solution to this important problem. we begin by showing that any algorithm that solves an instance of size n of the problem must take ω(logn) time on the crew, even if an infinite number of processors are available. we then go on to show that this time lower bound is tight by devising an erew algorithm that, given an n-vertex cograph g represented by its cotree, finds and reports all the paths in a minimum path cover in o(logn) time using n/logn processors.
on the expected time for herman's probabilistic self-stabilizing algorithm. in this article we investigate the expected time for herman's probabilistic self-stabilizing algorithm in distributed systems: suppose that the number of identical processes in a unidirectional ring, say n, is odd and n ≥ 3. if the initial configuration of the ring is not "legitimate", that is, the number of tokens differs from one, then execution of the algorithm made up of synchronous probabilistic procedures with a local parameter 0 < r < 1 results in convergence to a legitimate configuration with a unique token (herman's algorithm). we then show that the expected time of the convergence is less than ((π2-8)/8r(1-r))n2. note that if r = ½ then it is bounded by 0.936n2. moreover, there exists a configuration whose expected time is θ(n2). the method of the proof is based on the analysis of coalescing random walks.
a logic for secure memory access of abstract state machines. we extend the logic for abstract state machines by a read predicate that allows to make precise statements about the accesses of locations of an asm. the logic can be used to prove security properties of asms like that the machine does not read locations containing critical information or that all accesses of the machine to the abstract memory are permitted. the new read predicate is also useful for proving refinements of parallel asms to sequential c-like programs. the logic is complete for hierarchical asms and still sound for turbo asms. it is integrated in the asmkey theorem prover.
an efficient k nearest neighbors searching algorithm for a query line. we present an algorithm for finding k nearest neighbors of a given query line among a set of n points distributed arbitrarily on a two-dimensional plane. our algorithm requires o(n2) time and o(n2/log n) space to preprocess the given set of points, and it answers the query for a given line in o(k + log n) time, where k may also be an input at the query time. almost a similar technique works for finding k farthest neighbors of a query line, keeping the time and space complexities invariant. we also show that if k is known at the time of preprocessing, the time and space complexities for the preprocessing can be reduced keeping the query times unchanged.
a framework for security analysis of mobile wireless networks. we present a framework for specification and security analysis of communication protocols for mobile wireless networks. this setting introduces new challenges which are not being addressed by classical protocol analysis techniques. the main complication stems from the fact that the actions of intermediate nodes and their connectivity can no longer be abstracted into a single unstructured adversarial environment as they form an inherent part of the system's security. in order to model this scenario faithfully, we present a broadcast calculus which makes a clear distinction between the protocol processes and the network's connectivity graph, which may change independently from protocol actions. we identify a property characterising an important aspect of security in this setting and express it using behavioural equivalences of the calculus. we complement this approach with a control flow analysis which enables us to automatically check this property on a given network and attacker specification.
finding the most vital node of a shortest path. in an undirected, 2-node connected graph g=(v,e) with positive real edge lengths, the distance between any two nodes r and s is the length of a shortest path between r and s in g. the removal of a node and its incident edges from g may increase the distance from r to s. a most vital node of a given shortest path from r to s is a node (other than r and s) whose removal from g results in the largest increase of the distance from r to s. in the past, the problem of finding a most vital node of a given shortest path has been studied because of its implications in network management, where it is important to know in advance which component failure will affect network efficiency the most. in this paper, we show that this problem can be solved in o(m+n log n) time and o(m) space, where m and n denote the number of edges and the number of nodes in g.
spiking neurons and the induction of finite state machines. we discuss in this short survey article some current mathematical models from neurophysiology for the computational units of biological neural systems: neurons and synapses. these models are contrasted with the computational units of common artificial neural network models, which reflect the state of knowledge in neurophysiology 50 years ago. we discuss the problem of carrying out computations in circuits consisting of biologically realistic computational units, focusing on the biologically particularly relevant case of computations on time series. finite state machines are frequently used in computer science as models for computations on time series. one may argue that these models provide a reasonable common conceptual basis for analyzing computations in computers and biological neural systems, although the emphasis in biological neural systems is shifted more towards asynchronous computation on analog time series. in the second half of this article some new computer experiments and theoretical results are discussed, which address the question whether a biological neural system can, in principle, learn to behave like a given simple finite state machine.
ga performance distributions and randomly generated binary constraint satisfaction problems. we investigate the variable performance of a genetic algorithm (ga) on randomly generated binary constraint satisfaction problem instances which occur near the phase transition from soluble to non-soluble. we first carry out a conventional landscape analysis and observe, next to a number of common features related to the interaction structure, important differences between the instances, such as the number of solutions, the quality of the paths to the solutions, and the lengths and extent of the neutral paths for mutation. we then split the dynamics of the ga into two phases: the ascent towards the high fitness region, and from this high fitness region to a solution. to gain further information about the ga's behavior in the first phase, we construct two models based on the much simpler fully separable functions, and try to match instances which show a similar performance distribution. although far from exact, this technique of comparing with analog search problems gives a hint about the landscape elements that are responsible for the ga's slow ascent.
soundness of data refinement for a higher-order imperative language. using a set-theoretic model of predicate transformers and ordered data types, we give a semantics for an oberon-like higher-order imperative language with record subtyping and procedure-type variables and parameters. data refinement is shown to be sound for this language: it implies algorithmic refinement when suitably localized. all constructs are shown to preserve simulation, so data refinement can be carried out piecewise.