Search

In this paper we consider the problem of segmenting n aligned random sequences of equal length m into a finite number of independent blocks. We propose a penalized maximum likelihood criterion to infer simultaneously the number of points of independence as well as the position of each point. We show how to compute exactly the estimator by means of a dynamic programming algorithm with time complexity O ( m 2 n ) . We also propose another method, called hierarchical algorithm, that provides an approximation to the estimator when the sample size increases and runs in time O { m ln ( m ) n } . Our main theoretical results are the strong consistency of both estimators when the sample size n grows to infinity. We illustrate the convergence of these algorithms through some simulation examples and we apply the method to identify recombination hotspots in real SNPs data. [ABSTRACT FROM AUTHOR]

Abstract Doubly stochastic learning algorithms are scalable kernel methods that perform very well in practice. However, their generalization properties are not well understood and their analysis is challenging since the corresponding learning sequence may not be in the hypothesis space induced by the kernel. In this paper, we provide an in-depth theoretical analysis for different variants of doubly stochastic learning algorithms within the setting of nonparametric regression in a reproducing kernel Hilbert space and considering the square loss. Particularly, we derive convergence results on generalization error for the studied algorithms either with or without an explicit penalty term. To the best of our knowledge, the derived results for the unregularized variants are the first of this kind, while the results for the regularized variants improve those in the literature. The novelties in our proof are a sample error bound that requires controlling the trace norm of a cumulative operator, and a refined analysis of bounding initial error. [ABSTRACT FROM AUTHOR]

Abstract It is known that, for systems of initial-value problems, algorithms using adaptive information perform much better in the worst case setting than the algorithms using nonadaptive information. In the latter case, lower and upper complexity bounds significantly depend on the number of equations. However, in contrast with adaptive information, existing lower and upper complexity bounds for nonadaptive information are not asymptotically tight. In this paper, we close the gap in the complexity exponents, showing asymptotically matching bounds for nonadaptive standard information, as well as for a more general class of nonadaptive linear information. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the problem of dominant point detection on digital curves which consists in finding points with local maximum curvature. Thanks to previous studies of the decomposition of curves into sequence of discrete structures [1–3] , namely maximal blurred segments of width ν [4] , an initial algorithm has been proposed in [5] to detect dominant points. However, an heuristic strategy is used to identify the dominant points. We now propose a modified algorithm without heuristics but a simple measure of angle. In addition, two applications are as well presented: (1) polygonal simplification to reduce the number of detected dominant points by associating a weight to each of them, and (2) classification using the polygon issued from the reduced dominant points. The experimental results demonstrate the efficiency and robustness of the proposed method. [ABSTRACT FROM AUTHOR]

Markov chains have been widely employed as a fundamental model in the studies of probabilistic and stochastic communicating and concurrent systems. It is well-understood that decomposition techniques play a key role in reachability analysis and model-checking of Markov chains. (Discrete-time) quantum Markov chains have been introduced as a model of quantum communicating systems [1] and also a semantic model of quantum programs [2] . The BSCC (Bottom Strongly Connected Component) and stationary coherence decompositions of quantum Markov chains were introduced in [3–5] . This paper presents a new decomposition technique, namely periodic decomposition, for quantum Markov chains. We further establish a limit theorem for them. As an application, an algorithm to find a maximum dimensional noiseless subsystem of a quantum communicating system is given using decomposition techniques of quantum Markov chains. [ABSTRACT FROM AUTHOR]

Taking as input a time-varying sequence of 2D binary digital images, we develop an algorithm for encoding, in the so-called spatiotemporal barcode, lifetime of connected components that are moving in the sequence over time. Given a connected component in a specific time in the sequence, we can track it backwards, by what we call a spatiotemporal path. The main contribution of this paper lies in a new algorithm that computes spatiotemporal paths valid for both foreground and background and developed in a general context, setting the ground for tracking higher dimensional topological features in nD. [ABSTRACT FROM AUTHOR]

This paper presents a method for fitting digital hyperspheres to a given set of n D points in an image in the presence of noise by maximizing the number of inliers, namely the consensus set. The digital Hyperspheres are defined using the k -Flake Digitization models [25] . We present an algorithm, that provides optimal fitting solutions for digital k -Flake hyperspheres within a time complexity O ( ( ( n k ) 2 n − k ) n N n + 1 log ⁡ N ) for dimension n , N being the number of points. We have implemented this algorithm for the particular case of 3D 2-Flake spheres that corresponds to the classical so called Naive digital spheres. [ABSTRACT FROM AUTHOR]

This paper presents a study on the set of the digitizations generated by all the translations of a planar body on a square grid. First the translation vector set is reduced to a bounded subset, then the dual introduced in [1] linking the translation vector to the corresponding digitization is proved to be piecewise constant. Finally, a new algorithm is proposed to compute the digitization set using the dual. [ABSTRACT FROM AUTHOR]

