On computable automorphisms in formal concept analysis

Under study are the automorphism groups of computable formal contexts. We give a general method to transform results on the automorphisms of computable structures into results on the automorphisms of formal contexts. Using this method, we prove that the computable formal contexts and computable structures actually have the same automorphism groups and groups of computable automorphisms. We construct some examples of formal contexts and concept lattices that have nontrivial automorphisms but none of them could be hyperarithmetical in any hyperarithmetical presentation of these structures. We also show that it could be happen that two formal concepts are automorphic but they are not hyperarithmetically automorphic in any hyperarithmetical presentation.     

A uniformly computable Implicit Function Theorem

We prove uniformly computable versions of the Implicit Function Theorem in its differentiable and non‐differentiable forms. We show that the resulting operators are not computable if information about some of the partial derivatives of the implicitly defining function is omitted. Finally, as a corollary, we obtain a uniformly computable Inverse Function Theorem, first proven by M. Ziegler (2006). (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

When series of computable functions with varying domains are computable

In this paper we study the behavior of computable series of computable partial functions with varying domains (but each domain containing all computable points), and prove that the sum of the series exists and is computable exactly on the intersection of the domains when a certain computable Cauchyness criterion is met. In our point‐free approach, we name points via nested sequences of basic open sets, and thus our functions from a topological space into the reals are generated by functions from basic open sets to basic open sets. The construction of a function that produces the sum of a series requires working with an infinite array of pairs of basic open sets, and reconciling the varying domains. We introduce a general technique for using such an array to produce a set function that generates a well‐defined point function and apply the technique to a series to establish our main result. Finally, we use the main finding to construct a computable, and thus continuous, function whose domain is of Lebesgue measure zero and which is nonextendible to a continuous function whose domain properly includes the original domain. (We had established existence of such functions with domains of measure less than ε for any , in an earlier paper.)     

Study of a universal formal context

Studying a universal formal context, we obtain a number of properties of the context itself, its concepts, and the lattice formed by the set of these concepts. The most significant of these properties is represented by a theorem showing that there exists an embedding of the concept lattice of an arbitrary at most countable universal context into the concept lattice of a universal context under which the image of the embedding is an initial segment of the concept set of a universal formal context with infinite volumes, and the validity of the dual result. It is shown that the theorem also holds in the computable case. This theorem demonstrates the complexity of the structure of a universal formal context.     

Block relations in formal fuzzy concept analysis

One of the main problems in formal concept analysis (especially in fuzzy setting) is to reduce a concept lattice of a formal context to appropriate size to make it graspable and understandable. A natural way to do it is to substitute the formal context by its block relation which is equivalent to factorization of the concept lattice by a complete tolerance. We generalize known results on the correspondence of block relations of formal contexts and complete tolerances on concept lattices to fuzzy setting and we provide an illustrative example of using block relations to reduce the size of a concept lattice.     

Uniformity in Computable Structure Theory

We investigate the effects of adding uniformity requirements to concepts in computable structure theory such as computable categoricity (of a structure) and intrinsic computability (of a relation on a computable structure). We consider and compare two different notions of uniformity, previously studied by Kudinov and by Ventsov. We discuss some of their results and establish new ones, while also exploring the connections with the relative computable structure theory of Ash, Knight, Manasse, and Slaman and Chisholm and with previous work of Ash, Knight, and Slaman on uniformity in a general computable structure-theoretical setting.     

Complexity of some natural problems on the class of computable I-algebras

We study computable Boolean algebras with distinguished ideals (I-algebras for short). We prove that the isomorphism problem for computable I-algebras is Σ ₁ ¹ -complete and show that the computable isomorphism problem and the computable categoricity problem for computable I-algebras are Σ ₃ ⁰ -complete.     

The computable embedding problem

Calvert calculated the complexity of the computable isomorphism problem for a number of familiar classes of structures. Rosendal suggested that it might be interesting to do the same for the computable embedding problem. By the computable isomorphism problem and (computable embedding problem) we mean the difficulty of determining whether there exists an isomorphism (embedding) between two members of a class of computable structures. For some classes, such as the class of \mathbbQ \mathbb{Q} -vector spaces and the class of linear orderings, it turns out that the two problems have the same complexity. Moreover, calculations are essentially the same. For other classes, there are differences. We present examples in which the embedding problem is trivial (within the class) and the computable isomorphism problem is more complicated. We also give an example in which the embedding problem is more complicated than the isomorphism problem.     

h‐monotonically computable real numbers

Let h : ? → ? be a computable function. A real number x is called h‐monotonically computable (h‐mc, for short) if there is a computable sequence (x_s) of rational numbers which converges to x h‐monotonically in the sense that h(n)|x – x_n| ≥ |x – x_m| for all n andm > n. In this paper we investigate classes h‐ MC of h‐mc real numbers for different computable functions h. Especially, for computable functions h : ? → (0, 1)_?, we show that the class h‐ MC coincides with the classes of computable and semi‐computable real numbers if and only if Σ_i∈?(1 – h(i)) = ∞and the sum Σ_i∈?(1 – h(i)) is a computable real number, respectively. On the other hand, if h(n) ≥ 1 and h converges to 1, then h‐ MC = SC (the class of semi‐computable reals) no matter how fast h converges to 1. Furthermore, for any constant c > 1, if h is increasing and converges to c, then h‐ MC = c‐ MC . Finally, if h is monotone and unbounded, then h‐ MC contains all ω‐mc real numbers which are g‐mc for some computable function g. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Computable Families of Superatomic Boolean Algebras

We describe the families of superatomic Boolean algebras which have a computable numbering. We define the notion of majorizability and establish a criterion that is formulated only on using algorithmic terms and majorizability. We give some examples showing that the condition of majorizability is essential. We also prove some criterion for the existence of a computable numbering for a family of -atomic algebras ( is a computable ordinal).     

形式背景的AE-仿紧性

利用拓扑学的思想定义了形式背景的AE-仿紧性,给出了AE-仿紧背景的充分条件,研究了AE-仿紧背景的若干性质.证明了AE-仿紧性被适当的信息态射所保持,对一类闭嵌入子背景是遗传的.在以形式背景为对象,信息态射为态射的范畴FCC中,给出了两个形式背景乘积对象的表示,证明了两个AE-仿紧背景的乘积对象还是AE-仿紧的.     

Initial segments of computable linear orders with additional computable predicates

We study computable linear orders with computable neighborhood and block predicates. In particular, it is proved that there exists a computable linear order with a computable neighborhood predicate, having a Π₁⁰ -initial segment which is isomorphic to no computable order with a computable neighborhood predicate. On the other hand, every Σ₁⁰ -initial segment of such an order has a computable copy enjoying a computable neighborhood predicate. Similar results are stated for computable linear orders with a computable block predicate replacing a neighborhood relation. Moreover, using the results obtained, we give a simpler proof for the Coles–Downey–Khoussainov theorem on the existence of a computable linear order with Π₂⁰ -initial segment, not having a computable copy.     

On Classifying Subsets of Natural Numbers by Their Computable Permutations

We introduce some alternative definitions of the concept of computable automorphism of a set of natural numbers. We study their relationships and investigate whether some classes of sets having isomorphic groups of automorphisms coincide with other classes of sets usual in computability. Finally, we show that the classification of sets by these groups of automorphisms is nontrivial.     

可计算建模

可计算建模(computable modeling) 指根据所研究问题对计算精度的要求, 综合运用相关领域知识建立或简化模型, 减少计算量, 提高计算效率, 使得模型在现有计算机条件下可计算. 可计算建模是科学与工程计算研究的一个重要方面. 本文主要通过若干例子介绍可计算建模研究的内涵.     

Computable Structure and Non-Structure Theorems

In a lecture in Kazan (1977), Goncharov dubbed a number of problems regarding the classification of computable members of various classes of structures. Some of the problems seemed likely to have nice answers, while others did not. At the end of the lecture, Shore asked what would be a convincing negative result. The goal of the present article is to consider some possible answers to Shore's question. We consider structures of some computable language, whose universes are computable sets of constants. In measuring complexity, we identify with its atomic diagram D(), which, via the Gödel numbering, may be treated as a subset of . In particular, is computable if D() is computable. If K is some class, then K^c denotes the set of computable members of K. A computable characterization for K should separate the computable members of K from other structures, that is, those that either are not in K or are not computable. A computable classification (structure theorem) should describe each member of K^c up to isomorphism, or other equivalence, in terms of relatively simple invariants. A computable non-structure theorem would assert that there is no computable structure theorem. We use three approaches. They all give the correct answer for vector spaces over Q, and for linear orderings. Under all of the approaches, both classes have a computable characterization, and there is a computable classification for vector spaces, but not for linear orderings. Finally, we formulate some open problems.     

Polyadic Concept Analysis

The framework and the basic results of Wille on triadic concept analysis, including his Basic Theorem of Triadic Concept Analysis, are here generalized to n-dimensional formal contexts.     

Spectra of computable models for Ehrenfeucht theories

We construct an example of a theory with a finite (greater than one) number of isomorphism types of countable models such that its prime and saturated models have computable presentations and there exists a model which lacks in such. Supported by the Council for Grants (under RF President) and State Aid of Fundamental Science Schools via project NSh-4413.2006.1. __________ Translated from Algebra i Logika, Vol. 46, No. 3, pp. 275–289, May–June, 2007.     

Possibility-theoretic extension of derivation operators in formal concept analysis over fuzzy lattices

Formal concept analysis (FCA) associates a binary relation between a set of objects and a set of properties to a lattice of formal concepts defined through a Galois connection. This relation is called a formal context, and a formal concept is then defined by a pair made of a subset of objects and a subset of properties that are put in mutual correspondence by the connection. Several fuzzy logic approaches have been proposed for inducing fuzzy formal concepts from L-contexts based on antitone L-Galois connections. Besides, a possibility-theoretic reading of FCA which has been recently proposed allows us to consider four derivation powerset operators, namely sufficiency, possibility, necessity and dual sufficiency (rather than one in standard FCA). Classically, fuzzy FCA uses a residuated algebra for maintaining the closure property of the composition of sufficiency operators. In this paper, we enlarge this framework and provide sound minimal requirements of a fuzzy algebra w.r.t. the closure and opening properties of antitone L-Galois connections as well as the closure and opening properties of isotone L-Galois connections. We apply these results to particular compositions of the four derivation operators. We also give some noticeable properties which may be useful for building the corresponding associated lattices.     

Estimation of the algorithmic complexity of classes of computable models

We estimate the algorithmic complexity of the index set of some natural classes of computable models: finite computable models (Σ ₂ ⁰ -complete), computable models with ω-categorical theories (Δ _ω ⁰ -complex Π _ω+2 ⁰ -set), prime models (Δ _ω ⁰ -complex Π _ω+2 ⁰ -set), models with ω ₁-categorical theories (Δ _ω ⁰ -complex Σ _ω+1 ⁰ -set. We obtain a universal lower bound for the model-theoretic properties preserved by Marker’s extensions (Δ _ω ⁰ .