Fundamenta Informaticae

This essay contains personal views about mathematical chemistry — mainly with nonnumerical and non-quantumflavor. Similarities between mathematics and chemistry are pointed out, mainly based on the invention aspect of these two sciences, in contrast to discoveries characterizing most natural sciences. The author's involvement with chemical applications of graph theory needed a biographical background. Then five topics are reviewed: (1) enumerations of certain classes of chemical compounds initiated in collaboration with Professors Silviu Teleman and Frank Harary; (2) the (3,g)-cages with g=10 and 11; (3) isoprenoid structures modeled in collaboration with Professor Solomon Marcus by cellular automata and picture grammars; (4) benzenoid polycyclic hydrocarbons described in collaboration with Professor Ioan Tomescu; and (5) topological indices.

In this paper we consider a new framework for linguistics based on the behavior of DNA molecules: biosyntax. This new framework includes two approaches – molecular syntax and recombination patterns – that seem to be quite suitable for explaining in a completely new way some syntactic phenomena. Molecular syntax and recombination patterns are two different formalisms with the same single idea: mechanisms at work in biology may be used in the field of linguistics and natural language processing and may provide a simpler and more efficient approach to the description of the syntax of natural languages.

The study of P systems as a mathematical model for biological systems is an important research topic in the area of membrane computing. In this respect, the detection of periodicity and almost periodicity as aspects of the system dynamics seems to be of particular relevance for understanding many biological processes and their related phenomena. This paper introduces specific notions of periodicity and almost periodicity for (infinite) sequences of multisets, which are used to describe the dynamics of P systems. Specifically, a variant of P systems, called P systems with resources, is considered where the rules always consume a certain amount of resources, which are provided in the form of a periodic input sequence of multisets. It is then shown that P systems with resources are computationally complete (when halting computations are considered) and that, in general, they can generate sequences of multisets that are not even almost periodic (once the constraint of having halting computation is released). However, if P systems with resources are restricted to be deterministic, it is shown that a characterization of the behaviour of a particular class of P systems with resources can be obtained in terms of almost periodicty.

Gödel's incompleteness theorem states that every finitely-presented, consistent, sound theory which is strong enough to include arithmetic is incomplete. In this paper we present elementary proofs for three axiomatic variants of Gödel's incompleteness theorem and we use them (a) to illustrate the idea that there is more than "complete vs. incomplete" there are degrees of incompleteness, and (b) to discuss the implications of incompleteness and computer-assisted proofs for Hilbert's Programme. We argue that the impossibility of carrying out Hilbert's Programme is a thesis and has a similar status to the Church-Turing thesis.

In this paper we consider the transformation from (minimal) non-deterministic finite automata (NFAs) to deterministic finite cover automata (DFCAs). We want to compare the two equivalent accepting devices with respect to their number of states; this becomes in fact a comparison between the expression power of the nondeterministic device and the expression power of the deterministic with loops device. We prove a lower bound for the maximum state complexity of deterministic finite cover automata obtained from non-deterministic finite automata of a given state complexity n, considering the case of a binary alphabet. We show, for such binary alphabets, that the difference between maximum blow-up state complexity of DFA and DFCA can be as small as 2⌈n/2;⌉−2 compared to the number of states of the minimal DFA. Moreover, we show the structure of automata for worst case exponential blow-up complexity from NFA to DFCA. We conjecture that the lower bound given in the paper is also the upper bound. Several results clarifying some of the structure of the automata in the worst case are given (we strongly believe they will be pivotal in the upper bound proof).

Membrane systems are parallel computational devices inspired from the cell functioning. Since the original definition, a standard feature of membrane systems is the fact that each rule of the system is executed in exactly one time-unit. However, this hypothesis seems not to have a counterpart in real world. In fact, in cells, chemical reactions might take different times to be exe-cuted. Therefore, a natural step is to associate to each rule of a membrane system a certain time of execution. We are interested in membrane systems, called time-free, working independently from the assigned execution time of the rules. A basic and interesting problem in time-free membrane systems consists in the synchronization of different rules, running in parallel, and having unknown execution times. Here, we present different ways to approach this problem within the framework of membrane systems. Several research proposals are also suggested.