Reading more and more bits from an infinite binary sequence that is random for a Bernoulli measure with parameter p , we can get better and better approximations of p using the strong law of large numbers. In this paper, we study a similar situation from the viewpoint of inductive inference. Assume that p is a computable real, and we have to eventually guess the program that computes p . We show that this cannot be done computably, and extend this result to more general computable distributions. We also provide a weak positive result showing that looking at a sequence X generated according to some computable probability measure, we can guess a sequence of algorithms that, starting from some point, compute a measure that makes X Martin-Löf random. [ABSTRACT FROM AUTHOR]

The wireless sensor networks recently abstract great attention and are used for a wide range of cyber-enabled applications each of which with rigid accuracy requirements. The emergence and existence of coverage holes in WSNs will dramatically degrade the network coverage performance and quality of service. To diminish the negative effects of coverage holes, this paper addresses and studies the confident information coverage hole detection problem (CICHD) based on the proposed novel confident information coverage model (CIC). For solving the CICHD problem, we design two effective heuristic CIC holes detection algorithms including the CHD without considering the nodes residual energy and the other CHDRE taking the nodes’ residual energy into account. In the both proposed algorithms, the sensing field is firstly partitioned into a series of reconstruction grids based on the spatial correlation and correlation range. Then each reconstruction grid will be scanned and detected based on the CIC model to be judged whether it is a hole. Once obtaining the coverage status of every reconstruction grid, the boundary of the coverage hole will be exacted by image processing method. The results of the simulations show that both the proposed schemes can efficiently detect the emerged coverage holes including the locations and the number, and the CHDRE algorithm is more practical and efficient compared to the CHD without considering the energy problem. [ABSTRACT FROM AUTHOR]

In this paper an implicit characterization of the complexity classes k - EXP and k - FEXP , for k ≥ 0 , is given, by a type assignment system for a stratified λ -calculus, where types for programs are witnesses of the corresponding complexity class. Types are formulae of Elementary Linear Logic ( ELL ), and the hierarchy of complexity classes k - EXP is characterized by a hierarchy of types. [ABSTRACT FROM AUTHOR]

A proper subsemigroup of a semigroup is maximal if it is not contained in any other proper subsemigroup. A maximal subsemigroup of a finite semigroup has one of a small number of forms, as described in a paper of Graham, Graham, and Rhodes. Determining which of these forms arise in a given finite semigroup is difficult, and no practical mechanism for doing so appears in the literature. We present an algorithm for computing the maximal subsemigroups of a finite semigroup S given knowledge of the Green's structure of S , and the ability to determine maximal subgroups of certain subgroups of S , namely its group H -classes. In the case of a finite semigroup S represented by a generating set X , in many examples, if it is practical to compute the Green's structure of S from X , then it is also practical to find the maximal subsemigroups of S using the algorithm we present. In such examples, the time taken to determine the Green's structure of S is comparable to that taken to find the maximal subsemigroups. The generating set X for S may consist, for example, of transformations, or partial permutations, of a finite set, or of matrices over a semiring. Algorithms for computing the Green's structure of S from X include the Froidure–Pin Algorithm, and an algorithm of the second author based on the Schreier–Sims algorithm for permutation groups. The worst case complexity of these algorithms is polynomial in | S | , which for, say, transformation semigroups is exponential in the number of points on which they act. Certain aspects of the problem of finding maximal subsemigroups reduce to other well-known computational problems, such as finding all maximal cliques in a graph and computing the maximal subgroups in a group. The algorithm presented comprises two parts. One part relates to computing the maximal subsemigroups of a special class of semigroups, known as Rees 0-matrix semigroups. The other part involves a careful analysis of certain graphs associated to the semigroup S , which, roughly speaking, capture the essential information about the action of S on its J -classes. [ABSTRACT FROM AUTHOR]

Graphical models allow to represent a set of random variables together with their probabilistic conditional dependencies. Various algorithms have been proposed to estimate such models from data. The focus of this paper is on individual observations diagnosis issues. The use of an influence measure is a classical diagnostic method to measure the perturbation induced by a single element, in other terms we consider stability issue through jackknife. For a given graphical model, we provide tools to perform diagnosis on observations. In a second step we propose a filtering of the dataset to obtain a stable network. All along the paper an application to a gene expression dataset illustrates the proposals. [ABSTRACT FROM AUTHOR]

