Fundamenta Informaticae - Volume 87, issue 3-4

Authors: Domaratzki, Michael

Article Type: Research Article

Abstract: We consider the use of DNA trajectories to characterize DNA bond shapes. This is an extension of recent work on the bond-free properties of a language. Using a new definition of bondfreeness, we show that we can increase the types of DNA bond shapes which are expressible. This is motivated by the types of bond shapes frequently found in DNA computing. We examine the algebraic properties of sets of DNA trajectories. In particular, we consider rotation of trajectories …and weakening of the bonding conditions expressed by a set of DNA trajectories. We also consider decidability results for bond-freeness with respect to our definition. Show more

Citation: Fundamenta Informaticae, vol. 87, no. 3-4, pp. 269-285, 2008

Authors: Fokkink, Wan | Pang, Jun | Wijs, Anton

Article Type: Research Article

Abstract: We show that timed branching bisimilarity as defined by Van der Zwaag [17] and Baeten and Middelburg [2] is not an equivalence relation, in case of a dense time domain. We propose an adaptation based on Van der Zwaag's definition, and prove that the resulting timed branching bisimilarity is an equivalence indeed. Furthermore, we prove that in case of a discrete time domain, Van der Zwaag's definition and our adaptation coincide. Finally, we prove that a …rooted version of timed branching bisimilarity is a congruence over a basic timed process algebra containing parallelism, successful termination and deadlock. Show more

Citation: Fundamenta Informaticae, vol. 87, no. 3-4, pp. 287-311, 2008

Authors: Hu, Yu-Chen | Tsai, Piyu | Lo, Chun-Chi

Article Type: Research Article

Abstract: A low bit rate image coding scheme based on vector quantization is proposed. In this scheme, the block prediction coding and the relative addressing techniques are employed to cut down the required bit rate of vector quantization. In block prediction coding, neighboring encoded blocks are taken to compress the current block if a high degree of similarity between them is existed. In the relative addressing technique, the redundancy among neighboring indices are exploited to reduce the …bit rate. From the results, it is shown that the proposed scheme significantly reduces the bit rate of VQ while keeping good image quality of compressed images. Show more

Keywords: Image Compression, Vector Quantization, Bit Rate Reduction, Block Prediction

Citation: Fundamenta Informaticae, vol. 87, no. 3-4, pp. 313-329, 2008

Authors: Juhás, Gabriel | Lorenz, Robert | Mauser, Sebastian

Article Type: Research Article

Abstract: In the first part of this paper we extend the semantical framework proposed in [22] for process and causality semantics of Petri nets by an additional aim, firstly mentioned in the habilitation thesis [15]. The aim states that causality semantics deduced from process nets should be complete w.r.t. step semantics of a Petri net in the sense that each causality structure which is enabled w.r.t. step semantics corresponds to some process net. In the second part of this …paper we examine several process semantics of different Petri net classes w.r.t. this aim. While it is well known that it is satisfied by the process semantics of place/transition Petri nets (p/t-nets), we show in particular that the process semantics of p/t-nets with weighted inhibitor arcs (PTI-nets) proposed in [22] does not satisfy the aim. We develop a modified process semantics of PTI-nets fulfilling the aim of completeness and also all remaining axioms of the semantical framework. Finally, we sketch results in literature concerning the aim of completeness for process definitions of various further Petri net classes. The paper is a revised and extended version of the conference paper [18]. Show more

Keywords: Petri Net, Inhibitor Net, Process Semantics, Causal Semantics, Completeness

Citation: Fundamenta Informaticae, vol. 87, no. 3-4, pp. 331-365, 2008

Authors: Macià, Hermenegilda | Valero, Valentín | Cuartero, Fernando | Ruiz, M. Carmen

Article Type: Research Article

Abstract: Petri Box Calculus (PBC) is an algebraicmodel for the description of concurrent systems and sPBC (stochastic Petri Box Calculus) is a Markovian extension of that model. In this paper we add immediate multiactions to sPBC in order to increase the description power of this language. Thus, we both have timed multiactions that follow an exponential distribution, and multiactions that do not require any time and can be immediately executed. The denotational semantics of this model is …based on a special class of GSPN (Generalized Stochastic Petri Nets), called gs-boxes. Show more

