Search

It is well-known inside the Formal Concept Analysis (FCA) community that a concept lattice could have an exponential size with respect to the input data. Hence, the size of concept lattices is a critical issue in large real-life data sets. In this paper, we propose to investigate congruence relations as a tool to get meaningful parts of the whole lattice or its implication basis. This paper presents two main theoretical contributions, namely two context (or lattice) decompositions based on congruence relations and new results about implication computation after decomposition.

The paper presents a new method of investigating topological properties of three-dimensional manifolds by means of computers. Manifolds are represented as block complexes. The paper contains definitions and a theorem necessary to transfer some basic knowledge of the classical topology to finite topological spaces. The method is based on subdividing the given set into blocks of cells in such a way that a k-dimensional block be homeomorphic to a k-dimensional ball. The block structure is described by the data structure known as “cell list” which is generalized here for the multidimensional case. Results of computer experiments are presented.

In a recent paper [Discrete Appl. Math. 43 (1993) 115–129], Kern formulates two conjectures on the relationship between the computational complexity of computing the depth function of a discrete optimization problem and the computational complexity of solving this optimization problem to optimality. In this note (that might be considered to be a kind of erratum to Kern's paper), we exhibit simple counterexamples to both conjectures under the assumption P≠NP.

Multilevel secret sharing schemes are used in cryptography when a responsibility has to be delegated to qualified groups of participants rather than to a single one. In the present paper we propose a mathematical model for such a scheme based on projective geometry over a finite field. The main ingredients are normal rational curves and their osculating subspaces.

Rotation symmetric Boolean functions have raised widespread attention because of the good properties in cryptosystem. This paper presents a new construction of odd-variable rotation symmetric Boolean functions with optimal algebraic immunity. The nonlinearity of the new functions is higher than some existing theoretical constructions of rotation symmetric Boolean functions with optimal algebraic immunity. Further, it is also checked that such functions have almost optimal immunity against fast algebraic attacks for small variables. Besides, the algebraic degree of the constructed functions is also high enough.

While investigating the N -Queens Puzzle, Thomas Preuser came to a simplification for the search; this is generalized and proven here. The main point is: if you have a suitable mapping of a big set to a small one, explore and use the symmetry of the small set, and transfer the result to the big set. With this mapping and the lemma, you no longer bother with the symmetry of a single element in the big set. The paper is written for two different groups: first for computer scientists implementing searches under symmetry, and second for mathematicians supporting them, and interested in understanding how search spaces can be diminished under symmetry.

In this paper, we demonstrate the capability of formal concept analysis in representing a special partially ordered structures named algebraic L-domains. In particular, we introduce the notion of locally complete consistent F-augmented contexts and prove that its associated category with F-approximable connections as morphisms is precisely equivalent to that of algebraic L-domains with Scott continuous functions as morphisms. This result provides a concrete representation of algebraic L-domains via formal concept analysis as an efficient approach.

In this paper we consider applications of max-plus algebra to flow shop scheduling problems. Our aim is to show that max-plus algebra is useful for flow shop scheduling. We present two new solvable conditions in m -machine permutation flow shops using max-plus algebra. One of the conditions is found by considering a max-plus algebraic analogue of a proposition in linear algebra. The other is derived using a new framework, which associates a machine with a matrix and is the dual of the max-plus approach associating a job with a matrix by Bouquard, Lente, and Billaut (2006). The framework is the first one which can deal with non-permutation flow shop problems based on max-plus algebra. Moreover, using the framework, we provide new simple proofs of some known results.

In this paper, we characterize balanced Boolean functions with optimal algebraic immunity by Schur functions. By applying this characterization, three classes of balanced Boolean functions with optimal algebraic immunity are constructed. Some examples of the constructed functions with other desired cryptographic properties are also presented.

This paper (the second of two parts) settles the decidability status of several properties of derivations in E0L systems (forms). In particular we show that the so called “one-to-many simulation” among E0L forms is decidable, solving in this way an open problem from [6]. We use a more general mathematical framework, based on the theory of well-quasi orders, developed in Part I of this paper [2].

In two recent papers the authors introduced some new approaches to the problem of modeling the phenomena underlying immunological reaction tests. These approaches allow one to easily construct the best possible models for a given amount of immunological test data. In the first paper the authors used a purely Boolean approach, i.e., it was assumed that the experimenter signified whether or not a reaction occurred in a given test. In the second paper the authors assumed that the relative strengths of the reactions were available as data for the modeling process. They showed that in this case strictly better models could be constructed. This paper generalizes the approaches taken in the first two papers and provides a unified approach to this whole subject. Many of the results, e.g., the ability to construct the best model, of the first two papers hold in this more general setting. Moreover, this generalization allows one to assess the tradeoffs involved in using data on the relative strengths of reactions. In particular, we see that using relative strengths is equivalent to using an additional intersection factor in a strictly Boolean approach. This intersection factor it turns out, can be obtained experimentally by using elution in addition to the absorption involved in the first two papers. Finally, the duality between fragments and cofragments becomes apparent using this approach.

In previous papers we have introduced a notion of multivalued continuity in digital spaces which extends the usual notion of digital continuity and allows us to define topological notions, like retractions, in a far more realistic way than by using just single-valued digitally continuous functions. In particular, we have characterized the deletion of simple points in 2-D, one of the most important processing operations in digital topology, as a particular kind of retraction. In this work we extend this result to three-dimensional digital sets, characterizing the deletion of ( 26 , 6 ) -simple points in 3-D as ( N , 26 ) -retractions.

Let k ? 1 be an integer. A signed Roman k -dominating function on a graph G is a function f : V ( G ) ?s? { - 1 , 1 , 2 } such that ? u ? N v f ( u ) ? k for every v ? V ( G ) , where N v is the closed neighborhood of v , and every vertex u ? V ( G ) for which f ( u ) = - 1 is adjacent to at least one vertex w for which f ( w ) = 2 . A set { f 1 , f 2 , ? , f d } of distinct signed Roman k -dominating functions on G with the property that ? i = 1 d f i ( v ) ? k for each v ? V ( G ) , is called a signed Roman k -dominating family (of functions) on G . The maximum number of functions in a signed Roman k -dominating family on G is the signed Roman k -domatic number of G , denoted by d s R k ( G ) . In this paper we initiate the study of signed Roman k -domatic numbers in graphs, and we present sharp bounds for d s R k ( G ) . In particular, we derive some Nordhaus-Gaddum type inequalities. In addition, we determine the signed Roman k -domatic number of some graphs.

This paper investigates methods based on codes and matrices for determining the existence or nonexistence of designs. The methods are general but are applied to the particular case of a design (22, 33, 12, 8, 4). As such it is a sequel to a paper of Hall, Jr., Roth, van Rees and Vanstone. An early paper by Hamada and Kobayashi made the first steps in this direction.

This paper aims to draw the attention of mathematicians to a class of problems whose resolution has recently become possible from the practical viewpoint but still badly lacks a firm mathematical basis. These problems arise in biological systems which involve multiple interacting feedback loops. Such systems may be described in terms of differential equations. However, the non-linear character of most of these equations precludes an analytic treatment, and it is often very difficult to obtain a global idea of their complex dynamics. Logical methods (briefly summarised in this paper) have been developed (Thomas [13–15]). In spite of the somewhat caricatural character inherent to logical descriptions, these methods grasp the essential qualitative features of the dynamics of the systems, and, for complex systems, they greatly help in clarifying the continuous description. Graphs are involved at two distinct levels; first, the logical structure of a system can be described by a graph of interactions , and at a later stage of the analysis one obtains a graph of the logical sequences of states . Although algorithms permit the second type of graph to be derived from the first, there is so far no general mathematical analysis of their relation. The paper gives, as an illustration of this type of problem, the relation between positive loops (in the graph of interactions) and multiple steady states (which are found as the final states in the graph of the sequences of states). In short, a system comprising n positive loops may have up to 3 n steady states (2 n attractors); interactions between the loops reduce these numbers in a predictable way.

Given a distribution of pebbles on the vertices of a connected graph G, a pebbling move on G consists of taking two pebbles off one vertex and placing one on an adjacent vertex. The t-pebbling [email protected]"t(G) is the smallest positive integer such that, for every distribution of @p"t(G) pebbles and every vertex v, t pebbles can be moved to v. For t=1, Graham conjectured that @p"1([email protected]?H)@[email protected]"1(G)@p"1(H) for any connected graphs G and H, where [email protected]?H denotes the Cartesian product of G and H. Herscovici further conjectured that @p"s"t([email protected]?H)@[email protected]"s(G)@p"t(H). In this paper, we show that @p"s"t([email protected]?G)@[email protected]"s(T)@p"t(G), @p"s"t(K"[email protected]?G)@[email protected]"s(K"n)@p"t(G) and @p"s"t(C"2"[email protected]?G)@[email protected]"s(C"2"n)@p"t(G) when G has the 2t-pebbling property, T is a tree, K"n is the complete graph on n vertices, and C"2"n is the cycle on 2n vertices, which confirms a conjecture due to Lourdusamy. Moreover, we also show that any graph G with diameter 2 and @p"t(G)[email protected](G)+4(t-1) has the 2t-pebbling property, which extends a result of Pachter et al.