In a recent paper Kelly et al. (2015) [PICIN: A Particle-In-Cell solver for incompressible free surface flows with two-way fluid–solid coupling. SIAM Journal on Scientific Computing 37 (3), B403–24.] detailed the PICIN full particle Particle-In-Cell (PIC) solver for incompressible free-surface flows. The model described in that paper employed a tailored version of the Distributed Lagrange Multiplier (DLM) method for the strong coupling of fluid–solid interaction. In this paper we propose an alternative strong fluid–solid coupling algorithm based on a modification to the cut cell methodology that is informed by the variational approach. The solid velocity flux/integral on the boundary is expressed purely in terms of pressure leading to a revised pressure Poisson equation that is discretised in a finite volume sense. This approach allows the PICIN model to simulate the motion of floating bodies of arbitrary configuration. 2D test cases involving floating bodies with one or more degrees of freedom (DoF) are used to validate the modified PICIN model. The results presented show that the modified PICIN model is able to both efficiently and robustly predict the motions of surface-piercing floating structures under either regular or extreme wave action. [ABSTRACT FROM AUTHOR]

In this paper, we explain in more details the modern treatment of the problem of group classification of (systems of) partial differential equations (PDEs) from the algorithmic point of view. More precisely, we revise the classical Lie algorithm of construction of symmetries of differential equations, describe the group classification algorithm and discuss the process of reduction of (systems of) PDEs to (systems of) equations with smaller number of independent variables in order to construct invariant solutions. The group classification algorithm and reduction process are illustrated by the example of the generalized Zakharov–Kuznetsov (GZK) equations of form u t + ( F ( u ) ) x x x + ( G ( u ) ) x y y + ( H ( u ) ) x = 0 . As a result, a complete group classification of the GZK equations is performed and a number of new interesting nonlinear invariant models which have non-trivial invariance algebras are obtained. Lie symmetry reductions and exact solutions for two important invariant models, i.e., the classical and modified Zakharov–Kuznetsov equations, are constructed. The algorithmic framework for group analysis of differential equations presented in this paper can also be applied to other nonlinear PDEs. [ABSTRACT FROM AUTHOR]

This paper contains three new algorithms for computing invariant rings. The first two apply to invariants of a finite group acting on a finitely generated algebra over a Euclidean ring. This may be viewed as a first step in “computational arithmetic invariant theory.” As a special case, the algorithms can compute multiplicative invariant rings. The third algorithm computes the invariant ring of a reductive group acting on a vector space, and often performs better than the algorithms known to date. The main tool upon which two of the algorithms are built is a generalized version of an ideal that was already used by Derksen in his algorithm for computing invariants of linearly reductive groups. As a further application, these so-called extended Derksen ideals give rise to invariantization maps, which turn an arbitrary ring element into an invariant. For the most part, the algorithms of this paper have been implemented. [ABSTRACT FROM AUTHOR]

This paper introduces hybrid LU–QR algorithms for solving dense linear systems of the form A x = b . Throughout a matrix factorization, these algorithms dynamically alternate LU with local pivoting and QR elimination steps based upon some robustness criterion. LU elimination steps can be very efficiently parallelized, and are twice as cheap in terms of floating-point operations, as QR steps. However, LU steps are not necessarily stable, while QR steps are always stable. The hybrid algorithms execute a QR step when a robustness criterion detects some risk for instability, and they execute an LU step otherwise. The choice between LU and QR steps must have a small computational overhead and must provide a satisfactory level of stability with as few QR steps as possible. In this paper, we introduce several robustness criteria and we establish upper bounds on the growth factor of the norm of the updated matrix incurred by each of these criteria. In addition, we describe the implementation of the hybrid algorithms through an extension of the PaRSEC software to allow for dynamic choices during execution. Finally, we analyze both stability and performance results compared to state-of-the-art linear solvers on parallel distributed multicore platforms. A comprehensive set of experiments shows that hybrid LU–QR algorithms provide a continuous range of trade-offs between stability and performances. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm which, given a point and a set of polynomials, constructs a single cylindrical cell containing the point, such that the given polynomials are sign-invariant in the computed cell. To represent a single cylindrical cell, a novel data structure is introduced. The algorithm works with this representation and proceeds incrementally, i.e., first constructing a cell representing the whole real space, and then iterating over the input polynomials, refining the cell at each step to ensure the sign-invariance of the current input polynomial. A merge procedure realizing this refinement is described, and its correctness is proven. The merge procedure is based on McCallum's projection operator, but uses geometric information relative to the input point to reduce the number of projection polynomials computed. The use of McCallum's operator implies the incompleteness of the algorithm in general. However, the algorithm is complete for well-oriented sets of polynomials. Moreover, the incremental approach described in this paper can be easily adapted to a different projection operator. The cell construction algorithm presented in this paper is an alternative to the “model-based” method described by Jovanović and de Moura in a 2012 paper. It generalizes the algorithm described by the first author in a 2013 paper, which could only produce full-dimensional cells, to allow for the construction of cells of arbitrary dimension. While a thorough comparison, whether analytical or empirical, of the new algorithm and the “model-based” approach will be the subject of future work, this paper provides preliminary justification for asserting the superiority of the new method. [ABSTRACT FROM AUTHOR]

