The Undecidability of the First-Order Theories of One Step Rewriting in Linear Canonical Systems

By reduction from the halting problem for Minsky's two-register machines we prove that there is no algorithm capable of deciding the -theory of one step rewriting of an arbitrary finite linear confluent finitely terminating term rewriting system (weak undecidability). We also present a fixed such system with undecidable *-theory of one step rewriting (strong undecidability). This improves over all previously known results of the same kind.     

The ** Part of the Theory of Ground Term Algebra Modulo an AC Symbol is Undecidable

We show that the ** part of the equational theory modulo an AC symbol is undecidable. This solves the open problem 25 from the RTA list. We show that this result holds also for the equational theory modulo an ACI symbol.     

A Logic for Reasoning about Generic Judgments

This paper presents an extension of a proof system for encoding generic judgments, the logic FOλ^Δ of Miller and Tiu, with an induction principle. The logic FOλ^Δ is itself an extension of intuitionistic logic with fixed points and a “generic quantifier”, , which is used to reason about the dynamics of bindings in object systems encoded in the logic. A previous attempt to extend FOλ^Δ with an induction principle has been unsuccessful in modeling some behaviours of bindings in inductive specifications. It turns out that this problem can be solved by relaxing some restrictions on , in particular by adding the axiom B≡x.B, where x is not free in B. We show that by adopting the equivariance principle, the presentation of the extended logic can be much simplified. Cut-elimination for the extended logic is stated, and some applications in reasoning about an object logic and a simply typed λ-calculus are illustrated.     

On Some Schützenberger Conjectures

In this paper we consider factorizing codes C over A, i.e., codes verifying the factorization conjecture by Schützenberger. Let n be the positive integer such that aⁿC, we show how we can construct C starting with factorizing codes C′ with a^n′C′ and n′ < n, under the hypothesis that all words aⁱza^j in C, with z(A\a)A*(A\a) (A\a), satisfy i, j, > n. The operation involved, already introduced by Anselmo, is also used to show that all maximal codes C=P(A−1)S+1 with P, SZA and P or S in Za can be constructed by means of this operation starting with prefix and suffix codes. Old conjectures by Schützenberger have been revised.     

Drag and lift coefficients of inclined finite circular cylinders at moderate Reynolds numbers

The flow around two-dimensional cylinders at moderate Reynolds numbers has been much studied, both for cylinders perpendicular to the flow and for cylinders yawed to the flow. In contrast, yawed finite aspect ratio cylinders have received little attention. In this article we describe computer simulations of cylinders with aspect ratios 2  L/D  20 yawed at angles 0°  α  90° relative to a free stream. The simulations were carried out for Reynolds numbers in the range 1  Re  40. The simulations show that the Independence Principle [Zdravkovich MM. Flow around circular cylinders, vol. 2: applications. New York: Oxford University Press; 2003[1]] is not accurate for α  45°. We have also found that for all aspect ratios, the ratio of the lift to drag force reaches a maximum for 40° < α < 50°. Finally, we present C_L and C_D relationships as best curve fits to computational data.     

Long paths in hypercubes with a quadratic number of faults

A path between distinct vertices u and v of the n-dimensional hypercube Q_n avoiding a given set of f faulty vertices is called long if its length is at least 2ⁿ-2f-2. We present a function (n)=Θ(n²) such that if f(n) then there is a long fault-free path between every pair of distinct vertices of the largest fault-free block of Q_n. Moreover, the bound provided by (n) is asymptotically optimal. Furthermore, we show that assuming f(n), the existence of a long fault-free path between an arbitrary pair of vertices may be verified in polynomial time with respect to n and, if the path exists, its construction performed in linear time with respect to its length.     

Predicate Abstraction for Dense Real-Time Systems

We propose predicate abstraction as a means for verifying a rich class of safety and liveness properties for dense real-time systems. First, we define a restricted semantics of timed systems which is observationally equivalent to the standard semantics in that it validates the same set of μ-calculus formulas without a next-step operator. Then, we recast the model checking problem S for a timed automaton S and a μ-calculus formula in terms of predicate abstraction. Whenever a set of abstraction predicates forms a so-called basis, the resulting abstraction is strongly preserving in the sense that S validates iff the corresponding finite abstraction validates this formula . Now, the abstracted system can be checked using familiar μ-calculus model checking. Like the region graph construction for timed automata, the predicate abstraction algorithm for timed automata usually is prohibitively expensive. In many cases it suffices to compute an approximation of a finite bisimulation by using only a subset of the basis of abstraction predicates. Starting with some coarse abstraction, we define a finite sequence of refined abstractions that converges to a strongly preserving abstraction. In each step, new abstraction predicates are selected nondeterministically from a finite basis. Counterexamples from failed μ-calculus model checking attempts can be used to heuristically choose a small set of new abstraction predicates for refining the abstraction.     

Liquid–solid equilibria in quinary system Na,Mg/Cl,SO4,NO3–H2O at 298.15 K