A variant of contextual grammars, namely the total contextual grammar with restricted choice, is studied from several points of view. The results obtained by comparing this concept with other related types of contextual grammars support the claim that total contextual grammars with restricted choice are a generative model with good enough qualities for applications in the field of computational linguistics.

In this paper we present the genetic message translation in terms of automata, transformation semigroups, restricted direct product and cascade product. We give a description of the alphabets and words involved in the processes of transcription and translation. We define a Mealy automata for the translation process, providing its detailed coverings by simpler machines. This leads to an interesting structural representation of the proteins.

We discuss external contextual grammars with choice where the choice language belongs to a family of subregular languages. We determine the hierarchy of language families of contextual languages which is obtained by the use of nilpotent, combinational, definite, regular suffix closed, and regular commutative languages as choice languages.

We consider the data compression using antidictionaries and give algorithms for faster compression and decompression. While the original method of Crochemore et al. uses finite transducers with ε-moves, we (de)compress using ε-free transducers. This is provably faster, assuming data non-negligibly compressible, but we have to consider the overhead due to building the new ma-chines. In general, they can be quadratic in size compared to the ones allowing ε-moves; we prove this bound optimal as it is reached for de Bruijn words. However, in practice, the size of the ε-free machines turns out to be close to the size of the ones allowing ε-moves and therefore we can achieve significantly faster (de)compression. We show our results for the files in Calgary corpus.

In this paper we introduce a metric for measuring the similarity between two classifications which differ by their constitutive elements. Our measure is inspired from natural language and genomics where the most important information is carried by the first part of the unit. We extend the measure to words and to rooted (un)labelled general trees. We use this metric to analyze the syllabic similarity of Romance languages.

Using well-known characterizations of regular languages, on the basis of known iteration lemmas, new iteration lemmas for regular languages are given.

The main result proved in this paper shows that the natural embedding of any recursively enumerable one-dimensional array language in the two-dimensional space can be characterized by the projection of a two-dimensional array language generated by a contextual array grammar working in the t-mode and with norm one. Moreover, we show that any recursively enumerable one – dimensional array language can even be characterized by the projection of a two-dimensional array language generated by a contextual array grammar working in the t-mode where in the selectors of the contextual array productions only the ability to distinguish between blank and non-blank positions is necessary; in that case, the norm of the two-dimensional contextual array grammar working in the -mode cannot be bounded.

We extend the result from [8] by giving also a concrete polynomial parsing algorithm for a class of languages generated by a variant of contextual grammars, namely local internal contextual grammars with context-free choice.

The evolution of life on our planet is briefly reviewed emphasizing the roles played by light and language. Life and language are regarded as a single interlocking system which light has stimulated to serve as an organ of cosmic awareness. Light first rewarded life with energy. Light then stimulated life to grow upward from the surface of our planet. Life is now integrating into itself detailed knowledge of the cosmos by decoding the vast store of information contained in celestial light.

The paper formalizes two types of refinement for finite state machines: OR refinement and p-OR refinement. For each such type of refinement, it shows that, if the implementation is also constructed through a process of refinement, then the application of Chow's W test generation method can be distributed into smaller chunks, thus diminishing the effort devoted to testing and the size of the final test set.

One of the strengths of using a stream X-machine to specify a system is that, under certain well defined conditions, it is possible to produce a test set that is guaranteed to determine the correctness of the implementation. This testing method assumes that the processing functions are correctly implemented, therefore it only tests the integration of the processing functions implementations into the system implementation. This paper uses a case study to illustrate how this method can be extended so that it will no longer require the implementations of the processing functions to be proved correct before the actual system testing can take place. Instead, the testing of the processing functions is performed along with the integration testing.

It is known that for (right-) monotone deterministic one-way restarting automata, the use of auxiliary symbols does not increase the expressive power. Here we show that the same is true for deterministic two-way restarting automata that are right-left-monotone. Moreover, we present a transformation of this kind of restarting automata into contextual grammars with regular selection.

Bracketed contextual grammars are a variant of Marcus' contextual grammars with an induced Dyck-structure to control the derivation process and to provide derivation trees. Many variants of bracketed contextual grammars have been proposed in literature. In this paper, we study the relationship between various mechanisms in such grammars, in particular the number of brackets, the used selector languages, and the ability to introduce more than a single pair of brackets in a derivation step, with respect to the generative capacity of the resulting models.

