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

Authors: Davidson, Michael | Ilie, Lucian

Article Type: Research Article

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

Keywords: Text compression, antidictionaries, finite transducers, ε-free transducers, de Bruijn words

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

Authors: Dinu, Liviu P.

Article Type: Research Article

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

Keywords: Rank distance, similarities, tree-to-tree distance, computing with words, classifications, similarity of Romance languages

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

Authors: Dömösi, Pál | Kudlek, Manfred

Article Type: Research Article

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

Keywords: Regular language, finite automaton, pumping lemma

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

Authors: Fernau, Henning | Freund, Rudolf | Holzer, Markus

Article Type: Research Article

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

Keywords: Arrays, array grammars, contextual grammars, shape

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

Authors: Gramatovici, Radu | Manea, Florin

Article Type: Research Article

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

Keywords: Contextual grammar, parsing, polynomial complexity

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

Authors: Head, Tom

Article Type: Research Article

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

Keywords: Light & life, astrobiology, cosmos, awareness

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

Authors: Ipate, Florentin | Bălănescu, Tudor

Article Type: Research Article

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

Keywords: Finite state machines, testing, test generation, verification, W-method

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

Authors: Ipate, Florentin | Holcombe, Mike

Article Type: Research Article

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

Keywords: Testing, test generation, verification, stream X-machines, finite state machines

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

Authors: Jurdziński, Tomasz | Otto, Friedrich | Mráz, František | Plátek, Martin

Article Type: Research Article

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

Keywords: Contextual grammars, restarting automata, right-left monotonicity

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

Authors: Kappes, Martin

Article Type: Research Article

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

Keywords: Contextual grammars, bracketed contextual grammars

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

Authors: Krishna, Shankara Narayanan | Rama, R. | Ramesh, H.

Article Type: Research Article

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

Keywords: P systems, contextual grammars, replicated rewriting, leftmost rewriting, recursively enumerable languages

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

Authors: Kudlek, Manfred

Article Type: Research Article

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

Keywords: Contextual grammar, probabilistic grammar, multiset

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

Authors: Manca, Vincenzo

Article Type: Research Article

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

Keywords: DNA structure, bilinearity, complementarity, antiparallelism, DNA helix, DNA computing

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

Authors: Mardare, Radu | Priami, Corrado

Article Type: Research Article

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

Keywords: Hypersets, process algebra, ambient calculus, temporal logics, model checking

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

Authors: Margenstern, Maurice | Verlan, Sergey | Rogozhin, Yurii

Article Type: Research Article

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

Keywords: Biomolecular computing, splicing systems, formal grammars

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

Authors: Mitrana, Victor

Article Type: Research Article

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

Keywords: External contextual grammars, multi-dimensional external contextual grammars, range concatenation grammars

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

Authors: Mutyam, Madhu | Krithivasan, Kamala | Reddy, A. Siddhartha

Article Type: Research Article

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

Keywords: Insertion grammar, contextual grammar, recursively enumerable languages, Penttonen normal form, Kuroda normal form

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

Authors: Novotný, Miroslav

Article Type: Research Article

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

Keywords: Contextual hypergrammar, contextual grammar, reducing operator

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

Authors: Okhotin, Alexander | Salomaa, Kai

Article Type: Research Article

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

Keywords: Contextual grammar, trajectory, regular language, context-free language

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

Authors: Păun, Gheorghe | Pérez-Jiménez, Mario J. | Pazos, Juan | Rodríguez-Patón, Alfonso

Article Type: Research Article

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

Keywords: Membrane computing, Turing computability, register machine, symport/antiport

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

Authors: Pawlak, Zdzisław

Article Type: Research Article

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

Keywords: Flow graphs, data mining, information flow, intelligent data analysis, Bayes' rule

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

Authors: Polkowski, Lech | Semeniuk-Polkowska, Maria

Article Type: Research Article

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

Keywords: rough mereology, logics for rough sets, similarity relations

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

Authors: Salomaa, Arto

Article Type: Research Article

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

Keywords: Subword, scattered subword, number of subwords, Parikh matrix, ambiguity

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

Authors: Scollo, Giuseppe

Article Type: Research Article

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

Keywords: state transition dynamics, attractor, periodicity, quasiperiodicity, infinitary rewriting

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

Authors: Skowron, Andrzej

Article Type: Research Article

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

Keywords: vague concept approximation, reasoning about vague concepts, approximation spaces, rough sets, inductive extensions, granulation of approximation spaces, adaptive learning

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

Authors: Tatar, Doina

Article Type: Research Article

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

Keywords: Word sense disambiguation, machine learning, context

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

Authors: Titchener, Mark R. | Nicolescu, Radu | Staiger, Ludwig | Gulliver, Aaron | Speidel, Ulrich

Article Type: Research Article

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

Keywords: Formal languages, generative systems, prefix codes, complexity measures, T-codes, entropy, information

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

Authors: Tomescu, Ioan

Article Type: Research Article

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

Keywords: Word, factor, recurrence relation, characteristic equation, pseudo-Vandermonde determinant, autocorrelation polynomial, generating function

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

Authors: Yu, Sheng

Article Type: Research Article

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

Keywords: State complexity, regular languages, finite languages, finite automata

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