Recently End-to-end (E2E) Automatic Speech Recognition (ASR) has been widely used due to its advantages over the hybrid method. Even though existing E2E ASR models have achieved impressive performance, they usually take a large model size and suffer from a slow inference speed in real-world applications. To obtain faster models for E2E ASR, we propose searching faster architectures with the help of neural architecture search (NAS) in this paper, named SFA. SFA consists of one search space that contains a set of candidate architectures and one search algorithm responsible for searching the optimal architecture from the search space. On one hand, SFA designs a topology-fused search space to integrate different topologies of existing architectures (e.g. Transformer, Conformer) and explore more brand-new ones. On the other hand, combined with the training criterion of E2E ASR, SFA develops a speed-aware differentiable search algorithm to search faster architectures according to target hardware devices. Additionally, a connectionist temporal classification based progressive search algorithm is proposed to reduce the difficulty of the architecture search and obtain better performance. On two commonly-used Mandarin datasets, SFA can effectively improve the inference speed of existing E2E ASR models with comparable performance and achieve at most 2. 46 × / 1. 98 × CPU/GPU speedup than the best human-designed baselines. • E2E ASR suffers from a slow inference speed. • The proposed SFA platform designs fasterarchitectures with the for E2E ASR. • A topology-fused search space provides adequate candidate architectures. • A speed-aware search algorithm selects promising architectures. • An obvious speedup can be achieved with SFA. [ABSTRACT FROM AUTHOR]

Combinatorics of biopolymer structures, especially enumeration of various RNA secondary structures and protein contact maps, is of significant interest for communities of both combinatorics and computational biology. However, most of the previous combinatorial enumeration results for these structures are presented in terms of generating functions, and few are explicit formulas. This paper is mainly concerned with finding explicit enumeration formulas for a particular class of biologically relevant structures, say, saturated 2-regular simple stacks, whose configuration is related to protein folds in the 2D honeycomb lattice. We establish a semi-bijective algorithm that converts saturated 2-regular simple stacks into forests of small trees, which produces a uniform formula for saturated extended 2-regular simple stacks with any of the six primary component types. Summarizing the six different primary component types, we obtain a bivariate explicit formula for saturated extended 2-regular simple stacks with n vertices and k arcs. As consequences, the uniform formula can be reduced to Clote's results on k -saturated 2-regular simple stacks and the optimal 2-regular simple stacks, and Guo et al.'s result on the optimal extended 2-regular simple stacks. [ABSTRACT FROM AUTHOR]

When a plain Monte Carlo estimate on n samples has variance σ 2 / n , then scrambled digital nets attain a variance that is o (1 / n) as n → ∞. For finite n and an adversarially selected integrand, the variance of a scrambled (t , m , s) -net can be at most Γ σ 2 / n for a maximal gain coefficient Γ < ∞. The most widely used digital nets and sequences are those of Sobol'. It was previously known that Γ ⩽ 2 t 3 s for any nets in base 2. For digital nets, Dick and Pillichshammer (2010) obtained the bound 2 t + s. In this paper we study digital nets in base 2 and show that Γ ⩽ 2 t + s − 1 for such nets. This bound is a simple, but apparently unnoticed, consequence of a microstructure analysis by Niederreiter and Pirsic in 2001. We obtain a sharper bound that is smaller than this for some digital nets. Our main finding is that all nonzero gain coefficients must be powers of two. A consequence of this latter fact is a simplified algorithm for computing gain coefficients of digital nets in base 2. [ABSTRACT FROM AUTHOR]

Martin-Löf defined algorithmic randomness, the use of martingales in this definition and several variants were explored by Schnorr, and Lutz introduced resource-bounded randomness. Ambos-Spies et al. have studied resource-bounded randomness under time-bounds and have shown that resource-bounded randomness implies resource-bounded genericity. While the genericity of Ambos-Spies is based on time-bound on finite-extension strategy, the genericity of Dowd, the main topic of this paper, is based on an analogy of the forcing theorem. For a positive integer r , an oracle D is r -generic in the sense of Dowd ( r -Dowd) if the following holds: If a certain formula F on an exponential-sized portion of D is a tautology then a polynomial-sized subfunction of D forces F to be a tautology. Here, r is the number of occurrences of query symbols in F . The relationship between resource-bounded randomness and Dowd-type genericity has been not clear so far. We show that there exists a primitive recursive function t ( n ) with the following property: Every t ( n ) -random set is r -Dowd for each positive integer r . A proof is done by means of constructing resource-bounded martingales. In our former paper, we left an open problem whether there exists a primitive recursive set which is r -Dowd for every positive integer r . In our recent work, we give an affirmative answer to the problem. The main theorem of the present paper gives an alternative proof of the affirmative answer. [ABSTRACT FROM AUTHOR]