In order to develop the nitrate deposits found close to Lop Nur in the Xinjiang region in China, the solubilities of the system Na⁺,Mg²⁺/Cl⁻,SO₄²⁻, NO₃⁻–H₂O and its subsystems, the quaternary systems Na⁺,Mg²⁺/SO₄²⁻,NO₃⁻–H₂O and Mg²⁺/Cl⁻,SO₄²⁻,NO₃⁻–H₂O, were studied at 298.15 K. The phase diagrams were plotted according to the solubilities achieved. In the equilibrium phase diagram of Mg²⁺/Cl⁻,SO₄²⁻,NO₃⁻–H₂O, there are two invariant points, five univariant curves and four regions of crystallization: Mg(NO₃)₂6H₂O,MgCl₂6H₂O,MgSO₄7H₂O and MgSO₄(1–6)H₂O. In the equilibrium phase diagram of Na⁺,Mg²⁺/SO₄²⁻, NO₃⁻–H₂O, there are five invariant points, eleven univariant curves and seven regions of crystallization: Na₂SO₄,Na₂SO₄10H₂O,NaNO₃,MgSO₄Na₂SO₄4H₂O,NaNO₃Na₂SO₄2H₂O,Mg(NO₃)₂6H₂O and MgSO₄7H₂O. In the equilibrium phase diagram of the Na⁺, Mg²⁺/Cl⁻,SO₄²⁻,NO₃⁻–H₂O system, there are six invariant points, and ten regions of crystallization: NaCl, NaNO₃,Na₂SO₄,Na₂SO₄10H₂O,MgSO₄Na₂SO₄4H₂O, NaNO₃Na₂SO₄2H₂O,MgCl₂6H₂O,Mg(NO₃)₂6H₂O, MgSO₄(1–6)H₂O and MgSO₄7H₂O.     

A generalization of ACP using Belnap’s logic

ACP is combined with Belnap’s four-valued logic via conditional composition (if–then–else). We show that the operators of ACP can be seen as instances of more general, conditional operators. For example, both the choice operator + and δ (deadlock) can be seen as instances of conditional composition, and the axiom x + δ = x follows from this perspective. Parallel composition is generalized to the binary conditional merge _ψ where covers the choice between interleaving and synchronization, and ψ determines the order of execution. The instance _BB is ACP’s parallel composition, where B (both) is the truth value that models both true and false in Belnap’s logic. Other instances of this conditional merge are sequential composition, pure interleaving and synchronous merge. We investigate the expression of scheduling strategies in the conditions of the conditional merge.     

Modelling Generic Judgements

We propose a semantics for the -quantifier of Miller and Tiu. First we consider the case for classical first-order logic. In this case, the interpretation is close to standard Tarski-semantics and completeness can be shown using a standard argument. Then we put our semantics into a broader context by giving a general interpretation of in categories with binding structure. Since categories with binding structure also encompass nominal logic, we thus show that both -logic and nominal logic can be modelled using the same definition of binding. As a special case of the general semantics in categories with binding structure, we recover Gabbay & Cheney's translation of FOλ into nominal logic.     

Thermostable tensoresistors of Co doped GaSb–FeGa1.3 eutectic composites

The microstructure and tensoresistive properties of GaSb–FeGa_1.3 eutectic composites doped with 0.1% Co have been investigated. It was found that the Co impurity atoms mainly accumulate in the metallic inclusions. The length of the inclusions in GaSb–FeGa_1.3Co was measured to be about half of those in undoped GaSb–FeGa_1.3 eutectics. The tensometric characteristics of gauges based on GaSb–FeGa_1.3Co have been found to be more thermostable than undoped samples.     

Interactions Between PVS and Maple in Symbolic Analysis of Control Systems

This paper presents a decision procedure for problems relating polynomial and transcendental functions. The procedure applies to functions that are continuously differentiable with a finite number of points of inflection in a closed convex set. It decides questions of the form ‘is f0?’, where {=,>,<}. An implementation of the procedure in Maple and PVS exploits the existing Maple, PVS and QEPCAD connections. It is at present limited to those twice differentiable functions whose derivatives are rational functions (rationally differentiable). This procedure is particularly applicable to the analysis of control systems in determining important properties such as stability.     

Reduction of Permutation-Invariant Polynomials: A Noncommutative Case Study

Let R be a commutative ring with 1, let RX₁,…,X_n/I be the polynomial algebra in the n≥4 noncommuting variables X₁,…,X_n over R modulo the set of commutator relations I={(X₁+···+X_n)*X_i=X_i*(X₁+···+X_n)|1≤i≤n}. Furthermore, let G be an arbitrary group of permutations operating on the indeterminates X₁,…,X_n, and let RX₁,…,X_n/I^G be the R-algebra of G-invariant polynomials in RX₁,…,X_n/I. The first part of this paper is about an algorithm, which computes a representation for any fRX₁,…,X_n/I^G as a polynomial in multilinear G-invariant polynomials, i.e., the maximal variable degree of the generators of RX₁,…,X_n/I^G is at most 1. The algorithm works for any ring R and for any permutation group G. In addition, we present a bound for the number of necessary generators for the representation of all G-invariant polynomials in RX₁,…,X_n/I^G with a total degree of at most d. The second part contains a first but promising analysis of G-invariant polynomials of solvable polynomial rings.     

