An Optimal Algorithm for Constructing the Reduced Gröbner Basis of Binomial Ideals

In this paper, we present an optimal, exponential space algorithm for generating the reduced Gröbner basis of binomial ideals. We make use of the close relationship between commutative semigroups and pure difference binomial ideals. Based on an optimal algorithm for the uniform word problem in commutative semigroups, we first derive an exponential space algorithm for constructing the reduced Gröbner basis of pure difference binomial ideals. In addition to some applications to finitely presented commutative semigroups, this algorithm is then extended to an exponential space algorithm for generating the reduced Gröbner basis of binomial ideals over Q in general.     

A Convergence Analysis of the Inexact Simplified Jacobi–Davidson Algorithm for Polynomial Eigenvalue Problems

The simplified Jacobi–Davidson (JD) method is a variant of the JD method without subspace acceleration. If the correction equation is solved approximately, the inexact simplified JD method is obtained. In this paper, we present a new convergence analysis of the inexact simplified JD method. The analysis applies to polynomial eigenvalue problems with simple eigenpairs. We first establish a relationship between the solution of the correction equation and the residual of the approximate eigenpair. From this relationship, we find the difference of two adjacent approximate eigenvalues bounded in terms of the residual norm of the approximate eigenpair. Then we prove the convergence of the inexact simplified JD method in terms of the residual norm of the approximate eigenpair. Depending on how accurately we solve the correction equation, the convergence rate of the inexact simplified JD may take several different forms. Numerical experiments confirm the convergence analysis.     

An Algorithm for Timing Verification of Systems Constrained by Min–max Inequalities

To determine the maximum separation between events for nonrepetitive systems with max and linear constraints, there are the “iterative tightening from above” (ITA) approach and the “iterative tightening from below” (ITB) approach. Since such systems can be formulated as systems constrained by min–max inequalities, this paper gives an algorithm named MMIMaxSep for solving min–max inequalities. The algorithm is a generalization and a mathematically elegant reformulation of Yen et al.’s MaxSeparation algorithm which uses the ITB approach. Our numerical experiments indicate that MMIMaxSep is very efficient. Moreover, MMIMaxSep has a unique advantage of being able to directly handle tree-represented min–max functions, and its complexity is closely related to the complexity of computing cycle time of min–max functions.

An Optimal Algorithm for Constructing the Reduced Gröbner Basis of Binomial Ideals,and Applications to Commutative Semigroups

It is known that the reduced Gröbner basis of general polynomial ideals can be computed in exponential space. The algorithm, obtained by Kühnle and Mayr, is, however, based on rather complex parallel computations, and, above that, makes extensive use of the parallel computation thesis. In this paper, we exhibit an exponential space algorithm for generating the reduced Gröbner basis of binomial ideals which can be implemented without any complex parallel computations. This result is then applied to derive space optimal decision procedures for the finite enumeration and subword problems for commutative semigroups.     

An Efficient Algorithm for the Calculation of NURBS Curves and All Their Derivatives

Through a precise recursion of B-spline bases, this paper presents an efficient algorithm for the calculation of NURBS curves and all their derivatives. The algorithm requires less storage and is proved to be stable.     

On two versions of the Loomis–Sikorski Theorem for algebraic structures

We present two versions of the Loomis–Sikorski Theorem, one for monotone σ-complete generalized pseudo effect algebras with strong unit satisfying a kind of the Riesz decomposition property. The second one is for Dedekind σ-complete positive pseudo Vitali spaces with strong unit. For any case we can find an appropriate system of nonnegative bounded functions forming an algebra of the given type with the operations defined by points that maps epimorphically onto the algebra. The paper has been supported by the Center of Excellence SAS—Physics of Information—I/2/2005, the grant VEGA No. 2/6088/26 SAV, the Slovak Research and Development Agency under the contract No. APVV-0071-06, Slovak-Italian Project No. 15:“Algebraic and logical systems of soft computing”, and MURST, project “Analisi Reale”.     

An Algorithm for Determining Minimal Reduced-Coverings of Acyclic Database Schemes