In this paper, we develop a novel and effective Euclidean algorithm for Laurent polynomial matrix extension (LPME), which is the key of the construction of perfect reconstruction filter banks (PRFBs). The algorithm gives an approach to the construction of PRFBs other than the dual-chain approach in the paper [5] . The developed algorithm can also be used in the applications where LPME plays a role. [ABSTRACT FROM AUTHOR]

Text A weird number is a number n for which σ ( n ) > 2 n and such that n is not a sum of distinct proper divisors of n . In this paper we prove that n = 2 k p q is weird for a quite large set of primes p and q . In particular this gives an algorithm to generate very large primitive weird numbers, i.e., weird numbers that are not multiple of other weird numbers. Assuming classical conjectures on the gaps between consecutive primes, this also would prove that there are infinitely many primitive weird numbers, a question raised by Benkoski and Erdős in 1974. Video For a video summary of this paper, please visit http://youtu.be/OS93l3a_Mjo . [ABSTRACT FROM AUTHOR]

In this paper, a new algorithm is presented for deciding the semi-definiteness of multivariate polynomials with coefficients in a computable ordered field, which admits an effective method of finding an isolating set for every non-zero univariate polynomial. This algorithm is an improvement of the method presented in Ref. [24]. The technique in this paper is to compute triangular decompositions of polynomial systems into regular chains. [ABSTRACT FROM AUTHOR]

The paper introduces an extension of context-free grammars equipped with an operator for referring to the left context of the substring being defined. For example, a rule A→a& B defines a symbol a, as long as it is preceded by a string defined by B. The conjunction operator in this example is taken from conjunctive grammars (Okhotin, 2001), which are an extension of ordinary context-free grammars that maintains most of their practical properties, including many parsing algorithms. This paper gives two equivalent definitions of grammars with left contexts--by logical deduction and by language equations--and establishes their basic properties, including a transformation to a normal form and a cubic-time parsing algorithm, with a square-time version for unambiguous grammars. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we continue our investigation of symmetric tight framelet filter banks (STFFBs) with a minimum number of generators in [6]. In particular, we shall systematically study STFFBs with three high-pass filters which are derived from the oblique extension principle. To our best knowledge, except the papers [1,10], there are no other papers in the literature so far systematically studying this problem. In this paper we show that there are two different types, called type I and type II, of STFFBs with three high-pass filters. Then we provide a detailed analysis and a complete algorithm to obtain all type I STFFBs with three high-pass filters. Our results not only significantly generalize the results in [1,10], but also help us answer several unresolved problems on STFFBs. Based on [6], we also propose an algorithm to construct all type II STFFBs with three high-pass filters and with the shortest possible filter supports. Several examples are given to illustrate the results and algorithms in this paper. [Copyright &y& Elsevier]

In this paper, we study the desingularization problem in the first q -Weyl algebra. We give an order bound for desingularized operators, and thus derive an algorithm for computing desingularized operators in the first q -Weyl algebra. Moreover, an algorithm is presented for computing a generating set of the first q -Weyl closure of a given q -difference operator. As an application, we certify that several instances of the colored Jones polynomial are Laurent polynomial sequences by computing the corresponding desingularized operator. [ABSTRACT FROM AUTHOR]

We describe a subdivision algorithm for isolating the complex roots of a polynomial F ∈ C [ x ] . Given an oracle that provides approximations of each of the coefficients of F to any absolute error bound and given an arbitrary square B in the complex plane containing only simple roots of F , our algorithm returns disjoint isolating disks for the roots of F in B . Our complexity analysis bounds the absolute error to which the coefficients of F have to be provided, the total number of iterations, and the overall bit complexity. It further shows that the complexity of our algorithm is controlled by the geometry of the roots in a near neighborhood of the input square B , namely, the number of roots, their absolute values and pairwise distances. The number of subdivision steps is near-optimal. For the benchmark problem , namely, to isolate all the roots of a polynomial of degree n with integer coefficients of bit size less than τ , our algorithm needs O ˜ ( n 3 + n 2 τ ) bit operations, which is comparable to the record bound of Pan (2002) . It is the first time that such a bound has been achieved using subdivision methods, and independent of divide-and-conquer techniques such as Schönhage's splitting circle technique. Our algorithm uses the quadtree construction of Weyl (1924) with two key ingredients: using Pellet's Theorem (1881) combined with Graeffe iteration, we derive a “soft-test” to count the number of roots in a disk. Using Schröder's modified Newton operator combined with bisection, in a form inspired by the quadratic interval method from Abbot (2006), we achieve quadratic convergence towards root clusters. Relative to the divide-conquer algorithms, our algorithm is quite simple with the potential of being practical. This paper is self-contained: we provide pseudo-code for all subroutines used by our algorithm. [ABSTRACT FROM AUTHOR]

