Tyrolean termination tool: Techniques and features

The Tyrolean Termination Tool (T_TT for short) is a powerful tool for automatically proving termination of rewrite systems. It incorporates several new refinements of the dependency pair method that are easy to implement, increase the power of the method, result in simpler termination proofs, and make the method more efficient. T_TT employs polynomial interpretations with negative coefficients, like x − 1 for a unary function symbol or x − y for a binary function symbol, which are useful for extending the class of rewrite systems that can be proved terminating automatically. Besides a detailed account of these techniques, we describe the convenient web interface of T_TT and provide some implementation details.     

Completion of Rewrite Systems with Membership Constraints Part I: Deduction Rules

We consider a constrained equational logic where the constraints are membership conditions t∈swheresis interpreted as a regular tree language. Our logic includes a fragment of second-order equational logic (without projections) where second-order variables range over regular sets of contexts. The problem with constrained equational logics is the failure of the critical pair lemma. This is the reason why we propose new deduction rules for which the critical pair lemma is restored. Computing critical pairs requires, however, solving some constraints in a second-order logic with membership constraints. In a second paper we give a terminating set of transformation rules for these formulas, which decides the existence of a solution, thus showing a new term scheme unification algorithm.Since an order-sorted signature is nothing but a bottom–up tree automaton, order-sorted equational logic falls into the scope of our study; our results show how to perform order-sorted completion without regularity and without sort-decreasingness. It also shows how to perform unification in the order-sorted case, with some higher-order variables (without any regularity assumption).     

Fast congruence closure and extensions

Congruence closure algorithms for deduction in ground equational theories are ubiquitous in many (semi-)decision procedures used for verification and automated deduction. In many of these applications one needs an incremental algorithm that is moreover capable of recovering, among the thousands of input equations, the small subset that explains the equivalence of a given pair of terms. In this paper we present an algorithm satisfying all these requirements. First, building on ideas from abstract congruence closure algorithms, we present a very simple and clean incremental congruence closure algorithm and show that it runs in the best known time O(n  log  n). After that, we introduce a proof-producing union-find data structure that is then used for extending our congruence closure algorithm, without increasing the overall O(n  log  n) time, in order to produce a k-step explanation for a given equation in almost optimal time (quasi-linear in k). Finally, we show that the previous algorithms can be smoothly extended, while still obtaining the same asymptotic time bounds, in order to support the interpreted functions symbols successor and predecessor, which have been shown to be very useful in applications such as microprocessor verification.     

Algorithmic complexity bounds on future prediction errors

We bound the future loss when predicting any (computably) stochastic sequence online. Solomonoff finitely bounded the total deviation of his universal predictor M from the true distribution μ by the algorithmic complexity of μ. Here we assume that we are at a time t > 1 and have already observed x = x₁ ⋯ x_t. We bound the future prediction performance on x_t+1x_t+2 ⋯ by a new variant of algorithmic complexity of μ given x, plus the complexity of the randomness deficiency of x. The new complexity is monotone in its condition in the sense that this complexity can only decrease if the condition is prolonged. We also briefly discuss potential generalizations to Bayesian model classes and to classification problems.     

Parallel Sorting Algorithm Using Multiway Merge and Its Implementation on a Multi-Mesh Network

In this paper, we present a parallel sorting algorithm using the technique of multi-way merge. This algorithm, when implemented on a t dimensional mesh having n^t nodes (t>2), sorts n^t elements in O((t²−3t+2) n) time, thus offering a better order of time complexity than the [((t²−t) n log n)/2+O(nt)]-time algorithm of P. F. Corbett and I. D. Scherson (1992, IEEE Trans. Parallel Distrib. Systems3, 626–632). Further, the proposed algorithm can also be implemented on a Multi-Mesh network (1999, D. Das, M. De, and B. P. Sinha, IEEE Trans. Comput.48, 536–551) to sort N elements in 54N^1/4+o(N^1/4) steps, which shows an improvement over 58N^1/4+o(N^1/4) steps needed by the algorithm in (1997, M. De, D. Das, M. Ghosh, and P. B. Sinha, IEEE Trans. Comput.46, 1132–1137).     

Predicting guild commitment in World of Warcraft with the investment model of commitment

