Fundamenta Informaticae - Volume 126, issue 1

Authors: Baader, Franz | Okhotin, Alexander

Article Type: Research Article

Abstract: Language equations are equations where both the constants occurring in the equations and the solutions are formal languages. They have first been introduced in formal language theory, but are now also considered in other areas of computer science. In the present paper, we restrict the attention to language equations with one-sided concatenation, but in contrast to previous work on these equations, we allow not just union but all Boolean operations to be used when formulating them. In addition, we are not just interested in deciding solvability of such equations, but also in deciding other properties of the set of solutions, …like its cardinality (finite, infinite, uncountable) and whether it contains least/greatest solutions. We show that all these decision problems are EXPTIME-complete. Show more

DOI: 10.3233/FI-2013-870

Citation: Fundamenta Informaticae, vol. 126, no. 1, pp. 1-35, 2013

Authors: Berghammer, Rudolf | Winter, Michael

Article Type: Research Article

Abstract: We introduce the decomposition of an arbitrary relation into a sequential composition of three relations, viz. of a mapping with a partial order and then the transpose of a mapping. After presenting some basic properties, we investigate the specific classes of junkfree, irreducible and minimal decompositions and show that for all relations a minimal decomposition exists. We also study decompositions with regard to DedekindMacNeille completions and concept lattices. These constructions are closely related to decompositions of relations. In our setting the fundamental theorem of concept lattices states that concept lattices are minimal-complete decompositions and all such decompositions are isomorphic. As …a further main result we prove that the cutDedekindMacNeille completion of the order that belongs to the minimal decomposition of a relation is isomorphic to the concept lattice of that relation. Instead of considering binary relations on sets, we will work point-free within the general framework of allegories. This complement-free approach implies that the results of the paper can be applied to all models of these algebraic structures, including, for instance, lattice-valued fuzzy relations. Show more

Keywords: Division allegory, power allegory, relation algebra, partial order, complete lattice, decomposition, concept lattice, cut completion

DOI: 10.3233/FI-2013-871

Citation: Fundamenta Informaticae, vol. 126, no. 1, pp. 37-82, 2013

Authors: Nagarajan, E.K.R. | Umadevi, D.

Article Type: Research Article

Abstract: In this paper, we give a characterization theorem for rough sets based on quasi order. We obtain an algebra on the rough sets system determined by a quasi order which is the generalization of the algebra of rough sets system determined by an equivalence relation given in [1]. The properties of this algebra are abstracted at various levels and define new class of algebras. Further we give a representation theorem for the new class of algebras.

Keywords: Rough sets, quasi order, weakly topological quasi-Boolean algebra, pre Q-rough algebra, Q-rough algebra

DOI: 10.3233/FI-2013-872

Citation: Fundamenta Informaticae, vol. 126, no. 1, pp. 83-101, 2013

Authors: Pan, Ping | Wang, Licheng | Yang, Yixian | Gan, Yuanju | Wang, Lihua | Xu, Chengqian

Article Type: Research Article

Abstract: In this paper, we build a family of chameleon hash functions and strongly unforgeable one-time signature schemes based on the intractability assumption of the discrete logarithm problem (DLP) over inner automorphism groups. Since the DLP assumption over inner automorphism groups does not admit sub-exponential attacks, thus the sizes of the working parameters used in our constructions are shorten significantly. This leads to remarkable gains for our proposals both in running time and in storage space. In addition, as far as we know, this is the first time to build CHF and OTS based on noncommutative groups.

Keywords: Chameleon Hash, One-Time Signature, Inner Automorphism Group, Discrete Logarithm Problem

DOI: 10.3233/FI-2013-873

Citation: Fundamenta Informaticae, vol. 126, no. 1, pp. 103-119, 2013