In this paper, we continue the study of contextual and rewriting P systems. In contextual P systems, we improve a universality result avoiding the extended feature and by using rules of small weight. In rewriting P systems, we have two (rather surprising) universality results, both of them using three membranes, for non-extended systems with replicated rewriting and with leftmost rewriting, respectively.

A generalization of contextual grammars by adding probabilities is introduced, enriching the generative power of such grammars. An example exhibits a non-contextual, even not context-free language.

The double stranded structure of DNA molecules is investigated in an abstract setting. Only the general structure of bilinear strings is taken into account regardless of specific physical and biochemical aspects of DNA molecules. In this context, the principles which DNA processes are based on are formulated in an abstract form. Surprisingly enough, some intrinsic features of DNA molecules turn out to be implied by these general principles.

Our paper proposes a technique for performing logical analysis over the calculi for communication and mobility, i.e., Ambient Calculus type of calculi. We show how this analysis can be used in the case of biological models in order to obtain significant information for biologists.

The technique is based on set theoretical models we developed for ambient processes by using the power of Hypersets Theory. These models are further used as possible worlds in a Kripke structure organized for a propositional branching temporal logic.

Providing the temporal logical structure for the accessibility relation between ambient processes, we open the perspective of reusing model checking algorithms developed for temporal logics in analyzing any phenomena that can be described by these calculi.

Time-varying distributed H systems are a well known model of molecular computing. In this article we present an overview of this model, its history, related results, and open problems.

This work is a continuation of [9]. We extend the multi-dimensional external contextual grammars introduced in the aforementioned work with the possibility of adjoining contexts in a selective way. An investigation of some mathematical properties (computational power and recognition complexity) of these new variants of contextual grammars is done via a constant comparison with the corresponding properties of classic Marcus external contextual grammars with or without choice.

Insertion grammars have been introduced in [1] and their computational power has been studied in several places. In [7] it is proved that insertion grammars with weight at least 7 can characterize recursively enumerable languages (modulo a weak coding and an inverse morphism), and the question was formulated whether or not this result can be improved. In this paper, we come up with a positive answer to this question, by decreasing the weight of the insertion grammar used to 5. We also give a characterization of recursively enumerable languages in terms of right quotients of insertion languages.

The concept of a contextual grammar is slightly generalized here; the generalized grammars called contextual hypergrammars admit to introduce the so called reducing operators. Using some results concerning these operators a construction is described assigning a contextual grammar G _n (V,L) to any language (V,L) and to any nonnegative integer n. This construction has the following property: The language (V,L) is generated by a contextual grammar if and only if there exists a nonnegative integer n _0 such that G _n =G _{n_0} (V,L) for any n ≥ n _0 .

A uniformcontextual grammar with contexts shuffled along trajectories uses the same set of trajectories for each context. We prove that when the alphabet has at least two symbols, the nonuniform contextual grammars with trajectories are strictly more powerful than the uniform variant. For unary alphabets the generative power of the two variants coincides, and the same is true for grammars where the sets of trajectories are regular or context-free.

The operations of symport and antiport, directly inspired frombiology, are already known to be rather powerful when used in the framework of P systems. In this paper we confirm this observation with a quite surprising result: P systems with symport/antiport rules using only three objects can simulate any counter machine, while systems with only two objects can simulate any blind counter machine. In the first case, the universality (of generating sets of numbers) is obtained also for a small number of membranes, four.

This paper concerns a new approach to intelligent data analysis based on information flow distribution study in a flow graph. Branches of a flow graph are interpreted as decision rules, whereas a flow graph is supposed to describe a decision algorithm. We propose to model decision processes as flow graphs and analyze decisions in terms of flow spreading in a graph.

