waashk/dblp huggingface dataset:
stable normal forms for polynomial system solving. the paper describes and analyzes a method for computing border bases of a zero-dimensional ideal i. the criterion used in the computation involves specific commutation polynomials, and leads to an algorithm and an implementation extending the ones in [b. mourrain, ph. trebuchet, generalised normal forms and polynomial system solving, in: m. kauers (ed.), proc. intern. symp. on symbolic and algebraic computation, acm press, new-york, 2005, pp. 253-260]. this general border basis algorithm weakens the monomial ordering requirement for grobner bases computations. it is currently the most general setting for representing quotient algebras, embedding into a single formalism grobner bases, macaulay bases and a new representation that does not fit into the previous categories. with this formalism, we show how the syzygies of the border basis are generated by commutation relations. we also show that our construction of normal form is stable under small perturbations of the ideal, if the number of solutions remains constant. this feature has a huge impact on practical efficiency, as illustrated by the experiments on classical benchmark polynomial systems, at the end of the paper.
a fast hermite transform. we present algorithms for fast and stable approximation of the hermite transform of a compactly supported function on the real line, attainable via an application of a fast algebraic algorithm for computing sums associated with a three-term relation. trade-offs between approximation in bandlimit (in the hermite sense), and size of the support region are addressed. numerical experiments are presented that show the feasibility and utility of our approach. generalizations to any family of orthogonal polynomials are outlined. applications to various problems in tomographic reconstruction, including the determination of protein structure, are discussed.
real algebraic numbers and polynomial systems of small degree. based on precomputed sturm-habicht sequences, discriminants and invariants, we classify, isolate with rational points, and compare the real roots of polynomials of degree up to 4. in particular, we express all isolating points as rational functions of the input polynomial coefficients. although the roots are algebraic numbers and can be expressed by radicals, such representation involves some roots of complex numbers. this is inefficient, and hard to handle in applications in geometric computing and quantifier elimination. we also define rational isolating points between the roots of the quintic. we combine these results with a simple version of rational univariate representation to isolate all common real roots of a bivariate system of rational polynomials of total degree @?2 and to compute the multiplicity of these roots. we present our software within library synaps and perform experiments and comparisons with several public-domain implementations. our package is 2-10 times faster than numerical methods and exact subdivision-based methods, including software with intrinsic filtering.
cpo semantics of timed interactive actor networks. we give a denotational framework for composing interactive components into closed or open systems and show how to adapt classical domain-theoretic approaches to open systems and to timed systems. for timed systems, prior approaches are based on temporal logics, automata theory, or metric spaces. in this paper, we base the semantics on a cpo with a prefix order, as has been done previously for untimed systems. we show that existence and uniqueness of behaviors are ensured by continuity with respect to this prefix order. existence and uniqueness of behaviors, however, do not imply that a composition of components yields a useful behavior. the unique behavior could be empty or smaller than expected. we define liveness and show that appropriately defined causality conditions ensure liveness and freedom from zeno conditions. in our formulation, causality does not require a metric and can embrace a wide variety of models of time.
the computable kernel of abstract state machines. abstract state machines (asms) were introduced as ''a computation model that is more powerful and more universal than standard computation models'', by yuri gurevich in 1985. asms gained much attention as a specification method. it is extremely flexible because any mathematical structure may serve as a state. gurevich characterized the expressive power of asms in terms of intuitively convincing postulates. the core result of this paper shows that the next-state function m of an abstract state machine m can be described on a symbolic level, notwithstanding the generality of the model: the successor state m(s) of a state s is fully specified by the equivalence ~"s induced by s on the terms over the signature of m. consequently, m(s) is computable in case ~"s is decidable. furthermore, this result implies a notion of computability for general structures, e.g. for algorithms operating on real numbers.
optimization techniques for propositional intuitionistic logic and their implementation. this paper presents some techniques which bound the proof search space in propositional intuitionistic logic. these techniques are justified by kripke semantics and are the backbone of a tableau based theorem prover (pitp) implemented in c++. pitp and some known theorem provers are compared using the formulas of iltp benchmark library. it turns out that pitp is, at the moment, the propositional prover that solves most formulas of the library.
a numerical elimination method for polynomial computations. a numerical elimination method is presented in this paper for floating-point computation in polynomial algebra. the method is designed to calculate one or more polynomials in an elimination ideal by a sequence of matrix rank/kernel computation. the method is reliable in numerical computation with verifiable stability and a sensitivity measurement. computational experiment shows that the method possesses significant advantages over classical resultant computation in numerical stability and in producing eliminant polynomials with lower degrees and fewer extraneous factors. the elimination algorithm combined with an approximate gcd finder appears to be effective in solving polynomial systems for positive dimensional solutions.
complexity of real root isolation using continued fractions. in this paper, we provide polynomial bounds on the worst case bit-complexity of two formulations of the continued fraction algorithm. in particular, for a square-free integer polynomial of degree n with coefficients of bit-length l, we show that the bit-complexity of akritas' formulation is o@?(n^8l^3), and the bit-complexity of a formulation by akritas and strzebonski is o@?(n^7l^2); here o@? indicates that we are omitting logarithmic factors. the analyses use a bound by hong to compute the floor of the smallest positive root of a polynomial, which is a crucial step in the continued fraction algorithm. we also propose a modification of the latter formulation that achieves a bit-complexity of o@?(n^5l^2).
computing sum of squares decompositions with rational coefficients. sum of squares (sos) decompositions for nonnegative polynomials are usually computed numerically, using convex optimization solvers. although the underlying floating point methods in principle allow for numerical approximations of arbitrary precision, the computed solutions will never be exact. in many applications such as geometric theorem proving, it is of interest to obtain solutions that can be exactly verified. in this paper, we present a numeric-symbolic method that exploits the efficiency of numerical techniques to obtain an approximate solution, which is then used as a starting point for the computation of an exact rational result. we show that under a strict feasibility assumption, an approximate solution of the semidefinite program is sufficient to obtain a rational decomposition, and quantify the relation between the numerical error versus the rounding tolerance needed. furthermore, we present an implementation of our method for the computer algebra system macaulay 2.
responsiveness in process calculi. a system guarantees responsive usage of a channel r if a communication along r is guaranteed to eventually take place. responsiveness is important, for instance, to ensure that any request to a service be eventually replied. we propose two distinct type systems, each of which statically guarantees responsive usage of names in well-typed pi-calculus processes. in the first system, we achieve responsiveness by combining techniques for deadlock and livelock avoidance with linearity and receptiveness. the latter is a guarantee that a name is ready to receive as soon as it is created. these conditions imply relevant limitations on the nesting of actions and on multiple use of names in processes. in the second system, we relax these requirements so as to permit certain forms of nested inputs and multiple outputs. we demonstrate the expressive power of the two systems by showing that primitive recursive functions-in the case of the first system-and cook and misra's service orchestration language orc-in the case of the second system-can be encoded into well-typed processes.
approximate gcds of polynomials and sparse sos relaxations. the problem of computing approximate gcds of several polynomials with real or complex coefficients can be formulated as computing the minimal perturbation such that the perturbed polynomials have an exact gcd of given degree. we present algorithms based on sos (sums of squares) relaxations for solving the involved polynomial or rational function optimization problems with or without constraints.
machine semantics. using simple systems with a notion of discrete deterministic evolution over time, we study discrete causality via tools from theoretical computer science and logic. we consider the set of all representations (i.e. partial descriptions) of such systems, from algebraic, domain-theoretic, and categorical viewpoints. the order theory introduced, is based in the notion of comparing high-level and low-level descriptions of the same system. this is shown to give a complete partial order where the down-closure of each element is a locale. this partial order has a very close connection to a categorical construction known as the 'particle-style' trace, via analogues of domain-theoretic equations. thus, the trace may be thought of as the computation of suprema in this partial order. as a sample application, we show how to construct algebraic models of space-bounded turing machines in these terms, and derive compositionality from the abstract properties of the trace.
verification of qualitative z constraints. we introduce an ltl-like logic with atomic formulae built over a constraint language interpreting variables in z. the constraint language includes periodicity constraints and comparison constraints of the form x=y and x
computations with quasiseparable polynomials and matrices. in this paper, we survey several recent results that highlight an interplay between a relatively new class of quasiseparable matrices and univariate polynomials. quasiseparable matrices generalize two classical matrix classes, jacobi (tridiagonal) matrices and unitary hessenberg matrices that are known to correspond to real orthogonal polynomials and szego polynomials, respectively. the latter two polynomial families arise in a wide variety of applications, and their short recurrence relations are the basis for a number of efficient algorithms. for historical reasons, algorithm development is more advanced for real orthogonal polynomials. recent variations of these algorithms tend to be valid only for the szego polynomials; they are analogues and not generalizations of the original algorithms. herein, we survey several recent results for the ''superclass'' of quasiseparable matrices, which includes both jacobi and unitary hessenberg matrices as special cases. the interplay between quasiseparable matrices and their associated polynomial sequences (which contain both real orthogonal and szego polynomials) allows one to obtain true generalizations of several algorithms. specifically, we discuss the bjorck-pereyra algorithm, the traub algorithm, certain new digital filter structures, as well as qr and divide and conquer eigenvalue algorithms.
gravitational wave signal templates, pattern recognition, and reciprocal eulerian gamma functions. the direct detection of gravitational waves (gws) is one of the most challenging problems in experimental gravitation today. it necessitates the use of highly advanced large laser interferometers such as ligo, virgo, lisa, tama 300, geo 600 and aigo. the analysis of the data from such instruments requires and combines the expertise from a multitude of scientific disciplines. the verification of a detected signal demands an effective way to distinguish the source signal from the background noise. such a study is required for an all-sky search to determine the @f and @q angles on the sky of gravitational wave sources and their frequencies. in this paper, we present analytical solutions and associated numerical approximations for the inner products employed in matched filtering a gw signal using templates. an exact closed-form expression for the inner products is rigourously derived using the special functions of mathematical physics. the inner products involve reciprocal eulerian gamma functions, which occur in the study of many diverse phenomena. the spectral noise density of the virgo gw detector is shown to be amenable to our analysis. spectral noise densities like those for ligo and geo 600, although different and in a slightly more restricted frequency band, are likewise amenable. we study numerical computation of the inner products, estimate the computational time of the solution on serial and parallel computers, and show the efficiency of the resulting algorithms. the fitting factor that indicates the goodness of fit between a signal and a template is given in closed-form and computed numerically. the numerical plots display an approximate symmetry in the template @f and @q domain.
a new algorithm for sparse interpolation of multivariate polynomials. to reconstruct a black box multivariate sparse polynomial from its floating point evaluations, the existing algorithms need to know upper bounds for both the number of terms in the polynomial and the partial degree in each of the variables. here we present a new technique, based on rutishauser's qd-algorithm, in which we overcome both drawbacks.
the identity type weak factorisation system. we show that the classifying category c(t) of a dependent type theory t with axioms for identity types admits a non-trivial weak factorisation system. we provide an explicit characterisation of the elements of both the left class and the right class of the weak factorisation system. this characterisation is applied to relate identity types and the homotopy theory of groupoids.
expanders and time-restricted branching programs. the replication number of a branching program is the minimum number r such that along every accepting computation at most r variables are tested more than once; the sets of variables re-tested along different computations may be different. for every branching program, this number lies between 0 (read-once programs) and the total number n of variables (general branching programs). the best results so far were exponential lower bounds on the size of branching programs with r=o(n/logn). we improve this to r@?@en for a constant @e>0. this also gives an alternative and simpler proof of an exponential lower bound for (1+@e)n time branching programs for a constant @e>0. we prove these lower bounds for quadratic functions of ramanujan graphs.
games to induce specified equilibria. media access protocols in wireless networks require each contending node to wait for a backoff time, chosen randomly from a fixed range, before attempting to transmit on a shared channel. however, nodes acting in their own selfish interest may not follow the protocol. in this paper, a static version of the problem is modeled as a strategic game played by non-cooperating, rational players (the nodes). the objective is to design a game which exhibits a unique, a priori mixed-strategy nash equilibrium. in the context of the media access problem, the equilibrium of the game would correspond to nodes choosing backoff times randomly from a given range of values, according to the given distribution. we consider natural variations of the problems concerning the number of actions available to the players and show that it is possible to design such a game when there are at least two players that each have the largest number of possible actions among all players. in contrast, we show that if there are exactly two players with different number of actions available to them, then it becomes impossible to design a strategic game with a unique such nash equilibrium.
playing with conway's problem. the centralizer of a language is the maximal language commuting with it. the question, raised by conway in [j.h. conway, regular algebra and finite machines, chapman hall, 1971], whether the centralizer of a rational language is always rational, recently received a lot of attention. in kunc [m. kunc, the power of commuting with finite sets of words, in: proc. of stacs 2005, in: lncs, vol. 3404, springer, 2005, pp. 569-580], a strong negative answer to this problem was given by showing that even complete co-recursively enumerable centralizers exist for finite languages. using a combinatorial game approach, we give here an incremental construction of rational languages embedding any recursive computation in their centralizers.
a new self-stabilizing maximal matching algorithm. the maximal matching problem has received considerable attention in the self-stabilizing community. previous work has given several self-stabilizing algorithms that solve the problem for both the adversarial and the fair distributed daemon, the sequential adversarial daemon, as well as the synchronous daemon. in the following we present a single self-stabilizing algorithm for this problem that unites all of these algorithms in that it has the same time complexity as the previous best algorithms for the sequential adversarial, the distributed fair, and the synchronous daemon. in addition, the algorithm improves the previous best time complexities for the distributed adversarial daemon from o(n^2) and o(@dm) to o(m) where n is the number of processes, m is the number of edges, and @d is the maximum degree in the graph.
quasiperiodic and lyndon episturmian words. recently the second two authors characterized quasiperiodic sturmian words, proving that a sturmian word is non-quasiperiodic if and only if, it is an infinite lyndon word. here we extend this study to episturmian words (a natural generalization of sturmian words) by describing all the quasiperiods of an episturmian word, which yields a characterization of quasiperiodic episturmian words in terms of their directive words. even further, we establish a complete characterization of all episturmian words that are lyndon words. our main results show that, unlike the sturmian case, there is a much wider class of episturmian words that are non-quasiperiodic, besides those that are infinite lyndon words. our key tools are morphisms and directive words, in particular normalized directive words, which we introduced in an earlier paper. also of importance is the use of return words to characterize quasiperiodic episturmian words, since such a method could be useful in other contexts.
paths and trails in edge-colored graphs. this paper deals with the existence and search for properly edge-colored paths/trails between two, not necessarily distinct, vertices s and t in an edge-colored graph from an algorithmic perspective. first we show that several versions of the s-t path/trail problem have polynomial solutions including the shortest path/trail case. we give polynomial algorithms for finding a longest properly edge-colored path/trail between s and t for a particular class of graphs and characterize edge-colored graphs without properly edge-colored closed trails. next, we prove that deciding whether there exist k pairwise vertex/edge disjoint properly edge-colored s-t paths/trails in a c-edge-colored graph g^c is np-complete even for k=2 and c=@w(n^2), where n denotes the number of vertices in g^c. moreover, we prove that these problems remain np-complete for c-edge-colored graphs containing no properly edge-colored cycles and c=@w(n). we obtain some approximation results for those maximization problems together with polynomial results for some particular classes of edge-colored graphs.
generalized lcs. the longest common subsequence (lcs) is a well studied problem, having a wide range of implementations. its motivation is in comparing strings. it has long been of interest to devise a similar measure for comparing higher dimensional objects, and more complex structures. in this paper we study the longest common substructure of two matrices and show that this problem is np-hard. we also study the longest common subforest problem for multiple trees including a constrained version, as well. we show np-hardness for k>2 unordered trees in the constrained lcs. we also give polynomial time algorithms for ordered trees and prove a lower bound for any decomposition strategy for k trees.
sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree. elimination game is a well-known algorithm that simulates gaussian elimination of matrices on graphs, and it computes a triangulation of the input graph. the number of fill edges in the computed triangulation is highly dependent on the order in which elimination game processes the vertices, and in general the produced triangulations are neither minimum nor minimal. in order to obtain a triangulation which is close to minimum, the minimum degree heuristic is widely used in practice, but until now little was known on the theoretical mechanisms involved. in this paper we show some interesting properties of elimination game; in particular that it is able to compute a partial minimal triangulation of the input graph regardless of the order in which the vertices are processed. this results in a new algorithm to compute minimal triangulations that are sandwiched between the input graph and the triangulation resulting from elimination game. one of the strengths of the new approach is that it is easily parallelizable, and thus we are able to present the first parallel algorithm to compute such sandwiched minimal triangulations. in addition, the insight that we gain through elimination game is used to partly explain the good behavior of the minimum degree algorithm. we also give a new algorithm for producing minimal triangulations that is able to use the minimum degree idea to a wider extent.
structural presburger digit vector automata. the least significant digit first decomposition of integer vectors into words of digit vectors provides a natural way for representing sets of integer vectors by automata. in this paper, the minimal automata representing presburger sets are proved structurally presburger: automata obtained by moving the initial state and replacing the accepting condition represent presburger sets.
edge-fault-tolerant hamiltonicity of pancake graphs under the conditional fault model. the conditional fault model imposes a constraint on the fault distribution. for example, the most commonly imposed constraint for edge faults is that each vertex is incident with two or more non-faulty edges. in this paper, subject to this constraint, we show that an n-dimensional pancake graph can tolerate up to 2n-7 edge faults, while retaining a fault-free hamiltonian cycle, where n>=4. previously, at most n-3 edge faults can be tolerated for the same problem, if the edge faults may occur anywhere without imposing any constraint.