Positive periodic solutions of second-order nonlinear differential systems with two parameters

By employing the Deimling fixed point index theory, we consider a class of second-order nonlinear differential systems with two parameters . We show that there exist three nonempty subsets of : Γ, Δ₁ and Δ₂ such that and the system has at least two positive periodic solutions for (λ,μ)Δ₁, one positive periodic solution for (λ,μ)Γ and no positive periodic solutions for (λ,μ)Δ₂. Meanwhile, we find two straight lines L₁ and L₂ such that Γ lies between L₁ and L₂.     

Approximating the Minimum Chain Completion problem

A bipartite graph G=(U,V,E) is a chain graph [M. Yannakakis, Computing the minimum fill-in is NP-complete, SIAM J. Algebraic Discrete Methods 2 (1) (1981) 77–79] if there is a bijection such that Γ(π(1))Γ(π(2))Γ(π(|U|)), where Γ is a function that maps a node to its neighbors.We give approximation algorithms for two variants of the Minimum Chain Completion problem, where we are given a bipartite graph G(U,V,E), and the goal is find the minimum set of edges F that need to be added to G such that the bipartite graph G^′=(U,V,E^′) (E^′=EF) is a chain graph.     

Inductive Synthesis of Recursive Processes from Logical Properties

This paper proposes an inductive synthesis algorithm for a recursive process. To synthesize a process, facts, which must be satisfied by the target process, are given to the algorithm one by one since such facts are infinitely many in general. When n facts are input to the algorithm, it outputs a process which satisfies the given n facts. And this generating process is repeated infinitely many times. To represent facts of a process, we adopt a subcalculus of μ-calculus. First, we introduce a new preorder _d on recursive processes based on the subcalculus to discuss its properties. p_d q means that pf implies qf, for all formulae f in the subcalculus. Then, its discriminative power and relationship with other preorders are also discussed. Finally, we present the synthesis algorithm. The correctness of the algorithm can be stated that the output sequence of processes by the algorithm converges to a process, which cannot be distinguished from the intended one (if we could know it) by a given enumeration of facts, in the limit. A prototype system based on the algorithm is stated as well.     

Convergence performance comparison of quantum-inspired multi-objective evolutionary algorithms

In recent research, we proposed a general framework of quantum-inspired multi-objective evolutionary algorithms (QMOEA) and gave one of its sufficient convergence conditions to the Pareto optimal set. In this paper, two Q-gate operators, H gate and R&N gate, are experimentally validated as two Q-gate paradigms meeting the convergence condition. The former is a modified rotation gate, and the latter is a combination of rotation gate and NOT gate with the specified probability. To investigate their effectiveness and applicability, several experiments on the multi-objective 0/1 knapsack problems are carried out. Compared to two typical evolutionary algorithms and the QMOEA only with rotation gate, the QMOEA with H gate and R&N gate have more powerful convergence ability in high complex instances. Moreover, the QMOEA with R&N gate has the best convergence in almost all of the experimental problems. Furthermore, the appropriate ε value regions for two Q-gates are verified.     

Isolation concepts for efficiently enumerating dense subgraphs

In an undirected graph G=(V,E), a set of k vertices is called c-isolated if it has less than ck outgoing edges. Ito and Iwama [H. Ito, K. Iwama, Enumeration of isolated cliques and pseudo-cliques, ACM Transactions on Algorithms (2008) (in press)] gave an algorithm to enumerate all c-isolated maximal cliques in O(4^cc⁴|E|) time. We extend this to enumerating all maximal c-isolated cliques (which are a superset) and improve the running time bound to O(2.89^cc²|E|), using modifications which also facilitate parallelizing the enumeration. Moreover, we introduce a more restricted and a more general isolation concept and show that both lead to faster enumeration algorithms. Finally, we extend our considerations to s-plexes (a relaxation of the clique notion), providing a W[1]-hardness result when the size of the s-plex is the parameter and a fixed-parameter algorithm for enumerating isolated s-plexes when the parameter describes the degree of isolation.     

Nonmonotonic Trust Management for P2P Applications

Community decisions about access control in virtual communities are non-monotonic in nature. This means that they cannot be expressed in current, monotonic trust management languages such as the family of Role Based Trust Management languages (RT). To solve this problem we propose RT, which adds a restricted form of negation to the standard RT language, thus admitting a controlled form of non-monotonicity. The semantics of RT is discussed and presented in terms of the well-founded semantics for Logic Programs. Finally we discuss how chain discovery can be accomplished for RT.     

Intervals of solutions of the discrete-time algebraic Riccati equation

If two solutions YZ of the DARE are given then the set of solutions X with YXZ can be parametrized by invariant subspaces of the closed loop matrix corresponding to Y. The paper extends the geometric theory of Willems from the continuous-time to the discrete-time ARE making the weakest possible assumptions.