Fundamenta Informaticae - Volume 92, issue 1-2

Authors: Bouyer, Patricia | Haddad, Serge | Reynier, Pierre-Alain

Article Type: Research Article

Abstract: In this work, we study decision problems related to timed automata with silent transitions (TA_{ϵ} ) which strictly extend the expressiveness of timed automata (TA). We first answer negatively a central question raised by the introduction of silent transitions: can we decide whether the language recognized by a TA_{ϵ} can be recognized by some TA? Then we establish in the framework of TA_{ϵ} some old open conjectures that O. Finkel has recently solved …for TA. His proofs follow a generic scheme which relies on the fact that only a finite number of configurations can be reached by a TA while reading a timed word. This property does not hold for TA_{ϵ} , the proofs in the framework of TA_{ϵ} thus require more elaborated arguments. We establish undecidability of complementability, minimization of the number of clocks, and closure under shuffle. We also show these results in the framework of infinite timed languages. Show more

Keywords: Timed automata, silent transitions, decidability

DOI: 10.3233/FI-2009-0063

Citation: Fundamenta Informaticae, vol. 92, no. 1-2, pp. 1-25, 2009

Authors: Chang, Chin-Chen | Chen, Tzung-Her | Liu, Li-Jen

Article Type: Research Article

Abstract: Visual Cryptography (VC) has drawn much attention for providing the service of secret communication. Basically, VC is the process of encoding a secret into several meaningless shares and later decoding the secret by superimposing all or some of the shares without any computation involved. VC has been adopted to support some practical applications, such as image authentication, visual authentication, image hiding, and digital watermarking. Unfortunately, in many applications, VC has been shown to suffer from the …"cheating problem" in which the disclosed secret image may be altered by malicious insiders who are called "cheaters." While ubiquitous computing has been well developed, it has recently occurred to people in both academia and industry that research could benefit more from computational VC by introducing light-weight computation costs in the decoding phase. In this paper, a simple scheme is proposed to conquer the cheating problem by facilitating the capability of share authentication. It is worthwhile to note that the proposed scheme can identify for certain whether cheating attacks have occurred or not, while other schemes that have the same objective frequently provide a vague answer. In addition, the proposed scheme effectively addresses the two main problems of VC, i.e., the inconvenience of meaningless share management and the challenge of achieving difficult alignment. Show more

Keywords: Visual cryptography, secret sharing, cheating problem

DOI: 10.3233/FI-2009-0064

Citation: Fundamenta Informaticae, vol. 92, no. 1-2, pp. 27-42, 2009

Authors: Czerniak, Jacek

Article Type: Research Article

Abstract: This article presents the LDGen method which is based on genetic algorithm. The author proposed evolutionary approach to the solution of the discretization problem for systems that induce rules on the basis of rough sets theory. The study describes details of the method with special focus on the crossing operator. The proposed approach concerns working with multidimensional samples. Thanks to application of the author's own method of for visualizing multidimensionality, i.e. so called Pipes of Samples, …it was possible to visualize up to 360 dimensions, which is usually sufficient in case of problems the Rough Sets Theory deals with. Mutation and crossing methods were developed using this visualisation so that, for real numbers, it allowed to create individuals that describe one solution of the discretization. Hence the population is a set of many complete discretizations of all the attributes. Show more

Keywords: Discretization, LDGen, Rough Sets Theory, Genetic Algorithm, Pipe of Samples

DOI: 10.3233/FI-2009-0065

Citation: Fundamenta Informaticae, vol. 92, no. 1-2, pp. 43-61, 2009

Authors: Fredriksson, Kimmo | Nikitin, Fedor

Article Type: Research Article

Abstract: Given a sequence S of n symbols over some alphabet Σ of size σ, we develop new compression methods that are (i) very simple to implement; (ii) provide O(1) time random access to any symbol (or short substring) of the original sequence. Our simplest solution uses at most 2h+o(h) bits of space, where h = n(H_{0} (S)+1), and H_{0} (S) is the zeroth-order empirical entropy of S. We discuss a number of improvements …and trade-offs over the basic method. For example, we can achieve n(H_{k} (S)+1)+o(n(H_{k} (S)+1)) bits of space, for k = o(log_{σ} (n)). Several applications are discussed, including text compression, (compressed) full-text indexing and string matching. Show more

Keywords: succinct data structures, text compression, string matching, full-text indexing

DOI: 10.3233/FI-2009-0066

Citation: Fundamenta Informaticae, vol. 92, no. 1-2, pp. 63-81, 2009

Authors: Hartmann, Sven | Link, Sebastian

Article Type: Research Article

Abstract: Nesting is a useful technique in many areas of database practice. For instance, nesting is a fundamental operation for the nested relational data model, it can be applied to reduce the level of data redundancy in a database instance, to improve query processing or to convert data from one model to another. We further address the question when nesting operations commute with one another, i.e., when the final nested database relation is independent of …the order in which the nesting operations are applied. In fact, it has been shown that the satisfaction of weakmultivalued dependencies provides a sufficient and necessary condition for the commutativity of nesting operations. We study inference systems for different notions of implication for weak multivalued dependencies. First, we establish an axiomatisation with the property that every weak multivalued dependency can be inferred either without any application of the complementation rule or by a single application of the complementation rule necessary only in the very last step of the inference. Consequently, the complementation rule is a mere means to achieve a decomposition of the database. Secondly, we drop the assumption of having a fixed underlying schema, and establish an axiomatisation of weak multivalued dependencies for the notion of implication in this context. Show more