In this paper, we determine explicitly the zeta polynomials of near-MDS codes and obtain necessary and sufficient conditions for near-MDS codes to satisfy the Riemann hypothesis analogue.

The whist tournament problem has attracted the interests of many design theorists for over a century. To construct Z-cyclic whist tournaments, the concept of Z-cyclic patterned starter whist tournaments was introduced. The research on Z-cyclic patterned starter whist tournaments dates back to 1954. Although considerable progress has been made in the last decade or so, less has been made about the existence of Z-cyclic patterned starter whist tournaments, despite the efforts of many authors.In this paper, we will first provide two new nonexistence results for Z-cyclic patterned starter whist tournaments. Then, we will propose a general recursive construction, i.e., a frame construction, for Z-cyclic patterned starter whist tournaments. As a consequence, we are able to unify many known constructions for Z-cyclic patterned starter whist tournaments. The known existence results of such designs are then extended.

The left-regular multiplication is explicitly embedded in the notion of perfect nonlinearity. But there exist many other group actions. By replacing translations by another group action the new concept of group action-based perfect nonlinearity has been introduced. In this paper we show that this generalized concept of nonlinearity is actually equivalent to a new bentness notion that deals with functions defined on a finite Abelian group G that acts on a finite set X and with values in the finite-dimensional vector space of complex-valued functions defined on X.