1IntroductionItiswell-knownthatacyclicdatabaseschemeshavesomeverydesirablepr0P-erties-Thesepr0pertie8areappliedwidelyinb0thdesignandmanagement0fdatabases[1'3].Atpresent,therearemanyresultsab0utacyclicdatabaseschemesI1-4'7].Animp0rtantbranchoftheseresultsisthepr0blemofminimalcovers.Veryoften,inbothdesignandmanagementofdatabase,0nlyaset0fpartialrelationorsets0fattributeswithsomespecia.lproperties0fadatabaseschemeareconcerned.Applications0fthesesortsleadtothestudy0fmanyproblemsab0ut..lnummumand…     

An Algorithm for Determining Database Consistency Under the Closed World Assumption

It is well-known that there are circumstances where applying Reiter's closed world assump-tion (CWA) will lead to logical inconsistencies . In this paper, a new characterization of theCWA consistency is pesented and an algorithm is proposed for determining whether a datalase with-out function symbols is consistent with the CWA. The algorithm is shown to be efficient.     

An Algorithm for Determining Database Consistency Under the Closed World Assumption

It is well-known that there are circumstances where applying Reiter‘s closed world assumption(CWA)will lead to logical inconsistencies.In this paper,a new characterization of the CA consistency is pesented and an algorithm is proposed for determining whether a datalase without function symbols is consistent with the CWA.The algorithm is shown to be efficient.     

An SDP Primal-Dual Algorithm for Approximating the Lovász-Theta Function

The Lovász ?-function (Lovász in IEEE Trans. Inf. Theory, 25:1–7, 1979) of a graph G=(V,E) can be defined as the maximum of the sum of the entries of a positive semidefinite matrix X, whose trace Tr(X) equals 1, and X _ij =0 whenever {i,j}∈E. This function appears as a subroutine for many algorithms for graph problems such as maximum independent set and maximum clique. We apply Arora and Kale’s primal-dual method for SDP to design an algorithm to approximate the ?-function within an additive error of δ>0, which runs in time $O(\frac{\vartheta ^{2} n^{2}}{\delta^{2}} \log n \cdot M_{e})$ , where ?=?(G) and M _e =O(n ³) is the time for a matrix exponentiation operation. It follows that for perfect graphs G, our primal-dual method computes ?(G) exactly in time O(? ² n ⁵logn). Moreover, our techniques generalize to the weighted Lovász ?-function, and both the maximum independent set weight and the maximum clique weight for vertex weighted perfect graphs can be approximated within a factor of (1+?) in time O(? ^?2 n ⁵logn).     

An integrated Data Envelopment Analysis–Artificial Neural Network–Rough Set Algorithm for assessment of personnel efficiency

Personnel specifications have greatest impact on total efficiency. They can help us to design work environment and enhance total efficiency. Determination of critical personnel attributes is a useful procedure to overcome complication associated with multiple inputs and outputs. The proposed algorithm assesses the impact of personnel efficiency attributes on total efficiency through Data Envelopment Analysis (DEA), Artificial Neural Network (ANN) and Rough Set Theory (RST). DEA has two roles in the proposed integrated algorithm of this study. It provides data ANN and finally it selects the best reduct through ANN result. Reduct is described as a minimum subset of attributes, completely discriminating all objects in a data set. The reduct selection is achieved by RST. ANN has two roles in the integrated algorithm. ANN results are basis for selecting the best reduct and it is also used for forecasting total efficiency. The proposed integrated approach is applied to an actual banking system and its superiorities and advantages are discussed.     

An Adaptive Algorithm for the Time Dependent Transport Equation with Anisotropic Finite Elements and the Crank–Nicolson Scheme

Anisotropic finite elements and the Crank–Nicolson scheme are considered to solve the time dependent transport equation. Anisotropic a priori and a posteriori error estimates are derived. The sharpness of the error indicator is studied on non-adapted meshes and time steps. An adaptive algorithm in space and time is then designed to control the error at final time. Numerical results show the accuracy of the method.     

Generalization of the Firm’s Profit Maximization Problem: An Algorithm for the Analytical and Nonsmooth Solution

In this paper we present a generalization of the classic Firm’s profit maximization problem, using the linear model for the production function, considering a non constant price and maximum constraints for the inputs. We formulate the problem by previously calculating the analytical minimum cost function. This minimum cost function will be calculated for each production level via the infimal convolution of quadratic functions and the result will be a piecewise quadratic function. To solve this family of optimization problems, we present an algorithm of quasi-linear complexity. Moreover, the resulting cost function in certain cases is not $C^{1}$ and the profit maximization problem will be solved within the framework of nonsmooth analysis. Finally, we present a numerical example.     