Many MMORPG offer players the possibility to become a member of a guild, a hierarchical organization of characters with common objectives. Guild membership can be beneficial to game progress, and offer opportunities for social interaction. In the current study we focus on the MMORPG World of Warcraft (WoW), with the main aim to examine whether guild commitment and players’ intention to remain in their guild can be predicted by players’ satisfaction, investments, and perceptions of alternatives to their guild. To this end, 165 WoW players completed an online questionnaire and answered questions related to their guild membership. They also completed the investment model scale which was reworded so all questions pertained to their guild and their fellow guild members. Results show that satisfaction level, quality of alternatives, and investment size significantly predict commitment level (p’s < .001), which in turn predicted likelihood of participants’ staying with their current guild (p < .001) and the number of guilds they had been a member of in the past (p < .001). Moreover, high levels of guild commitment were indicative of better mental health, whereas weekly hours of game play was negatively related to mental health. In the discussion, we conclude that interdependence theory and the investment model of commitment are applicable to online gaming environments, and we argue that commitment to one’s guild is one factor that could prevent the risks associated with online game play (i.e. problematic use).     

The STO problem is NP-complete

We prove that the problem STO of deciding whether or not a finite setEof term equations is subject to occur-check is in NP.Eis subject to occur-check if the execution of the Martelli–Montanari unification algorithm gives for inputEa setE^′  ∪ {x = t}, wheret ≠ xandxappears int. Aptet al. (1994) proved that STO is NP-hard leaving the problem of NP-completeness open.     

Semantic foundations for generalized rewrite theories

Rewriting logic (RL) is a logic of actions whose models are concurrent systems. Rewrite theories involve the specification of equational theories of data and state structures together with a set of rewrite rules that model the dynamics of concurrent systems. Since its introduction, more than one decade ago, RL has attracted the interest of both theorists and practitioners, who have contributed in showing its generality as a semantic and logical framework and also as a programming paradigm. The experimentation conducted in these years has suggested that some significant extensions to the original definition of the logic would be very useful in practice. These extensions may develop along several dimensions, like the choice of the underlying equational logic, the kind of side conditions allowed in rewrite rules and operational concerns for the execution of certain rewrites. In particular, the Maude system now supports subsorting and conditional sentences in the equational logic for data, and also frozen arguments to block undesired nested rewrites; moreover, it allows equality and membership assertions in rule conditions. In this paper, we give a detailed presentation of the inference rules, model theory, and completeness of such generalized rewrite theories. Our results provide a mathematical semantics for Maude, and a foundation for formal reasoning about Maude specifications.     

Symmetric and symplectic exponentially fitted Runge–Kutta–Nyström methods for Hamiltonian problems

The construction of symmetric and symplectic exponentially fitted modified Runge–Kutta–Nyström (SSEFRKN) methods is considered. Based on the symmetry, symplecticity, and exponentially fitted conditions, new explicit modified RKN integrators with FSAL property are obtained. The new integrators integrate exactly differential systems whose solutions can be expressed as linear combinations of functions from the set { exp(± iωt)}, ω > 0, i² = −1, or equivalently from the set { cos(ωt), sin(ωt)}. The phase properties of the new integrators are examined and their periodicity regions are obtained. Numerical experiments are accompanied to show the high efficiency and competence of the new SSEFRKN methods compared with some highly efficient nonsymmetric symplecti EFRKN methods in the literature.     

Approximate Solutions of Polynomial Equations

In this paper, we introduce “approximate solutions" to solve the following problem: given a polynomial F(x, y) over Q, where x represents an n -tuple of variables, can we find all the polynomials G(x) such that F(x, G(x)) is identically equal to a constant c in Q ? We have the following: let F(x, y) be a polynomial over Q and the degree of y in F(x, y) be n. Either there is a unique polynomial g(x)  ∈ Q [ x ], with its constant term equal to 0, such that F(x, y)  = ∑_j = 0ⁿc_j(y − g(x))^jfor some rational numbers c_j, hence, F(x, g(x)  + a)  ∈ Q for all a ∈ Q, or there are at most t distinct polynomials g₁(x),⋯ , g_t(x), t ≤ n, such that F(x, g_i(x))  ∈ Q for 1  ≤ i ≤ t. Suppose that F(x, y) is a polynomial of two variables. The polynomial g(x) for the first case, or g₁(x),⋯ , g_t(x) for the second case, are approximate solutions of F(x, y), respectively. There is also a polynomial time algorithm to find all of these approximate solutions. We then use Kronecker’s substitution to solve the case of F(x, y).     

A distance-based aggregation approach for group decision making with interval preference orderings

Xu (2013) proposed a nonlinear programming model to derive an exact formula to determine the experts’ relative importance weights for the group decision making (GDM) with interval preference orderings. However, in this study, we show that the exact formula to determine the weight vector which always equals to w = (1/m, 1/m, … , 1/m)^T (m is the number of experts). In this paper, we propose a distance-based aggregation approach to assess the relative importance weights for GDM with interval preference orderings. Relevant theorems are offered to support the proposed approach. After that, by using the weighted arithmetic averaging operator, we obtain the aggregated virtual interval preference orderings. We propose a possibility degree formula to compare two virtual interval preference orderings, then rank and select the alternatives. The proposed method is tested by two numerical examples. Comparative analysis are provided to show the advantages and effectiveness of the proposed method.     

