Lattice-valued fuzzy Turing machines: Computing power, universality and efficiency

In this paper we study fuzzy Turing machines with membership degrees in distributive lattices, which we called them lattice-valued fuzzy Turing machines. First we give several formulations of lattice-valued fuzzy Turing machines, including in particular deterministic and non-deterministic lattice-valued fuzzy Turing machines (l-DTMcs and l-NTMs). We then show that l-DTMcs and l-NTMs are not equivalent as the acceptors of fuzzy languages. This contrasts sharply with classical Turing machines. Second, we show that lattice-valued fuzzy Turing machines can recognize n-r.e. sets in the sense of Bedregal and Figueira, the super-computing power of fuzzy Turing machines is established in the lattice-setting. Third, we show that the truth-valued lattice being finite is a necessary and sufficient condition for the existence of a universal lattice-valued fuzzy Turing machine. For an infinite distributive lattice with a compact metric, we also show that a universal fuzzy Turing machine exists in an approximate sense. This means, for any prescribed accuracy, there is a universal machine that can simulate any lattice-valued fuzzy Turing machine on it with the given accuracy. Finally, we introduce the notions of lattice-valued fuzzy polynomial time-bounded computation (lP) and lattice-valued non-deterministic fuzzy polynomial time-bounded computation (lNP), and investigate their connections with P and NP. We claim that lattice-valued fuzzy Turing machines are more efficient than classical Turing machines.     

Approximate decidability in euclidean spaces

We study concepts of decidability (recursivity) for subsets of Euclidean spaces ?^k within the framework of approximate computability (type two theory of effectivity). A new notion of approximate decidability is proposed and discussed in some detail. It is an effective variant of F. Hausdorff's concept of resolvable sets, and it modifies and generalizes notions of recursivity known from computable analysis, formerly used for open or closed sets only, to more general types of sets. Approximate decidability of sets can equivalently be expressed by computability of the characteristic functions by means of appropriately working oracle Turing machines. The notion fulfills some natural requirements and is hereditary under canonical embeddings of sets into spaces of higher dimensions. However, it is not closed under binary union or intersection of sets. We also show how the framework of resolvability and approximate decidability can be applied to investigate concepts of reducibility for subsets of Euclidean spaces.     

Computable analogs of cardinal characteristics: Prediction and rearrangement

There has recently been work by multiple groups in extracting the properties associated with cardinal invariants of the continuum and translating these properties into similar analogous combinatorial properties of computational oracles. Each property yields a highness notion in the Turing degrees. In this paper we study the highness notions that result from the translation of the evasion number and its dual, the prediction number, as well as two versions of the rearrangement number. When translated appropriately, these yield four new highness notions. We will define these new notions, show some of their basic properties and place them in the computability-theoretic version of Cichoń's diagram.     

软群

Molodtsov提出了软集——一种处理不确定性信息的数学工具．本文在进行了阐述软集的相关概念和性质后,接下来给出了软群的定义,并对软群的软同态做了进一步研究．     

软群

Molodtsov提出了软集——一种处理不确定性信息的数学工具.本文在进行了阐述软集的相关概念和性质后,接下来给出了软群的定义,并对软群的软同态做了进一步研究.     

A decision procedure using discrete geometry

A decision procedure is given which makes essential use of concepts in discrete geometry. The procedure decides for any one-state Turing machine with three-dimensional tape, whether or not it has an immortal configuration, i.e., it solves the uniform halting problem for such devices. The history and significance of the problem is examined. The solution is given with the main motivation of showing how traditional mathematical concepts can be used in decision procedures. The paper is introductory in the sense that all notions are carefully defined.     

Power contexts and their concept lattices

We introduce a framework for the study of formal contexts and their lattices induced by the additional structure of self-relations on top of the traditional incidence relation. The induced contexts use subsets as objects and attributes, hence the name power context and power concept. Six types of new incidence relations are introduced by taking into account all possible combinations of universal and existential quantifiers as well as the order of the quantifications in constructing the lifted power contexts. The structure of the power concept lattice is investigated through projection mappings from the baseline objects and attributes to those of the power context, respectively. We introduce the notions of extensional consistency and intensional consistency, corresponding to the topological notions of continuity in the analogous setting when concepts are viewed as closed sets. We establish Galois connections for these notions of consistency. We further introduce the notion of faithfulness for the first type of lifted incidence relation based on the fact that it can be equivalently characterized by a concept-faithful morphism. We also present conditions under which the power concept lattice serves as a factor lattice of the base concept lattice.     

