The Mathematical Foundation of Informatics

Preface.

Contents.

In this paper is introduced the growth function of a Petri net. We show that the growth function of any Petri net is bounded by a certain polynomial. There are relations between the growth function and the representative complexity of the language which is accepted by a Petri net. Some applications are examined.

In this paper we show the existence of an infinite hierarchy of Petri net languages on the number of transitions and places of their recognizing nets.

In this paper we present some algoritms to decide whether a given rational language is an ω-code. Those algorithms have a complexity in the worst case in O(n³), n being the number of states of the automaton representing the language.

We present a distributed algorithm for constructing a random spanning tree, making use of random walks as network traversal scheme. Our approach is novel and make use of distributed random walks, each one represented by a token annexing a territory over the underlying graph. These multiple random walks collapse into a final one, that defines the final territory and provides the random spanning tree. The scheme is parallel and make use of waves to merge very efficiently the spanning forest computed by the random walks into one final random spanning tree.

This paper is concerned with the fundamental role of two mathematical theories in some clustering problems. Formal concept analysis provides the algebraic structure and properties of possible concepts from a given context, and rough set theory provides a mathematical tool to deal with imprecise and incomplete data. Based on these theories, we developed models and algorithms for solving three clustering problems: conceptual clustering, approximate conceptual clustering, and text clustering.

We consider the problem of k-partitioning a graph into k balanced subsets that minimizes the number of crossing weighted edges Previously, Maximum flow approach, iterative improvement, geometric representation were given to solve this problem. In this paper we propose a balanced k-partition heuristic based on a max spanning tree method.

A graph is called a maximal nonhamiltonian graph if it is nonhamiltonian and will be hamiltonian by adding any new edge. The following conjecture was presented by Erdös that if C is a longest cycle in a maximalnonhamiltonian graph G then G–C is a complete graph. In this paper we prove that the conjecture is true for some classes of graphs.

This paper is a survey article to introduce some results on deterministic and nondeterministic directable automata and their related languages.

The quality of codes can be expressed in terms of their error-resistance and their redundancy. Solid codes are highly resistant to decoding errors resulting from incorrectly transmitted code words. We derive lower bounds on the redundancy of certain maximal solid codes.

No abstract received.

We propose a new notion of the recognition of w-languages using monoids. The used criteria is stronger than the one previously introduced by Büchi. It very easy to build deterministic automaton accepting a given rational ω-language from a monoid that strongly recognizes this w-language.

In this paper we present a new class of data dependencies that called multivalued positive Boolean dependencies. This class is a generalization of all classes of positive Boolean dependencies. Some generalization concepts for implications as well as an axiom system for inference rules are also presented. With the help of the equivalence theorem of consequences in the world of all relations, the world of 2-tuple relations and propositional logic in the class of multivalued positive Boolean dependencies we can get some significant results related to m-covers. Some conditions for two sets being m-equivalent are given. Necessary and sufficient conditions for testing an m-redundant set of multivalued positive Boolean dependencies are introduced. Base on these results some algorithms for constructing a nonredundant m-cover of a given set of multivalued positive Boolean dependencies are presented.

In this article, we propose a new measure for attribute selection (R_N measure) having closed relations to rough measure (Pawlak Z. [6]) and R - measure (Ho Tu Bao, Nguyen Trung Dung [3]). We prove that all of these three measures are confidence measures i.e. satisfy the weak monotonous axiom. So the R_N - measure is worth in the class of attribute selection measures. Some relations between these three measures are also shown.

We study the complexity of circuit-based combinatorial problems (e.g., the circuit value problem and the satisfiability problem) defined by Boolean circuits with gates from an arbitrary finite base B of Boolean functions. Special cases have been investigated in the literature. We give a complete characterization of their complexity depending on the base B. For example, for the satisfiability problem for Boolean circuits with gates from B we present a complete collection of (decidable) criteria which tell us for which B this problem is in L, is complete for NL, is complete for L, is complete for P, or is complete for NP. Our proofs make substantial use of the characterization of all closed classes of Boolean functions given by E.L. POST already in the twenties of the last century.

We define the notion of -covering of automata with multiplicity (in a semiring ) that extend the one of covering of automata. We make use of this notion, together with the Schützenberger construct that we have explained in a previous work and that we briefly recall here, in order to give a direct and constructive proof of a fundamental theorem on -rational power series.

Let G be a finite simple group and π_e(G) the set of element orders of G. For a subset Γ of all positive integers, let h(Γ) denote the number of distinct groups G such that π_e(G)=Γ. For given group G, we have h(π_e(G)) ≥ 1. In this paper we prove that h(π_e(G)) {1, 2, ∞} for |G| < 10⁸. Moreover we give a classification for such simple groups G.

In this paper, we give necessary and sufficient conditions for tetravalent metacirculant graphs, the first symbol of which is not empty, to be connected.

In the Probabilistic Logic, the single value of the truth probability of a sentence is calculated by adding assumptions. By adding the Maximum Entropy Principle (MEP) the reasoning problem becomes a nonlinear optimization problem. In this note, we assert the equivalence between the MEP and the Conditional Independence assumption (CIA) and the Randomness Assumtpion (RA) formulas for a class of Probabilistic Knowledge Base. Thus, for this class, instead of solving a nonlinear optimization problem to find the truth probability of a sentence, we can drive it from Calculus and some CIA + RA formulas.