Keywords: Logic in Databases, Nested Relation, Weak Multivalued Dependency, Inference System

DOI: 10.3233/FI-2009-0067

Citation: Fundamenta Informaticae, vol. 92, no. 1-2, pp. 83-102, 2009

Authors: Högberg, Johanna | Maletti, Andreas | Vogler, Heiko

Article Type: Research Article

Abstract: Several models of automata are available that operate unranked trees. Two well-known examples are the stepwise unranked tree automaton (suta) and the parallel unranked tree automaton (puta). By adding a weight, taken from some semiring, to every transition we generalise these two qualitative automata models to quantitative models, thereby obtaining weighted stepwise unranked tree automata (wsuta) and weighted parallel unranked tree automata (wputa); the qualitative automata models are reobtained by choosing the BOOLEAN semiring. …The weighted versions have applications in natural language processing, XML-based data management and quantitative information retrieval. We address the minimisation problem of wsuta and wputa by using (forward and backward) bisimulations and we prove the following results: (1) for every wsuta an equivalent forward (resp. backward) bisimulation minimal wsuta can be computed in time O(mn) where n is the number of states and m is the number of transitions of the given wsuta; (2) the same result is proved for wputa instead of wsuta; (3) if the semiring is additive cancellative or the BOOLEAN semiring, then the bound can be improved to O(mlog n) for both wsuta and wputa; (4) for every deterministic puta we can compute a minimal equivalent deterministic puta in time O(mlog n); (5) the automata models wsuta, wputa, and weighted unranked tree automaton have the same computational power. Show more

Keywords: bisimulation, minimisation, automata, unranked trees

DOI: 10.3233/FI-2009-0068

Citation: Fundamenta Informaticae, vol. 92, no. 1-2, pp. 103-130, 2009

Authors: Hung, Kuo Lung | He, Shin-Wei

Article Type: Research Article

Abstract: This work, proposes a robust digital watermarking scheme based on feature points as a defense against illegal user attacks, such as, rotating, scaling and translation. First of all, a Gaussian filter is first adopted to discover the invariant feature points. The local maximum and the local minimum values are then calculated from those feature points. The Affine Invariant Region (AIR) is then divided by combination the values: local maximum, local minimum values and the center of …mass. The AIR region is then transformed using affine transform to a block image, called the normalized image, in which the size of the block image is predefined. The watermarks are then embedded into the normalized image. Experimental results indicate that the proposed method can still extract the correct watermark, even after a geometric attack. The proposed method has a lower false positive rate and higher accuracy than Lu's [12] that making it a robust blind watermarking scheme. Show more

Keywords: Normalization, Gaussian filter, DWT, affine transformation, geometric attacks

DOI: 10.3233/FI-2009-0069

Citation: Fundamenta Informaticae, vol. 92, no. 1-2, pp. 131-143, 2009

Authors: Verma, Rakesh

Article Type: Research Article

Abstract: We present several new and some significantly improved polynomial-time reductions between basic decision problems of term rewriting systems. We prove two theorems that imply tighter upper bounds for deciding the uniqueness of normal forms (UN^{=} ) and unique normalization (UN^{→} ) properties under certain conditions. From these theorems we derive a new and simpler polynomial-time algorithm for the UN^{=} property of ground rewrite systems, and explicit upper …bounds for both UN^{=} and UN^{→} properties of left-linear right-ground systems. We also show that both properties are undecidable for right-ground systems. It was already known that these properties are undecidable for linear systems. Hence, in a sense the decidability results are "close" to optimal. Show more

Keywords: Term rewriting systems, decision problems, reductions, confluence, existence of normal form, uniqueness of normal forms, reachability, joinability, unique normalization

DOI: 10.3233/FI-2009-0070

Citation: Fundamenta Informaticae, vol. 92, no. 1-2, pp. 145-168, 2009

Authors: Waszkiewicz, Paweł

Article Type: Research Article

Abstract: This paper is about a generalization of Scott's domain theory in such a way that its definitions and theorems become meaningful in quasimetric spaces. The generalization is achieved by a change of logic: the fundamental concepts of original domain theory (order, way-below relation, Scott-open sets, continuous maps, etc.) are interpreted as predicates that are valued in an arbitrary completely distributive Girard quantale (a CDG quantale). Girard quantales are known to provide a sound and complete semantics …for commutative linear logic, and complete distributivity adds a notion of approximation to our setup. Consequently, in this paper we speak about domain theory based on commutative linear logic with some additional reasoning principles following from approximation between truth values. Concretely, we: (1) show how to define continuous Q-domains, i.e. continuous domains over a CDG quantale Q; (2) study their way-below relation, and (3) study the rounded ideal completion of Q-abstract bases. As a case study, we (4) demonstrate that the domain-theoretic construction of the Hoare, Smyth and Plotkin powerdomains of a continuous dcpo can be straightforwardly adapted to yield corresponding constructions for continuous Q-domains. Show more

Keywords: (generalized) continuous domains, (generalized) way-below relation, rounded ideal completion

DOI: 10.3233/FI-2009-0071

Citation: Fundamenta Informaticae, vol. 92, no. 1-2, pp. 169-192, 2009