Complexity of some natural problems in automatic structures

We prove that the automatic isomorphism problem for automatic structures, the automatic automorphism problem for an automatic structure, and the automatic embedding problem for automatic structures are $ \overset{\lower0.5em\hbox{$ \overset{\lower0.5em\hbox{ Matematicheski $ \overset{\lower0.5em\hbox{$ \overset{\lower0.5em\hbox{ Zhurnal, Vol. 46, No. 1, pp. 71–78, January–February, 2005.     

On the complexity of categoricity in computable structures

We investigate the computational complexity the class of Γ‐categorical computable structures. We show that hyperarithmetic categoricity is Π¹₁‐complete, while computable categoricity is Π⁰₄‐hard. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Computational complexity of reconstruction and isomorphism testing for designs and line graphs

Graphs with high symmetry or regularity are the main source for experimentally hard instances of the notoriously difficult graph isomorphism problem. In this paper, we study the computational complexity of isomorphism testing for line graphs of t-(v,k,λ) designs. For this class of highly regular graphs, we obtain a worst-case running time of O(vlogv+O(1)) for bounded parameters t, k, λ.In a first step, our approach makes use of the Babai-Luks algorithm to compute canonical forms of t-designs. In a second step, we show that t-designs can be reconstructed from their line graphs in polynomial-time. The first is algebraic in nature, the second purely combinatorial. For both, profound structural knowledge in design theory is required. Our results extend earlier complexity results about isomorphism testing of graphs generated from Steiner triple systems and block designs.     

Performance analysis of linear and nonlinear techniques for automatic scaling of discretized control problems

This paper introduces three (one linear and two nonlinear) automatic scaling techniques for NLPs with states and constraints spread over several orders of magnitude, without requiring complex off-the-shelf external tools. All of these methods have been compared to standard techniques and applied to three problems using SNOPT and IPOPT. The results confirm that the proposed techniques significantly improve the NLP conditioning, yielding more reliable and in some cases, faster NLP solutions.     

Index sets of classes of automatic structures

We obtain exact estimates in the arithmetical and analytical hierarchies of index sets of various classes of automatic models. We also obtain estimates for the existence problems for computable isomorphism and embedding of automatic structures.     

Ideal polytopes and face structures of some combinatorial optimization problems

Given a finite setX and a family of feasible subsetsF ofX, the 0–1 polytope P (F is defined as the convex hull of all the characteristic vectors of members ofF We show that under a certain assumption a special type of face ofP(F) is equivalent to the ideal polytope of some pseudo-ordered set. Examples of families satisfying the assumption are those related to the maximum stable set problem, set packing and set partitioning problems, and vertex coloring problem. Using this fact, we propose a new heuristic for such problems and give results of our preliminary computational experiments for the maximum stable set problem.Supported by a JSPS Fellowship for Young Scientists.Supported by Grant-in-Aids for Co-operative Research (06740147) of the Ministry of Education, Science and Culture.     

Nilpotent Lie Algebras of Maximal Rank and of Kac–Moody Type: E6

Let be the Kac–Moody algebra associated to the affine Cartan matrix E₆⁽¹⁾. Each nilpotent Lie algebra of type E₆⁽¹⁾ is isomorphic to a quotient of the positive part of . We determine the isomorphism classes of nilpotent Lie algebras of type E₆⁽¹⁾.     

Uniqueness of solutions to inverse Sturm–Liouville problems with potential using three spectra

The uniqueness of solutions to two inverse Sturm–Liouville problems using three spectra is proven, based on the uniqueness of the solution-pair to an overdetermined Goursat–Cauchy boundary value problem. We discuss the uniqueness of the potential for a Dirichlet boundary condition at an arbitrary interior node, and for a Robin boundary condition at an arbitrary interior node, whereas at the exterior nodes we have Dirichlet boundary conditions in both situations. Here we are particularly concerned with potential functions that are L²(0,a).     

A finite element approach for analysis and computational modelling of coupled reaction diffusion models

In this article, we establish the existence and uniqueness of solutions to the coupled reaction–diffusion models using Banach fixed point theorem. The Galerkin finite element method is used for the approximation of solutions, and an a priori error estimate is derived for such approximations. A scheme is proposed by combining the Crank–Nicolson and the predictor–corrector methods for the time discretization. Some numerical examples are considered to illustrate the accuracy and efficiency of the proposed scheme. It is found that the scheme is second‐order convergent. In addition, nonuniform grids are used in some cases to enhance the accuracy of the scheme.     

Reversible coagulation–fragmentation processes and random combinatorial structures: Asymptotics for the number of groups

The equilibrium distribution of a reversible coagulation‐fragmentation process (CFP) and the joint distribution of components of a random combinatorial structure (RCS) are given by the same probability measure on the set of partitions. We establish a central limit theorem for the number of groups (= components) in the case a(k) = qk^p?1, k ≥ 1, q, p > 0, where a(k), k ≥ 1, is the parameter function that induces the invariant measure. The result obtained is compared with the ones for logarithmic RCS's and for RCS's, corresponding to the case p < 0. © 2004 Wiley Periodicals, Inc. Random Struct. Alg. 2004     

Wave operator for the system of the Dirac–Klein–Gordon equations

We prove the existence of the wave operator for the system of the massive Dirac–Klein–Gordon equations in three space dimensions x∈ R ³ where the masses m, M>0. We prove that for the small final data , (?, ?)∈ H ^{2 + µ, 1} × H ^{1 + µ, 1}, with and , there exists a unique global solution for system (1) with the final state conditions Copyright © 2010 John Wiley & Sons, Ltd.     

Multiplicity of nontrivial solutions to a biharmonic equation via Lusternik–Schnirelman theory

In this paper, we are concerned with the multiplicity of nontrivial solutions for the following class of biharmonic problem where is a bounded domain with smooth boundary. Using the Lusternik–Schnirelman theory, we relate the number of solutions with the topology of Ω. Copyright © 2012 John Wiley & Sons, Ltd.     

The compact and noncompact structures for two types of generalized Camassa–Holm–KP equations

The objective of this paper is to investigate two types of generalized nonlinear Camassa–Holm–KP equations in (2+1) dimensional space. Compactons, solitons, solitary patterns, periodic solutions and algebraic travelling wave solutions are expressed analytically under various circumstances. The conditions that cause the qualitative change in the physical structures of the solutions are emphasized.     

Worst case complexity of multivariate Feynman–Kac path integration

We study the multivariate Feynman–Kac path integration problem. This problem was studied in Plaskota et al. (J. Comp. Phys. 164 (2000) 335) for the univariate case. We describe an algorithm based on uniform approximation, instead of the L₂-approximation used in Plaskota et al. (2000). Similarly to Plaskota et al. (2000), our algorithm requires extensive precomputing. We also present bounds on the complexity of our problem. The lower bound is provided by the complexity of a certain integration problem, and the upper bound by the complexity of the uniform approximation problem. The algorithm presented in this paper is almost optimal for the classes of functions for which uniform approximation and integration have roughly the same complexities.     

Boundary-Value Problems for Second-Order Equations and for Systems of First-Order Equations

The oblique derivative problem for harmonic functions under violation of the Shapiro–Lopatinsky condition is considered as well as some multi-dimensional analogues of the Cauchy–Riemann system. These problems are reduced to nonelliptic pseudo-differential equations. A method generalizing the regularization of singular integral equations is also presented.     

A Multidimensional Singular Boundary Value Problem of the Cauchy–Nicoletti Type

A two-point singular boundary value problem of the Cauchy–Nicoletti type is studied by introducing a two-point boundary value set and using the topological principle. The results on the existence of solutions whose graph lies in this set are proved. Applications and comparisons to the known results are given, too.     

Complete systems of recursive integrals and Taylor series for solutions of Sturm–Liouville equations

Given a regular nonvanishing complex valued solution y₀ of the equation , x ∈ (a,b), assume that it is n times differentiable at a point x₀ ∈ [a,b]. We present explicit formulas for calculating the first n derivatives at x₀ for any solution of the equation . That is, a map transforming the Taylor expansion of y₀ into the Taylor expansion of u is constructed. The result is obtained with the aid of the representation for solutions of the Sturm‐Liouville equation in terms of spectral parameter power series. Copyright © 2012 John Wiley & Sons, Ltd.     

Cayley Graphs of Diameter Two from Difference Sets

Let and be the largest order of a Cayley graph and a Cayley graph based on an abelian group, respectively, of degree d and diameter k. When , it is well known that with equality if and only if the graph is a Moore graph. In the abelian case, we have . The best currently lower bound on is for all sufficiently large d. In this article, we consider the construction of large graphs of diameter 2 using generalized difference sets. We show that for sufficiently large d and if , and m is odd.