Fundamenta Informaticae - Volume 64, issue 1-4

Authors: Calude, C. | Păun, Gh. | Rozenberg, G.

Article Type: Other

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. vii-vii, 2005

Authors: Balaban, Alexandru T.

Article Type: Research Article

Abstract: 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. Show more

Keywords: Graph theory, g-cages, isoprenoid structures, topological index

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 1-16, 2005

Authors: Bel Enguix, Gemma | Jiménez López, Maria Dolores

Article Type: Research Article

Abstract: 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. Show more

Keywords: Linguistics, syntax, DNA computing

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 17-28, 2005

Authors: Bernardini, Francesco | Gheorghe, Marian | Manca, Vincenzo

Article Type: Research Article

Abstract: 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. Show more

Keywords: Membrane computing, P system, periodicity, almost periodicity, biological model

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 29-42, 2005

Authors: Calude, Cristian S. | Rudeanu, Sergiu

Article Type: Research Article

Abstract: 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. Show more

Keywords: Hilbert programme, Gödel theorems, Church-Turing thesis, incompleteness

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 43-52, 2005

Authors: Câmpeanu, Cezar | Kari , Lila | Păun, Andrei

Article Type: Research Article

Abstract: 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). Show more

Keywords: Finite automata, deterministic automata, nondeterministic automata, cover automata, state complexity

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 53-63, 2005

Authors: Cavaliere, Matteo | Sburlan, Dragoş

Article Type: Research Article

Abstract: 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. Show more

Keywords: Membrane systems, synchronization, time, time-free, universality

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 65-77, 2005

Authors: Ceterchi, Rodica | Gramatovici, Radu

Article Type: Research Article

Abstract: 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.

Keywords: Total contextual grammars, n-contextual grammars, contextual grammars with restricted choice, local contextual grammars

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 79-91, 2005

Authors: Ciobanu, Gabriel | Gontineac, Mihai

Article Type: Research Article

Abstract: 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.

Keywords: genetic code, transcription, translation, (semi)automata, transformation semigroups, coverings, restricted direct product, cascade product

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 93-107, 2005

Authors: Dassow, Jürgen

Article Type: Research Article

Abstract: 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.

Keywords: Contextual grammars, controlled derivations, subregular languages

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 109-118, 2005