In the field of human speech capturing systems, a fundamental role is played by the source localization algorithms. In this paper a Speaker Localization algorithm (SLOC) based on Deep Neural Networks (DNN) is evaluated and compared with state-of-the art approaches. The speaker position in the room under analysis is directly determined by the DNN, leading the proposed algorithm to be fully data-driven. Two different neural network architectures are investigated: the Multi Layer Perceptron (MLP) and Convolutional Neural Networks (CNN). GCC-PHAT (Generalized Cross Correlation-PHAse Transform) Patterns, computed from the audio signals captured by the microphone are used as input features for the DNN. In particular, a multi-room case study is dealt with, where the acoustic scene of each room is influenced by sounds emitted in the other rooms. The algorithm is tested by means of the home recorded DIRHA dataset, characterized by multiple wall and ceiling microphone signals for each room. In detail, the focus goes to speaker localization task in two distinct neighboring rooms. As term of comparison, two algorithms proposed in literature for the addressed applicative context are evaluated, the Crosspower Spectrum Phase Speaker Localization (CSP-SLOC) and the Steered Response Power using the Phase Transform speaker localization (SRP-SLOC). Besides providing an extensive analysis of the proposed method, the article shows how DNN-based algorithm significantly outperforms the state-of-the-art approaches evaluated on the DIRHA dataset, providing an average localization error, expressed in terms of Root Mean Square Error (RMSE), equal to 324 mm and 367 mm, respectively, for the Simulated and the Real subsets. [ABSTRACT FROM AUTHOR]

Model checking allows one to automatically verify a specification of the expected properties of a system against a formal model of its behavior (generally, a Kripke structure). Point-based temporal logics, such as LTL, CTL, and CTL ⁎ , that describe how the system evolves state-by-state, are commonly used as specification languages. They proved themselves quite successful in a variety of application domains. However, properties constraining the temporal ordering of temporally extended events as well as properties involving temporal aggregations, which are inherently interval-based, can not be properly dealt with by them. Interval temporal logics (ITLs), that take intervals as their primitive temporal entities, turn out to be well-suited for the specification and verification of interval properties of computations (we interpret all the tracks of a Kripke structure as computation intervals). In this paper, we study the model checking problem for some fragments of Halpern and Shoham's modal logic of time intervals (HS). HS features one modality for each possible ordering relation between pairs of intervals (the so-called Allen's relations). First, we describe an EXPSPACE model checking algorithm for the HS fragment of Allen's relations meets , met-by , starts , started-by , and finishes , which exploits the possibility of finding, for each track (of unbounded length), an equivalent bounded-length track representative. While checking a property, it only needs to consider tracks whose length does not exceed the given bound. Then, we prove the model checking problem for such a fragment to be PSPACE-hard. Finally, we identify other well-behaved HS fragments which are expressive enough to capture meaningful interval properties of systems, such as mutual exclusion, state reachability, and non-starvation, and whose computational complexity is less than or equal to that of LTL. [ABSTRACT FROM AUTHOR]

Data grid is emerging as the main part of the infrastructure for large-scale data intensive applications such as high energy physics and bioinformatics. The deployment of such infrastructures has allowed users of a grid site to gain access to a large amount of distributed data. Data replication is a key issue in a data grid and could be applied intelligently because it reduces data access time and bandwidth consumption for each grid site. In this paper, we introduce a new dynamic data replication algorithm named Popular Groups of Files Replication (PGFR). Our proposed algorithm is based on an assumption: users in a Virtual Organization have similar interests in groups of files. Based on this assumption, and file access history, PGFR builds a connectivity graph to recognize a group of dependent files in each grid site and replicates the most Popular Groups of Files to each grid site, thus increasing the local availability. We used OptorSim simulator to evaluate the efficiency of PGFR algorithm. The simulation results show that PGFR achieves better performance compared to the existing algorithm; PGFR minimized the mean job execution time, bandwidth consumption, and avoiding unnecessary replication. [ABSTRACT FROM AUTHOR]