This paper presents an algebraic formalism for reasoning on finite increasing sequences over Boolean algebras in general and on generalizations of rough set concepts in particular. We argue that these generalizations are suitable for modeling relevance of documents in an information retrieval system.

In this paper, we are going to study some additional relations between the Stirling matrix S"n and the Pascal matrix P"n. Also the representation for the matrix T"n and T"n^-^1 in terms of s"n and S"n will be considered. Consequently, this will give an answer to an open problem proposed by EI-Mikkawy [On a connection between the Pascal, Vandermonde and Stirling matrices-II, Appl. Math. Comput. 146 (2003) 759-769].

Primitive words, or strings over a finite alphabet that cannot be written as a power of another string, play an important role in formal language theory, coding theory, and combinatorics on words to name a few. In this paper, we extend some fundamental results about primitive words to primitive partial words. Partial words are strings that may have a number of “do not know” symbols.

In this paper we investigate how methods of deriving conceptual structures from ordinal data can be justified structurally. For the investigation we choose a categorical approach which is elaborated for suitable functors from the category of all ordinal structures to the category of all closure structures. The main result yields that the best functors are those which correspond to contra-ordinal scaling, a method developed in formal concept analysis (Formal Concept Analysis: Mathematical Foundations, Springer, Heidelberg, 1999).