Keywords: Petri Box Calculus, Stochastic Process Algebra, Generalized Stochastic Petri Nets

Citation: Fundamenta Informaticae, vol. 87, no. 3-4, pp. 367-406, 2008

Authors: Masopust, Tomáš | Meduna, Alexander

Article Type: Research Article

Abstract: This paper presents some new results concerning the descriptional complexity of partially parallel grammars. Specifically, it proves that every recursively enumerable language is generated (i) by a four-nonterminal scattered context grammar with no more than four non-context-free productions, (ii) by a two-nonterminal multisequential grammar with no more than two selectors, or (iii) by a three-nonterminalmulticontinuous grammar with no more than two selectors.

Keywords: formal languages, scattered context grammars, multisequential grammars, multicontinuous grammars, descriptional complexity

Citation: Fundamenta Informaticae, vol. 87, no. 3-4, pp. 407-415, 2008

Authors: Mitra, Suman K. | Kundu, Malay K. | Murthy, C.A. | Bhattacharya, Bhargab B. | Acharya, Tinku

Article Type: Research Article

Abstract: Approximation of an image by the attractor evolved through iterations of a set of contractive maps is usually known as fractal image compression. The set of maps is called iterated function system (IFS). Several algorithms, with different motivations, have been suggested towards the solution of this problem. But, so far, the theory of IFS with probabilities, in the context of image compression, has not been explored much. In the present article we have proposed a new …technique of fractal image compression using the theory of IFS and probabilities. In our proposed algorithm, we have used a multiscaling division of the given image up to a predetermined level or up to that level at which no further division is required. At each level, the maps and the corresponding probabilities are computed using the gray value information contained in that image level and in the image level higher to that level. A fine tuning of the algorithm is still to be done. But, the most interesting part of the proposed technique is its extreme fastness in image encoding. It can be looked upon as one of the solutions to the problem of huge computational cost for obtaining fractal code of images. Show more

Keywords: Iterated function System (IFS), Collage theorem, measure, Markov operator, image compression

Citation: Fundamenta Informaticae, vol. 87, no. 3-4, pp. 417-433, 2008

Authors: Oprocha, Piotr

Article Type: Research Article

Abstract: Among the class of sofic shifts Devaney chaos is equivalent to topological transitivity. The aim of this paper is to study possibilities of detection of this phenomena when a right-resolving graph presentation of a sofic shift is given. We show that Devaney chaos detection is co-NP-hard problem and point out some possible improvements of algorithms known from the literature.

Keywords: Devaney chaos, sofic shift, symbolic dynamics, irreducible shift space, graph, complexity, NP-completness

Citation: Fundamenta Informaticae, vol. 87, no. 3-4, pp. 435-446, 2008

Authors: Tsai, Piyu | Hu, Yu-Chen | Yeh, Hsiu-Lien

Article Type: Research Article

Abstract: The codebook design in the vector quantization scheme is important because it affects the image quality of the encoded image. The Linde-Buzo-Gray (LBG) codebook generation algorithm is well known and a popular choice among codebook users. However, a heavy computational complexity is consumed for the iteratively clustering process in the LBG algorithm. In this paper, the similarity of codewords in consecutive rounds of the LBG algorithm is exploited to reduce the computational complexity. By checking the …stability of codewords, the status of each codeword in the codebook can be determined. Only the unstable codewords are refined to generate the new codebook. The proposed method can be further improved by cooperating with the finite state technique. Experimental results show that the computational complexity of the proposed method is reduced to about 4% of the LBG algorithm while achieving a slightly worse image quality. Show more

Keywords: LBG, Codebook, Stable codeword, Finite state

Citation: Fundamenta Informaticae, vol. 87, no. 3-4, pp. 447-463, 2008

Authors: Xiao, Kai | Ho, Sooi Hock | ella Hassanien, Aboul

Article Type: Research Article

Citation: Fundamenta Informaticae, vol. 87, no. 3-4, pp. 465-481, 2008