Almost Stable Matchings by Truncating the Gale–Shapley Algorithm

We show that the ratio of matched individuals to blocking pairs grows linearly with the number of propose–accept rounds executed by the Gale–Shapley algorithm for the stable marriage problem. Consequently, the participants can arrive at an almost stable matching even without full information about the problem instance; for each participant, knowing only its local neighbourhood is enough. In distributed-systems parlance, this means that if each person has only a constant number of acceptable partners, an almost stable matching emerges after a constant number of synchronous communication rounds.     

Algorithm for Identifying Outline of 2D Graphics by Comparing Angles

The initial point and edge are first determined, the subsequent edges on contour are searched by comparing the angles formed by vectors of the candidate edges and the reference vector, repeat this process until the searched edges are closed. The bi-directional list is adopted to store graphic data. Data structure for storing the point and graphic entity is also discussed.     

On the Capabilities of the Polynomial Chaos Expansion Method within SFE Analysis—An Overview

This paper addresses the most recent developments concerning the application of the P-C expansion method within the Stochastic Finite Element (SFE) analysis, in particular considering computational solid mechanics. More specifically, the focus has been on the use of the method for the propagation of the stochastic structural responses due to the extensive amount of contributions in this context. Numerical examples presented in the literature are listed in this regard, in order to shed some light on the range of applications, especially in terms of the probabilistic dimensionality of the problem. Furthermore, the recently emerging utilization of the method within the modeling of uncertain input parameters is covered briefly. With this contribution, it is aimed to present an overview on the state-of-art of the P-C literature and the capabilities of the method.     

FOPWA： An Optimized Parallel Algorithm of Watershed Transform for Image Segmentation

Watershed segmentation/transform is a classical method for image segmentation in gray scale mathematical morphology. Nevertheless watershed algorithm has strong recursive nature, so straightforward parallel one has very low efficiency. Firstly, the advantages and disadvantages of some existing parallel algorithms are analyzed. Secondly, a Further Optimized Parallel Watershed Algorithm （FOPWA） is presented based on boundary components graph. As the experiments show, FOPWA optimizes both running time and relative speedup, and has more flexibility.     

High Order Algorithm for the Time-Tempered Fractional Feynman–Kac Equation

We provide and analyze the high order algorithms for the model describing the functional distributions of particles performing anomalous motion with power-law jump length and tempered power-law waiting time. The model is derived in Wu et al. (Phys Rev E 93:032151, 2016), being called the time-tempered fractional Feynman–Kac equation named after Richard Feynman and Mark Kac who first considered the model describing the functional distribution of normal motion. The key step of designing the algorithms is to discretize the time tempered fractional substantial derivative, being defined as

$$\begin{aligned} {^S\!}D_t^{\gamma ,\widetilde{\lambda }} G(x,p,t)\!=\!D_t^{\gamma ,\widetilde{\lambda }} G(x,p,t)\!-\!\lambda ^\gamma G(x,p,t) \end{aligned}$$

with \(\widetilde{\lambda }=\lambda + pU(x),\, p=\rho +J\eta ,\, J=\sqrt{-1}\), where

$$\begin{aligned} D_t^{\gamma ,\widetilde{\lambda }} G(x,p,t) =\frac{1}{\varGamma (1-\gamma )} \left[ \frac{\partial }{\partial t}+\widetilde{\lambda } \right] \int _{0}^t{\left( t-z\right) ^{-\gamma }}e^{-\widetilde{\lambda }\cdot (t-z)}{G(x,p,z)}dz, \end{aligned}$$

and \(\lambda \ge 0\), \(0<\gamma <1\), \(\rho >0\), and \(\eta \) is a real number. The designed schemes are unconditionally stable and have the global truncation error \(\mathscr {O}(\tau ^2+h^2)\), being theoretically proved and numerically verified in complex space. Moreover, some simulations for the distributions of the first passage time are performed, and the second order convergence is also obtained for solving the ‘physical’ equation (without artificial source term).

     

Alternative proof of the Lyndon–Schützenberger Theorem

Some observations on products of primitive words are discussed. By these results, alternative proof is given for the Lyndon–Schützenberger Theorem, which says that every solution of the equation a^mbⁿ=c^k$a^m{b}^n=c^k$ over Σ^*${\Sigma }^{*}$ is trivial.