Pattern formation in reaction-diffusion neural networks with leakage delay

Due to the heterogeneity of the electromagnetic field in neural networks, the diffusion phenomenon of electrons exists inevitably. In this paper, we investigate pattern formation in a reaction-diffusion neural network with leakage delay. The existence of Hopf bifurcation, as well as the necessary and sufficient conditions for Turing instability, are studied by analyzing the corresponding characteristic equation. Based on the multiple-scale analysis, amplitude equations of the model are derived, which determine the selection and competition of Turing patterns. Numerical simulations are carried out to show the possible patterns and how these patterns evolve. In some cases, the stability performance of Turing patterns is weakened by leakage delay and synaptic transmission delay.     

Generalized periodicity and primitivity for words

Starting from six kinds of periodicity of words we define six sets of words which are primitive in different senses and we investigate their relationships. We show that only three of the sets are external Marcus contextual languages with choice but none of them is an external contextual language without choice or an internal contextual language. For the time complexity of deciding any of our sets by one-tape Turing machines, n ² is a lower bound and this is optimal in two cases. The notions of roots and degrees of words and languages, which are strongly connected to periodicity and primitivity, are also considered, and we show that there can be an arbitrarily large gap between the complexity of a language and that of its roots. (© 2007 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Schnorr trivial reals: a construction

A real is Martin-Löf (Schnorr) random if it does not belong to any effectively presented null ${\Sigma^0_1}A real is Martin-L?f (Schnorr) random if it does not belong to any effectively presented null (recursive) class of reals. Although these randomness notions are very closely related, the set of Turing degrees containing reals that are K-trivial has very different properties from the set of Turing degrees that are Schnorr trivial. Nies proved in (Adv Math 197(1):274–305, 2005) that all K-trivial reals are low. In this paper, we prove that if , then h contains a Schnorr trivial real. Since this concept appears to separate computational complexity from computational strength, it suggests that Schnorr trivial reals should be considered in a structure other than the Turing degrees. This material is based upon work supported under a National Science Foundation Graduate Research Fellowship and appears in the author’s Ph.D. thesis. A preliminary version of this paper appeared in Electronic Notes in Theoretical Computer Science     

一类具扩散的Ivlev型捕食模型

研究一类具有扩散的Ivlev型捕食模型.首先利用线性化和特征值法给出正平衡解在常微分系统和加入自扩散的弱耦合偏微分系统下的局部渐近稳定性,其次,讨论在加入交错扩散的强耦合系统下会引起平衡解的Turing不稳定,最后给出数值模拟验证理论结果.     

Kolmogorov complexity and characteristic constants of formal theories of arithmetic

We investigate two constants c _T and r _T , introduced by Chaitin and Raatikainen respectively, defined for each recursively axiomatizable consistent theory T and universal Turing machine used to determine Kolmogorov complexity. Raatikainen argued that c _T does not represent the complexity of T and found that for two theories S and T , one can always find a universal Turing machine such that $c_\mathbf {S}= c_\mathbf {T}$. We prove the following are equivalent: $c_\mathbf {S}\ne c_\mathbf {T}$ for some universal Turing machine, $r_\mathbf {S}\ne r_\mathbf {T}$ for some universal Turing machine, and T proves some Π₁‐sentence which S cannnot prove. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Measurement structures with archimedean ordered translation groups

The paper focuses on three problems of generalizing properties of concatenation structures (ordered structures with a monotonic operation) to ordered structures lacking any operation. (1) What is the natural generalization of the idea of Archimedeaness, of commensurability between large and small? (2) What is the natural generalization of the concept of a unit concatenation structure in which the translations (automorphisms with no fixed point) can be represented by multiplication by a constant? (3) What is the natural generalization of a ratio scale concatenation structure being distributive in a conjoint one, which has been shown to force a multiplicative representation of the latter and the product-of-powers representation of units found in physics? It is established (Theorems 5.1 and 5.2) that for homogeneous structures, the latter two questions are equivalent to it having the property that the set of all translations forms a homogeneous Archimedean ordered group. A sufficient condition for Archimedeaness of the translations is that they form a group, which is equivalent to their being 1-point unique, and the structure be Dedekind complete and order dense (Theorems 2.1 and 2.2). It is suggested that Archimedean order of the translations is, indeed, also the answer to the first question. As a lead into that conclusion, a number of results are reported in Section 3 on Archimedeaness in concatenation structures, including for positive structures sufficient conditions for several different notions of Archimedeaness to be equivalent. The results about idempotent structures are fragmentary.     

Bifurcations and spatiotemporal patterns in a ratio‐dependent diffusive Holling‐Tanner system with time delay

In this paper, we concentrate on the spatiotemporal patterns of a delayed reaction‐diffusion Holling‐Tanner model with Neumann boundary conditions. In particular, the time delay that is incorporated in the negative feedback of the predator density is considered as one of the principal factors to affect the dynamic behavior. Firstly, a global Turing bifurcation theorem for τ = 0 and a local Turing bifurcation theorem for τ > 0 are given. Then, further considering the degenerated situation, we derive the existence of Bogdanov‐Takens bifurcation and Turing‐Hopf bifurcation. The normal form method is used to study the explicit dynamics near the Turing‐Hopf singularity. It is shown that a pair of stable nonconstant steady states (stripe patterns) and a pair of stable spatially inhomogeneous periodic solutions (spot patterns) could be bifurcated from a positive equilibrium. Moreover, the Turing‐Turing‐Hopf–type spatiotemporal patterns, that is, a subharmonic phenomenon with two spatial wave numbers and one temporal frequency, are also found and explained theoretically. Our results imply that the interaction of Turing and Hopf instabilities can be considered as the simplest mechanism for the appearance of complex spatiotemporal dynamics.     

A Solution Concept for Fuzzy Multiobjective Programming Problems Based on Convex Cones

A solution concept for fuzzy multiobjective programming problems based on ordering cones (convex cones) is proposed in this paper. The notions of ordering cones and partial orderings on a vector space are essentially equivalent. Therefore, the optimality notions in a real vector space can be elicited naturally by invoking a concept similar to that of the Pareto-optimal solution in vector optimization problems. We introduce a corresponding multiobjective programming problem and a weighting problem of the original fuzzy multiobjective programming problem using linear functionals so that the optimal solution of its corresponding weighting problem is also the Pareto-optimal solution of the original fuzzy multiobjective programming problem.     

Hyponormal and strongly hyponormal matrices in inner product spaces

Complex matrices that are structured with respect to a possibly degenerate indefinite inner product are studied. Based on earlier works on normal matrices, the notions of hyponormal and strongly hyponormal matrices are introduced. A full characterization of such matrices is given and it is shown how those matrices are related to different concepts of normal matrices in degenerate inner product spaces. Finally, the existence of invariant semidefinite subspaces for strongly hyponormal matrices is discussed.     

COILS FOR VECTORSPACE CATEGORIES

Coils as components of Auslander–Reiten quivers of algebras and coil algebras are introduced by Assem and Skowroński. This concept is applied in the present paper to vectorspace categories. The four admissible operations on an Auslander–Reiten component of a vectorspace category, and the notions of v-coils and of vcoil vectorspace categories are introduced. A detailed study on the indecomposable objects of factorspace category of a vcoil vectorspace category is carried out.     

Time considered irrelevant for real-time systems

Various manifestations of the time-as-a-proxy phenomenon in specification of computing problems are considered. It is argued that unless the time-related considerations constitute an essential part of natural (physical) problems, safer specifications are obtained from avoiding short-cuts offered by introduction of time-related notions. This methodological principle is illustrated by examples from several fields: digital control and simulation, design of operator's interface and communication protocols.Dedicated to Peter Naur on the occasion of his 60th birthday