Fuzzy model tuning using simulated annealing

This paper presents the use of simulated annealing metaheuristic for tuning Mamdani type fuzzy models. Structure of the Mamdani fuzzy model is learned from input–output data pairs using Wang and Mendel’s method and fuzzy c-means clustering algorithm. Then, parameters of the fuzzy system are tuned through simulated annealing. In this paper, we perform experiments to examine effects of (a) initial solution generated by Wang and Mendel’s method and fuzzy c-means clustering method, (b) membership function update procedure, (c) probability parameter for the calculation of the initial temperature, (d) temperature update coefficient used for cooling schedule, and (e) randomness level in the disturbance mechanism used in simulated annealing algorithm on the tuning of Mamdani type fuzzy models. Experiments are performed with Mackey–Glass chaotic time series. The results indicate that Wang and Mendel’s method provides better starting configuration for simulated annealing compared to fuzzy c-means clustering method, and for the membership function update parameter, MFChangeRate ∈  (0, 1], and the probability parameter for the calculation of the initial temperature, P₀ ∈  (0, 1), values close to zero produced better results.     

Perpetuality and Uniform Normalization in Orthogonal Rewrite Systems

We study perpetuality of reduction steps, as well as perpetuality of redexes, in orthogonal rewrite systems. A perpetual step is a reduction step which retains the possibility of infinite reductions. A perpetual redex is a redex which, when put into an arbitrary context, yields a perpetual step. We generalize and refine existing criteria for the perpetuality of reduction steps and redexes in orthogonal term rewriting systems and the λ-calculus due to Bergstra and Klop and others. We first introduce context-sensitive conditional expression reduction systems (CCERSs) and define a concept of orthogonality (which implies confluence) for them. In particular, several important λ-calculi and their extensions and restrictions can naturally be embedded into orthogonal CCERSs. We then define a perpetual reduction strategy which enables one to construct minimal (w.r.t. Lévy's permutation ordering on reductions) infinite reductions in orthogonal fully-extended CCERSs. Using the properties of the minimal perpetual strategy, we prove   1. perpetuality of any reduction step that does not erase potentially infinite arguments, which are arguments that may become, via substitution, infinite after a number of outside steps, and   2. perpetuality (in every context) of any safe redex, which is a redex whose substitution instances may discard infinite arguments only when the corresponding contracta remain infinite.  We prove both these perpetuality criteria for orthogonal fully-extended CCERSs and then specialize and apply them to restricted λ-calculi, demonstrating their usefulness. In particular, we prove the equivalence of weak and strong normalization (whose equivalence is here called uniform normalization) for various restricted λ-calculi, most of which cannot be derived from previously known perpetuality criteria.     

Glaucoma detection using adaptive neuro-fuzzy inference system

Purpose. To develop an automated classifier based on adaptive neuro-fuzzy inference system (ANFIS) to differentiate between normal and glaucomatous eyes from the quantitative assessment of summary data reports of the Stratus optical coherence tomography (OCT) in Taiwan Chinese population.Methods. This observational non-interventional, cross-sectional, case–control study included one randomly selected eye from each of the 341 study participants (135 patients with glaucoma and 206 healthy controls). Measurements of glaucoma variables (retinal nerve fiber layer thickness and optic nerve head topography) were obtained by Stratus OCT. Decision making was performed in two stages: feature extraction using the orthogonal array and the selected variables were treated as the feeder to adaptive neuro-fuzzy inference system (ANFIS), which was trained with the back-propagation gradient descent method in combination with the least squares method. With the Stratus OCT parameters used as input, receiver operative characteristic (ROC) curves were generated by ANFIS to classify eyes as either glaucomatous or normal.Results. The mean deviation was −0.67 ± 0.62 dB in the normal group and −5.87 ± 6.48 dB in the glaucoma group (P < 0.0001). The inferior quadrant thickness was the best individual parameter for differentiating between normal and glaucomatous eyes (ROC area, 0.887). With ANFIS technique, the ROC area was increased to 0.925.Conclusions. With Stratus OCT parameters used as input, the results from ANFIS showed promise for discriminating between glaucomatous and normal eyes. ANFIS may be preferable since the output concludes the if–then rules and membership functions, which enhances the readability of the output.     

Differentiation of online text-based advertising and the effect on users’ click behavior

Online syndicated text-based advertising is ubiquitous on news sites, blogs, personal websites, and on search result pages. Until recently, a common distinguishing feature of these text-based advertisements has been their background color. Following intervention by the Federal Trade Commission (FTC), the format of these advertisements has undergone a subtle change in their design and presentation. Using three empirical experiments, we investigate the effect of industry-standard advertising practices on click rates, and demonstrate changes in user behavior when this familiar differentiator is modified. Using three large-scale experiments (N₁ = 101, N₂ = 84, N₃ = 176) we find that displaying advertisement and content results with a differentiated background results in significantly lower click rates. Our results demonstrate the strong link between background color differentiation and advertising, and reveal how alternative differentiation techniques influence user behavior.     

Gröbner Bases Applied to Finitely Generated Field Extensions

Using a constructive field-ideal correspondence it is shown how to compute the transcendence degree and a (separating) transcendence basis of finitely generated field extensionsk (x) / k(g), resp. how to determine the (separable) degree if k(x) / k(g) is algebraic. Moreover, this correspondence is used to derive a method for computing minimal polynomials and deciding field membership. Finally, a connection between certain intermediate fields of k(x) / k(g) and a minimal primary decomposition of a suitable ideal is described. For Galois extensions the field-ideal correspondence can also be used to determine the elements of the Galois group.     

Permutation rewriting and algorithmic verification

We propose a natural subclass of regular languages (Alphabetic Pattern Constraints, APC) which is effectively closed under permutation rewriting, i.e., under iterative application of rules of the form ab → ba. It is well-known that regular languages do not have this closure property, in general. Our result can be applied for example to regular model checking, for verifying properties of parametrized linear networks of regular processes, and for modeling and verifying properties of asynchronous distributed systems. We also consider the complexity of testing membership in APC and show that the question is complete for PSPACE when the input is an NFA, and complete for NLOGSPACE when it is a DFA. Moreover, we show that both the inclusion problem and the question of closure under permutation rewriting are PSPACE-complete when we restrict to the class APC.     

Evaluation of a non-point source pollution model,AnnAGNPS, in a tropical watershed

Impaired water quality caused by human activity and the spread of invasive plant and animal species has been identified as a major factor of degradation of coastal ecosystems in the tropics. The main goal of this study was to evaluate the performance of AnnAGNPS (Annualized Non-Point Source Pollution Model), in simulating runoff and soil erosion in a 48 km² watershed located on the Island of Kauai, Hawaii. The model was calibrated and validated using 2 years of observed stream flow and sediment load data. Alternative scenarios of spatial rainfall distribution and canopy interception were evaluated. Monthly runoff volumes predicted by AnnAGNPS compared well with the measured data (R² = 0.90, P < 0.05); however, up to 60% difference between the actual and simulated runoff were observed during the driest months (May and July). Prediction of daily runoff was less accurate (R² = 0.55, P < 0.05). Predicted and observed sediment yield on a daily basis was poorly correlated (R² = 0.5, P < 0.05). For the events of small magnitude, the model generally overestimated sediment yield, while the opposite was true for larger events. Total monthly sediment yield varied within 50% of the observed values, except for May 2004. Among the input parameters the model was most sensitive to the values of ground residue cover and canopy cover. It was found that approximately one third of the watershed area had low sediment yield (0–1 t ha⁻¹ y⁻¹), and presented limited erosion threat. However, 5% of the area had sediment yields in excess of 5 t ha⁻¹ y⁻¹. Overall, the model performed reasonably well, and it can be used as a management tool on tropical watersheds to estimate and compare sediment loads, and identify “hot spots” on the landscape.     

Graph Isomorphism is in SPP

We show that Graph Isomorphism is in the complexity class SPP, and hence it is in ⊕P (in fact, in Mod_kP for each k ⩾ 2). These inclusions for Graph Isomorphism were not known prior to membership in SPP. We derive this result as a corollary of a more general result: we show that a generic problem FIND-GROUP has an FP^SPP algorithm. This general result has other consequences: for example, it follows that the hidden subgroup problem for permutation groups, studied in the context of quantum algorithms, has an FP^SPP algorithm. Also, some other algorithmic problems over permutation groups known to be at least as hard as Graph Isomorphism (e.g., coset intersection) are in SPP, and thus in Mod_kP for each k ⩾ 2.     

Composing Power Series Over a Finite Ring in Essentially Linear Time

Fix a finite commutative ringR. Letuandvbe power series overR, withv(0) = 0. This paper presents an algorithm that computes the firstnterms of the compositionu(v), given the firstnterms ofuandv, inn^1 + o(1)ring operations. The algorithm is very fast in practice whenRhas small characteristic.