Fundamenta Informaticae - Volume 73, issue 1-2

Article Type: Other

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. i-i, 2006

Authors: Calude, Cristian S. | Câmpeanu, Cezar | Dumitrescu, Monica

Article Type: Research Article

Abstract: How likely is that a randomly given (non-) deterministic finite automaton recognizes no word? A quick reflection seems to indicate that not too many finite automata accept no word; but, can this intuition be confirmed? In this paper we offer a statistical approach which allows us to conclude that for automata, with a large enough number of states, the probability that a given (non-) deterministic finite automaton recognizes no word is close to zero. More precisely, we will …show, with a high degree of accuracy (i.e., with precision higher than 99% and level of confidence 0.9973), that for both deterministic and non-deterministic finite automata: a) the probability that an automaton recognizes no word tends to zero when the number of states and the number of letters in the alphabet tend to infinity, b) if the number of states is fixed and rather small, then even if the number of letters of the alphabet of the automaton tends to infinity, the probability is strictly positive. The result a) is obtained via a statistical analysis; for b) we use a combinatorial and statistical analysis. The present analysis shows that for all practical purposes the fraction of automata recognizing no words tends to zero when the number of states and the number of letters in the alphabet grow indefinitely. From a theoretical point of view, the result can motivate the search for "certitude" that is, a proof of the fact established here in probabilistic terms. In the last section we critically discuss the result and the method used in this paper. Show more

Keywords: Finite automata, emptiness problem, statistical analysis, sampling method

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 1-18, 2006

Authors: Ceterchi, Rodica

Article Type: Research Article

Abstract: An algebraic characterization of simple splicing languages given in [6] is extended to semi-simple splicing languages.

Keywords: DNA computing, splicing, algebraic characterization

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 19-25, 2006

Authors: Ciobanu, Gabriel | Păun, Gheorghe | Pérez-Jiménez, Mario J.

Article Type: Research Article

Abstract: We consider two complexity parameters related to the graph of reachable configurations of a given P system, namely the outdegree as a measure of the degree of non-determinism, and the indegree as a measure of the degree of confluence. These parameters can be defined for both the generative and the accepting mode of using a P system. We investigate here these parameters in what concerns hierarchies and decidability issues. We prove that all hierarchies have only …two levels and that all considered decidability problems have a negative answer. Show more

Keywords: Membrane computing, non-determinism, descriptional complexity, decidability

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 27-36, 2006

Authors: Csuhaj-Varjú, Erzsébet | Mateescu, Alexandru

Article Type: Research Article

Abstract: In this paper we discuss some relationships between cooperating distributed (CD) grammar systems and the basic process algebra (BPA) calculus. We associate different types of process graphs from this calculus to CD grammar systems which describe the behavior of the components of the system under cooperation. We prove that these process graphs form a subalgebra of the graph model of BPA. It is also shown that for certain restricted variants of CD grammar systems and for …certain types of these process graphs the bisimilarity of two process graphs is decidable. Show more

Keywords: Cooperating distributed grammar systems, basic process algebra, process graph

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 37-50, 2006

Authors: Ding, Cunsheng | Salomaa, Arto

Article Type: Research Article

Abstract: Secret sharing schemes, introduced by Blakley and Shamir independently in 1979, have a number of applications in security systems. One approach to the construction of secret sharing schemes is based on coding theory. In principle, every linear code can be used to construct secret sharing schemes. But only well structured linear codes give secret sharing schemes with nice access structures in the sense that every pair of participants plays the same role in the secret sharing. …In this paper, we construct a class of good linear codes, and use them to obtain a class of secret sharing schemes with nice access structures. Show more

Keywords: Secret sharing, linear codes, access structures

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 51-63, 2006

Authors: Ding, Cunsheng | Salomaa, Arto

Article Type: Research Article

Abstract: The paper investigates inference based on quantities |W|_u , the number of occurrences of a word u as a scattered subword of W. Parikh matrices recently introduced are useful tools for such investigations. We introduce and study universal languages for Parikh matrices. We also obtain results concerning the inference from numbers |W|_u to W, as well as from certain entries of a Parikh matrix to other entries.

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

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 65-79, 2006

Authors: Domaratzki, Michael | Rozenberg, Grzegorz | Salomaa, Kai

Article Type: Research Article

Abstract: We introduce generalized trajectories where the individual symbols are interpreted as operations performed on the operand words. The various previously considered trajectory-based operations can all be expressed in this formalism. It is shown that the generalized operations can simulate Turing machine computations. We consider the equivalence problem and a notion of unambiguity that is sufficient to make equivalence decidable for regular sets of trajectories under nonincreasing interpretations.

Keywords: Formal languages, decidability, trajectories, regularity, unambiguity

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 81-97, 2006

Authors: Droste, Manfred | Kari, Jarkko | Steinby, Paula

Article Type: Research Article

Abstract: We continue investigations of weighted finite automata (WFA) as devices to compute real functions. Based on eigenvalues of the transition matrices of automata we provide a simple necessary condition for continuity and smoothness properties of the functions they compute. Using this condition we show that polynomials are the only smooth functions computed by WFA and that any WFA computing a polynomial of degree k must have at least k+1 states. The results answer problems left open …in [7]. Show more

Keywords: Weighted finite automata, continuity, smoothness

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 99-106, 2006

Authors: Dumitrescu, Sorina

Article Type: Research Article

Abstract: We address the problem of designing optimal prefix-free codes over an encoding alphabet with unequal integer letter costs. The most efficient algorithm proposed so far has O(n^{C+2} ) time complexity, where n is the number of codewords and C is the maximum letter cost. For the special case when the encoding alphabet is binary, a faster solution was proposed, namely of O(n^C ) time complexity, based on a more sophisticated modeling of the problem, …and on exploiting the Monge property of the cost function. However, those techniques seemed not to extend to the r-letter alphabet. This work proves that, on the contrary, the generalization to the r-letter case is possible, thus leading to a O(n^C ) time complexity algorithm for the case of arbitrary number of letters. Show more

Keywords: Prefix-free codes, unequal letter costs, lopsided trees, optimization, Monge property

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 107-117, 2006