The usefulness of topology in science and mathematics means that topological spaces must be studied, and computers must be used in this study. Here are examples of this need from physics: In classical physics, the Euclidean spaces and compact Hausdorff spaces that arise can be approximated by finite spaces, and the goal of this paper is to discuss such approximation. A recent nonclassical development in physics uses a version of such finite approximation to view the universe as finite and eternally changing, and this is also discussed. Finite spaces are completely determined by their specialization orders. As a special case, digital n-space, used to interpret Euclidean n-space and in particular, the computer screen, is also dealt with in terms of the specialization.

Because antimatroid closure spaces satisfy the anti-exchange axiom, it is easy to show that they are uniquely generated. That is, the minimal set of elements determining a closed set is unique. A prime example is a discrete convex geometry in Euclidean space where closed sets are uniquely generated by their extreme points. But, many of the geometries arising in computer science, e.g. the world wide web or rectilinear VLSI layouts are not uniquely generated. Nevertheless, these closure spaces still illustrate a number of fundamental antimatroid properties which we demonstrate in this paper. In particular, we examine both a pseudo-convexity operator and the Galois closure of formal concept analysis. In the latter case, we show how these principles can be used to automatically convert a formal concept lattice into a system of implications.

We present in this paper necessary and sufficient conditions for the representation of preferences in a decision-making problem, by the Sugeno integral, in a purely ordinal framework. We distinguish between strong representation (exact) and weak representation (no contradiction on strict preferences).

Formal concept analysis has been a topic of interest for about two decades. The mathematical notion of concept has its origin in formal logic. However, the empirical notion of concept has evolved through its use in many different disciplines. In this paper, we generalize the mathematical notion of concept and investigate order-theoretic properties of concept hierarchies for the new notion of concept.

During the past decade, perfect, almost perfect and maximum nonlinear functions on finite fields have been thoroughly investigated. The main tool to investigate these functions is the Walsh–Hadamard transform. This is a special version of the more general discrete Fourier transform. It is the purpose of this paper to show that the main results on nonlinear functions can be easily generalized to the case of arbitrary abelian groups if the Walsh–Hadamard transform is replaced by the discrete Fourier transform. This approach has three advantages: •Proofs become more transparent.•The connection with (relative) difference sets becomes apparent.•It yields possible generalizations to nonlinear functions on abelian groups.

Let A be a nonnegative integral n -square matrix with row sums r 1 , …, r n . It is known that per A ⩽ Π n i=1 r i ! l r i if A is a (0, 1)-matrix (Minc, 1963; Bregman, 1973) and also that per A ⩽ 1 + Π n i = 1 ( r i − 1) if A is fully indecomposable (Donald et al., 1984). These two bounds are, in general, uncomparable, even in the case that A is a fully indecomposable (0, 1)-matrix. In this paper we obtain some comparison test for these bounds with the aid of a function involving the gamma function.

In this paper, the representation, generation and inference of images using automata-theoretic techniques is investigated. It is shown that highly complex images, including “fractal” (self-similar) images, can be manipulated by the application of these techniques. Languages and relations over some alphabet are interpreted as images by treating strings as rational coordinates. In particular rational relations, specified by rational expressions, are considered. It is shown how texture of an image can be defined by probabilistic finite generators. Affine expressions are introduced as a generalization of both rational expressions and the IFS method to define images. Finally, two efficient methods to implement rational expressions are presented.

In this paper we describe algorithms to solve different problems in commutative algebra. These algorithms are linked by the fact that they are useful in considering integral extensions (integral closure, weak integral closure, etc.). The first algorithm computes the conductor of an extension of rings. The algorithm is based on the computation of the inverse image of a submodule relative to a module homomorphism. This problem is solved lifting suitably to free modules over polynomial rings. To complete the computation of the conductor one has to represent an integral extension as a finitely presented module; we give an algorithm for this, that at the same time verifies that the extension is integral. Other algorithms are given, that test subring inclusion and birational equivalence. These algorithms are not strictly necessary to perform the conductor computation, but are in some sense connected to the former problem, since if the answer to these tests is negative then the conductor is trivial.