A Dyck path of length 2 k with e flaws is a path in the integer lattice that starts at the origin and consists of k many ↗ -steps and k many ↘ -steps that change the current coordinate by ( 1 , 1 ) or ( 1 , − 1 ) , respectively, and that has exactly e many ↘ -steps below the line y = 0 . Denoting by D 2 k e the set of Dyck paths of length 2 k with e flaws, the well-known Chung–Feller theorem asserts that the sets D 2 k 0 , D 2 k 1 , … , D 2 k k all have the same cardinality 1 k + 1 2 k k = C k , the k th Catalan number. The standard combinatorial proof of this classical result establishes a bijection f ′ between D 2 k e and D 2 k e + 1 that swaps certain parts of the given Dyck path x , with the effect that x and f ′ ( x ) may differ in many positions. In this paper we strengthen the Chung–Feller theorem by presenting a simple bijection f between D 2 k e and D 2 k e + 1 which has the additional feature that x and f ( x ) differ in only two positions (the least possible number). We also present an algorithm that allows to compute a sequence of applications of f in constant time per generated Dyck path. As an application, we use our minimum-change bijection f to construct cycle-factors in the odd graph O 2 k + 1 and the middle levels graph M 2 k + 1 – two intensively studied families of vertex-transitive graphs – that consist of C k many cycles of the same length. [ABSTRACT FROM AUTHOR]

In this paper we prove a new recurrence relation on the van der Waerden numbers, w ( r , k ) . In particular, if p is a prime and p ≤ k then w ( r , k ) > p ⋅ w r − r p , k − 1 . This recurrence gives the lower bound w ( r , p + 1 ) > p r − 1 2 p when r ≤ p , which generalizes Berlekamp’s theorem on 2-colorings, and gives the best known bound for a large interval of r . The recurrence can also be used to construct explicit valid colorings, and it improves known lower bounds on small van der Waerden numbers. [ABSTRACT FROM AUTHOR]

This paper deals with two types of repetitions in strings: squares , which consist of two adjacent occurrences of substrings, and runs , which are periodic substrings that cannot be extended further to the left or right while maintaining the period. We show how to compute all the primitively-rooted squares in a given partial word, which is a sequence that may have undefined positions, called holes or wildcards, that match any letter of the alphabet over which the sequence is defined. We also describe an algorithm for computing all primitively-rooted runs in a given partial word and extend previous analyses on the number of runs to partial words. [ABSTRACT FROM AUTHOR]

A perfect 2-matching in an undirected graph G = ( V , E ) is a function x : E → 0 , 1 , 2 such that for each node v ∈ V the sum of values x ( e ) on all edges e incident to v equals 2. If supp ( x ) = e ∈ E ∣ x ( e ) ≠ 0 contains no triangles then x is called triangle-free . Polyhedrally speaking, triangle-free 2-matchings are harder than 2-matchings, but easier than usual 1-matchings. Given edge costs c : E → R + , a natural combinatorial problem consists in finding a perfect triangle-free matching of minimum total cost. For this problem, Cornuéjols and Pulleyblank devised a combinatorial strongly-polynomial algorithm, which can be implemented to run in O ( V E log V ) time. (Here we write V , E to indicate their cardinalities | V | , | E | .) If edge costs are integers in range [ 0 , C ] then for both 1- and 2-matchings some faster scaling algorithms are known that find optimal solutions within O ( V α ( E , V ) log V E log ( V C ) ) and O ( V E log ( V C ) ) time, respectively, where α denotes the inverse Ackermann function. So far, no efficient cost-scaling algorithm is known for finding a minimum-cost perfect triangle-free2-matching. The present paper fills this gap by presenting such an algorithm with time complexity of O ( V E log V log ( V C ) ) . [ABSTRACT FROM AUTHOR]

The goal of the present paper is to extend the mitosis algorithm, originally developed by Ezra Miller and Allen Knutson for the case of Schubert polynomials, to the case of Grothendieck polynomials. In addition we will also use this algorithm to construct a short combinatorial proof of Fomin–Kirillov's formula for the coefficients of Grothendieck polynomials. [ABSTRACT FROM AUTHOR]

In this paper, we study the backward–forward algorithm as a splitting method to solve structured monotone inclusions, and convex minimization problems in Hilbert spaces. It has a natural link with the forward–backward algorithm and has the same computational complexity, since it involves the same basic blocks, but organized differently. Surprisingly enough, this kind of iteration arises when studying the time discretization of the regularized Newton method for maximally monotone operators. First, we show that these two methods enjoy remarkable involutive relations, which go far beyond the evident inversion of the order in which the forward and backward steps are applied. Next, we establish several convergence properties for both methods, some of which were unknown even for the forward–backward algorithm. This brings further insight into this well-known scheme. Finally, we specialize our results to structured convex minimization problems, the gradient-projection algorithms, and give a numerical illustration of theoretical interest. [ABSTRACT FROM AUTHOR]

The computation of Kronecker coefficients is a challenging problem with a variety of applications. In this paper we present an approach based on methods from symplectic geometry and residue calculus. We outline a general algorithm for the problem and then illustrate its effectiveness in several interesting examples. Significantly, our algorithm does not only compute individual Kronecker coefficients, but also symbolic formulas that are valid on an entire polyhedral chamber. As a byproduct, we are able to compute several Hilbert series. [ABSTRACT FROM AUTHOR]