In this paper, dedicated to Professor Solomon Marcus on the occasion of His 80th birthday, we discuss the idea of intensional many-valued logic reflecting the logical content of rough set approach to analysis and treatment of uncertainty. In constructing the variety of logics presented in the paper, we make use of a certain kind of tolerance (similarity) relations called rough mereological tolerances. A study of tolerance relations that arise in rough set environments was initiated in 1994, with the paper [23], in which basic ideas pertaining to tolerance relations in the rough set framework were pointed to. The analysis of the role tolerance relations may play in machine learning based on rough set-theoretic ideas was carried out by Professor Solomon Marcus in His seminal paper, written during His stay in Warsaw in December of the year 1994. At the same time the first author had first ideas related to the applicability of ideas of mereology in the rough set analysis of uncertainty. In a later analysis it has turned out that mereological approach has led to a development of a new paradigm in reasoning under uncertainty, called rough mereology, proposed by Lech Polkowski and Andrzej Skowron. Within this paradigm, one is able to construct a variety of tolerance relations. Those tolerance relations, induced by rough mereological constructs called rough inclusions, serve as a basis for constructing a variety of logics, called rough mereological logics, that are related to the inherent structure of any rough set universe.

In this paper, we introduce gradually all essential and necessary notions from the area of rough set theory, mereology and rough mereology, and then we discuss tolerance relations induced by rough inclusions along with some methods for inducing rough inclusions with desired properties. The paper culminates with a discussion of intensional logics based on rough mereological tolerance relations. In this way, we explore one of so many paths in scientific research, that have been either pointed to or threaded by Professor Solomon Marcus.

We investigate the number of (scattered) subword occurrences and Parikh matrices, especially the case where the matrix determines the word uniquely. A condition introduced in this paper, called γ-property, turns out to be a powerful tool for such unambiguous matrices. Interconnections with the general theory of subword histories are also pointed out.

The Collatz problem is comprised of two distinct, separate questions: existence of eventually periodic Collatz reductions with a nontrivial period, and existence of period-free Collatz reductions. This paper introduces a few distinct, related formalizations of the Collatz dynamics as term rewriting systems, using elementary concepts from the theory of state transition dynamics. Some of the subject systems act on finite terms, whereas others rewrite terms that are endowed with a countable, recursively defined structure. The latter presents a convenient framework for the investigation of extensions of the Collatz dynamics to dense systems.

The approximation space definition has evolved in rough set theory over the last 15 years. The aim was to build a unified framework for concept approximations. We present an overview of this evolution together with some operations on approximation spaces that are used in searching for relevant approximation spaces. Among such operations are inductive extensions and granulations of approximation spaces. We emphasize important consequences of the paper for research on approximation of vague concepts and reasoning about them in the framework of adaptive learning. This requires developing new approach to vague concepts going beyond the traditional rough or fuzzy approaches.

There is a renewed interest in word sense disambiguation (WSD) as it contributes to various applications in natural language processing. In this paper we survey vector-based methods for WSD in machine learning. All the methods are corpus-based and use definition of context in the sense introduced by S. Marcus [11].

Lempel and Ziv (1976) proposed a computable string production-complexity. In this paper, our emphasis is on providing the rigorous development, where possible, for the theoretical aspects of a more recent and contrasting measure of string complexity. We derive expressions for complexity bounds subject to certain constraints. We derive an analytic approximation to the upper bound to linearize the complexity measure. The linearized measure enables us to propose an entropy measure, observed elsewhere to correspond closely with the Kolmogorov-Sinai entropy in simple dynamical systems.

Let A be an alphabet of cardinality m, k _n be a sequence of positive integers and ω∈ A* (|ω|=k _n ). In this paper it is shown that if lim sup _{n&rarr;&infin;} k _n /ln n<1/ln m, then almost all words of length n over A contain the factor ω, but if lim sup _{n&rarr;&infin;} k _n /ln n>1/ln m, then this property is not true. Also, if lim inf _{n&rarr;&infin;} k _n /ln n>1/ln m, then almost all words of length n over A do not contain the factor ω. Moreover, if lim _{n&rarr;&infin;} (ln n-k _n ln m)=α∈ R, then lim sup _{n&rarr;&infin;} |W(n,k _n ,ω,A)| /m ^m ≤1−exp (−exp(α)) and lim inf _{n&rarr;&infin;} |W (n, k _n ,ω,A)|/m ^n ≥1−exp (−(1−1/m) exp(α)), where W(n, k _n , ω, A) denotes the set of words of length n over A containing the factor ω of length k _n .

In this paper, we summarize recent results and progress in state complexity research. We analyze why many basic state complexity problems were not solved earlier, in the sixties and seventies. We also suggest several future directions for this area of research.