Fundamenta Informaticae - Volume 109, issue 2

Authors: Chang, Chin-Chen | Lin, Chih-Yang | Fan, Yi-Hsuan

Article Type: Research Article

Abstract: Reversible steganography becomes a popular hiding problem in recent years. A reversible steganographicmethod can reconstruct an original image without loss from the stego-image after extracting the embedded data. Unlike traditional reversible methods in which data is hidden in uncompressed images, we propose a reversible scheme for BTC (block truncation coding)-compressed images. The secret data embedded in the compressed image are more difficult to detect than in the uncompressed image. To achieve reversibility, the properties of side matching and BTC-compressed code are applied. The experimental results show that the proposed method is feasible for BTC-compressed images and can embed one more …bit in each BTC-encoded block. Show more

Keywords: Reversible data hiding, block truncation coding (BTC), steganography

DOI: 10.3233/FI-2011-500

Citation: Fundamenta Informaticae, vol. 109, no. 2, pp. 121-134, 2011

Authors: Gorrieri, Roberto | Versari, Cristian

Article Type: Research Article

Abstract: A2 CCS is a conservative extension of CCS, enriched with an operator of strong prefixing, enabling the modeling of atomic sequences and multi-party synchronization (realized as an atomic sequence of binary synchronizations); the classic dining philosophers problem is used to illustrate the approach. A step semantics for A2 CCS is also presented directly as a labeled transition system. A safe Petri net semantics for this language is presented, following the approach of Degano, De Nicola, Montanari and Olderog. We prove that a process p and its associated net Net(p) are interleaving bisimilar (Theorem 5.1). Moreover, to support the claim that …the intended concurrency is well-represented in the net, we also prove that a process p and its associated net Net(p) are step bisimilar (Theorem 5.2). Show more

DOI: 10.3233/FI-2011-501

Citation: Fundamenta Informaticae, vol. 109, no. 2, pp. 135-160, 2011

Authors: Jirásková, Galina | Okhotin, Alexander

Article Type: Research Article

Abstract: The state complexity of the star of union of an m-state DFA language and an n-state DFA language is proved to be 2m+n−1 −2m−1 −2n−1 +1 for every alphabet of at least two letters. The state complexity of the star of intersection is established as 3/4 2mn for every alphabet of six or more letters. This improves the recent results of A. Salomaa, K. Salomaa and Yu (“State complexity of combined operations”, Theoret. Comput. Sci., 383 (2007) 140–152).

Keywords: Descriptional complexity, finite automata, state complexity, combined operations

DOI: 10.3233/FI-2011-502

Citation: Fundamenta Informaticae, vol. 109, no. 2, pp. 161-178, 2011

Authors: Niu, Yunyun | Pan, Linqiang | Pérez-Jiménez, Mario J. | Font, Miquel Rius

Article Type: Research Article

Abstract: A tissue P system with cell division is a computing model which has two basic features: intercellular communication and the ability of cell division. The ability of cell division allows us to obtain an exponential amount of cells in linear time and to design cellular solutions to computationally hard problems in polynomial time. In this work we present an efficient solution to the tripartite matching problem by a family of such devices. This solution leads to an interesting open problem whether tissue P systems with cell division and communication rules of length 2 can solve NP-complete problems. An answer to …this open problem will provide a borderline between efficiency and non-efficiency in terms of the lengths of communication rules. Show more

Keywords: Membrane Computing, Tissue P System, Cell Division, Tripartite Matching Problem

DOI: 10.3233/FI-2011-503

Citation: Fundamenta Informaticae, vol. 109, no. 2, pp. 179-188, 2011

Authors: Wang, Xu An | Yang, Xiaoyuan | Zhang, Minqing

Article Type: Research Article

Abstract: In Informatica 32 (2008), Ren and Gu proposed an anonymous hierarchical identity based encryption scheme based on the q-ABDHE problem with full security in the standard model. Later in Indocrypt'08, they proposed another secure hierarchical identity based encryption scheme based on the q-TBDHE problem with full security in the standard model. They claimed that their schemes have short parameters, high efficiency and tight reduction. However, in this paper we give attacks to show their schemes are not secure at all. Concretely, from any first level private key, the adversary can easily derive a “private key” which can decrypt any ciphertexts …for the target identity. That is to say, a query on any first level identity is enough to decrypt any ciphertext in the system. Show more

Keywords: Cryptography, hierarchical identity based encryption, fully secure, attack

DOI: 10.3233/FI-2011-504

Citation: Fundamenta Informaticae, vol. 109, no. 2, pp. 189-200, 2011

Authors: Winkowski, Józef

Article Type: Research Article

Abstract: The paper is concerned with algebras whose elements can be used to represent runs of a system from a state to a state. These algebras, called multiplicative transition systems, are categories with respect to a partial binary operation called composition. They can be characterized by axioms such that their elements and operations can be represented by partially ordered multisets of a certain type and operations on such multisets. The representation can be obtained without assuming a discrete nature of represented elements. In particular, it remains valid for systems with infinitely divisible elements, and thus also for systems with elements which …can represent continuous and partially continuous runs. Show more

Keywords: Transition systems, states, transitions, composition, category, independence, regions, labelled posets, pomsets

DOI: 10.3233/FI-2011-505

Citation: Fundamenta Informaticae, vol. 109, no. 2, pp. 201-222, 2011