In this paper, we study Noether type symmetry theorem to fractional Birkhoffian systems with Riemann–Liouville derivatives. This theorem provides an explicit algorithmic way to compute a constant for any Birkhoffian systems admitting a symmetry. Finally, we extend our Noether's theorem to fractional Birkhoffian systems base on Caputo or Riesz derivatives. [ABSTRACT FROM AUTHOR]

One of the most famous algorithmic meta-theorems states that every graph property which can be defined in counting monadic second order logic (CMSOL) can be checked in linear time on graphs of bounded treewidth, which is known as Courcelle’s Theorem (Courcelle, 1990). These algorithms are constructed as finite state tree automata and hence every CMSOL-definable graph property is recognizable. Courcelle also conjectured that the converse holds, i.e. every recognizable graph property is definable in CMSOL for graphs of bounded treewidth. In this paper we prove two special cases of this conjecture, first for the class of k -outerplanar graphs, which are known to have treewidth at most 3 k − 1 (Bodlaender, 1998) and for graphs of bounded treewidth without chordless cycles of length at least some constant ℓ . We furthermore show that for a proof of Courcelle’s Conjecture it is sufficient to show that all members of a graph class admit constant width tree decompositions whose bags and edges can be identified with MSOL-predicates. For graph classes that admit MSOL-definable constant width tree decompositions that have bounded degree or allow for a linear ordering of all nodes with the same parent we even give a stronger result: In that case, the counting predicates of CMSOL are not needed. [ABSTRACT FROM AUTHOR]

The generalised colouring numbers col r ( G ) and wcol r ( G ) were introduced by Kierstead and Yang as a generalisation of the usual colouring number, and have since then found important theoretical and algorithmic applications. In this paper, we dramatically improve upon the known upper bounds for generalised colouring numbers for graphs excluding a fixed minor, from the exponential bounds of Grohe et al. to a linear bound for the r -colouring number col r and a polynomial bound for the weak r -colouring number wcol r . In particular, we show that if G excludes K t as a minor, for some fixed t ≥ 4 , then col r ( G ) ≤ t − 1 2 ( 2 r + 1 ) and wcol r ( G ) ≤ r + t − 2 t − 2 ( t − 3 ) ( 2 r + 1 ) ∈ O ( r t − 1 ) . In the case of graphs G of bounded genus g , we improve the bounds to col r ( G ) ≤ ( 2 g + 3 ) ( 2 r + 1 ) (and even col r ( G ) ≤ 5 r + 1 if g = 0 , i.e. if G is planar) and wcol r ( G ) ≤ ( 2 g + r + 2 2 ) ( 2 r + 1 ) . [ABSTRACT FROM AUTHOR]

The estimation of glottal closure instants (GCIs) plays a vital role in several glottal synchronous applications, and may not be restricted to clean speech. This necessitates the development of a GCI estimation algorithm that performs as well on degraded speech as on clean speech. Degradations in speech may be in the form of spectral or temporal perturbations. This could result in several spurious discontinuities, as in noisy speech, excitations that are not well-defined, as in band-limited speech, aperiodicity and variations in amplitude, as in pathological speech, thereby making the task of identifying GCIs more challenging. In this regard, a conditional group-delay/phase-difference-based (PD) algorithm that was initially proposed for use on clean speech is extended to operate on degraded speech, specifically telephone, noisy, and pathological speech. The performance of this algorithm is compared with six existing algorithms, in terms of identification, false alarm, and miss rates, and identification accuracy. It is observed that the PD algorithm is robust to degradations in speech and performs better than or on par with existing algorithms in all cases considered. Further, it is also observed that unlike existing algorithms, the PD algorithm scarcely estimates GCIs in non-voiced regions and this is verified in terms of a new metric proposed in the paper, namely, the spurious instants rate in non-voiced regions. [ABSTRACT FROM AUTHOR]

The main objective of this paper is to find algorithms accompanied by explicit error bounds for phase retrieval from noisy magnitudes of frame coefficients when the underlying frame has a low redundancy. We achieve these goals with frames consisting of N = 6 d − 3 vectors spanning a d -dimensional complex Hilbert space. The two algorithms we use, phase propagation or the kernel method, are polynomial time in the dimension d . To ensure a successful approximate recovery, we assume that the noise is sufficiently small compared to the squared norm of the vector to be recovered. In this regime, we derive an explicit error bound that is inverse proportional to the signal-to-noise ratio, with a constant of proportionality that depends only on the dimension d . Properties of the reproducing kernel space of complex polynomials and of trigonometric polynomials are central in our error estimates. [ABSTRACT FROM AUTHOR]