109(1) 2011


  1. From Glushkov WFAs to  K-Expressions
    Pascal Caron,  Marianne Flouret 1-25
    We take an active interest in the problem of conversion of a Weighted Finite Automaton (WFA) into a K-expression. The known algorithms give an exponential size expression in the number of states of the given automaton. We study the McNaughton-Yamada algorithm in the case of multiplicities and then we show that the resulting  K-expression is in the Star Normal Form (SNF) defined by Brüggemann-Klein [3].
    The Glushkov algorithm computes an (n+1)-state automaton from an expression having n occurrences of letters even in the multiplicity case [5]. We reverse this procedure and get a linear size  K-expression from a Glushkov WFA. A characterization of Glushkov WFAs which are not in SNF is given. This characterization allows us to emphasize a normal form for  K-expressions. As for SNF in the boolean case, we show that every  K-expression has an equivalent one in normal form having the same Glushkov WFA. We end with an algorithm giving a small normal form  K-expression from a Glushkov WFA.
  2. Constraint Satisfaction Problems in Clausal Form I: Autarkies and Deficiency
    Oliver Kullmann 27-81
    We consider the problem of generalising boolean formulas in conjunctive normal form by allowing non-boolean variables, with the goal of maintaining combinatorial properties. Requiring that a literal involves only a single variable, the most general form of literals are the well-known "signed literals", corresponding to unary constraints in CSP. However we argue that only the restricted form of "negative monosigned literals" and the resulting generalised clause-sets, corresponding to "sets of no-goods" in the AI literature, maintain the essential properties of boolean conjunctive normal forms. In this first part of a mini-series of two articles, we build up a solid foundation for (generalised) clause-sets, including the notion of autarky systems, the interplay between autarkies and resolution, and basic notions of (DP-)reductions. As a basic combinatorial parameter of generalised clause-sets we introduce the (generalised) notion of deficiency, which in the boolean case is the difference between the number of clauses and the number of variables. Autarky theory plays a fundamental role here, and we concentrate especially on matching autarkies (based on matching theory). A natural task is to determine the structure of (matching) lean clause-sets, which do not admit non-trivial (matching) autarkies. A central result is the computation of the lean kernel (the largest lean subset) of a (generalised) clause-set in polynomial time for bounded maximal deficiency.
  3. Constraint Satisfaction Problems in Clausal Form II: Minimal Unsatisfiability and Conflict Structure
    Oliver Kullmann 83-119
    Concluding this mini-series of 2 articles on the foundations of generalised clause-sets, we study the combinatorial properties of non-boolean conjunctive normal forms (clause-sets), allowing arbitrary (but finite) sets of values for variables, while literals express that some variable shall not get some (given) value. First we study the properties of the direct translation (or "encoding") of generalised clause-sets into boolean clause-sets. Many combinatorial properties are preserved, and as a result we can lift fixed-parameter tractability of satisfiability in the maximal deficiency from the boolean case to the general case. Then we turn to irredundant clause-sets, which generalise minimally unsatisfiable clause-sets, and we prove basic properties. The simplest irredundant clause-sets are hitting clause-sets, and we provide characterisations and generalisations. Unsatisfiable irredundant clause-sets are the minimally unsatisfiable clause-sets, and we provide basic tools. These tools allow us to characterise the minimally unsatisfiable clause-sets of minimal deficiency. Finally we provide a new translation of generalised boolean clause-sets into boolean clause-sets, the nested translation, which preserves the conflict structure. As an application, we can generalise results for boolean clause-sets regarding the hermitian rank/defect, especially the characterisation of unsatisfiable hitting clause-sets where between every two clauses we have exactly one conflict. We conclude with a list of open problems, and a discussion of the "generic translation scheme".

109 (2) 2011


  1. Reversible Steganography for BTC-compressed Images
    Chin-Chen Chang,  Chih-Yang Lin  Yi-Hsuan Fan 121-134
    Reversible steganography becomes a popular hiding problem in recent years. A reversible steganographic method 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.
  2. An Operational Petri Net Semantics for A2CCS
    Roberto Gorrieri,  Cristian Versari 135-160
    A2CCS 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 A2CCS 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).
  3. On the State Complexity of Star of Union and Star of Intersection
    Galina Jirásková,  Alexander Okhotin 161-178
    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).
  4. A Tissue P Systems Based Uniform Solution to Tripartite Matching Problem
    Yunyun Niu,  Linqiang Pan,  Mario J. Pérez-Jiménez,  Miquel Rius Font 179-188
    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.
  5. Cryptanalysis of Two Efficient HIBE Schemes in the Standard Model
    Xu An Wang,  Xiaoyuan Yang,  Minqing Zhang 189-200
    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.
  6. Multiplicative Transition Systems
    Józef Winkowski 201-222
    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.

109(3) 2011


  1. Concurrency Specification and Programming (CS&P). Preface i-i
  2. Resource Driven Automata Nets
    Vladimir A. Bashkin,  Irina A. Lomazova 223-236
    A new formalism of Resource Driven Automata Nets (RDA-nets) is presented. A RDA-net has two levels: a system level is represented by a net of active resources, describing distribution of agents/resources and their interactions; agents in an object level are finite automata, communicating via ports and shared resources of a system level. RDA-nets are assigned for modeling mobility in multi-agent systems from the resource dependence perspective. We prove that RDA-nets have the same expressive power as Petri nets and give examples of modeling agent communications, dynamics and mobility.
  3. Properties of Java Simple Closures
    Marco Bellia and M. Eugenia Occhiuto 237-253
    In the last years, the Java community has been arguing about adding closures to Java in order to improve expressivity. The debate has not yet terminated but all proposals seem to converge towards a notion of Simple Closures which contain only the essential features of anonymous functions. This paper addresses the problem of defining a rigorous semantics for Simple Closures. The technique adopted is well known and has already been used to prove interesting properties of other extensions of Java. A minimal calculus is defined: Featherweight Java extended with Simple Closures. Syntax and semantics of such a calculus are defined and type safety, backward compatibility, and the abstraction property are proved.
  4. On Deadlock and Fairness Decision Problems for Computations on Client-server Systems
    Ludwik Czaja 255-264
    Phenomena that inherently happen in distributed computing - some types of deadlock and fairness or starvation - are examined in a client-server model. Messages travelling between clients and a server are: request for an action, permission to start it, and termination of its execution. Deadlock-prone and (un)fair behaviours are formulated for the model and equivalence of the respective formulae to formulae expressing emptiness and finiteness of some sets generated by the model is established. >From these results, some answers to decision problems for the aforesaid properties are obtained. Furthermore, equivalence between the so-called strong fairness (specified by first-order formula) and weak-fairness (second-order formula) is demonstrated.
  5. A Logic-Algebraic Approach to Graded Inclusion
    Anna Gomoli˝ska 265-279
    In this article we continue searching for functions which might be used as measures of inclusion of information granules in information granules. Starting with a 3-valued logic having an adequate logical matrix, we show how to derive a corresponding graded inclusion function. We report on the results of examination of several best known 3-valued logics in this respect. We also give some basic properties of the inclusion functions obtained.
  6. Gained and Excluded Private Actions by Process Observations
    Damas P. Gruska 281-295
    Formalisms for description how much information on private actions can be obtained by observing public ones are presented. Two sets of private actions are considered. The set of actions which execution is guaranteed according to observations and the set of actions which execution is excluded according to observations. Since information flows could be realized also by means of different covert channels as time, termination and divergence this possibility is considered as well. Both qualitative and quantitative dimensions of the flow are considered.
  7. A Relation between Modal Logic and Language Closure Operators
    Manfred Kudlek 297-304
    Between modal logic and closure operators for topological spaces as well as for formal languages there exists a strong relation. Modal logic allows to define classes of formal languages in several ways.
  8. BDD-based Bounded Model Checking for Temporal Properties of 1-Safe Petri Nets
    Artur Mŕski,  Wojciech Penczek,  Agata Pó│rola 305-321
    In the paper we present a bounded model checking for 1-safe Petri nets and properties expressed in LTL and the universal fragment of CTL, based on binary decision diagrams. The presented experimental results show that we have obtained a technique which performs better in some of the considered cases, in comparison with the existing SAT-based implementation. The results are also compared with standard BDD-based symbolic method.
  9. BITES Instead of FIRST for Parsing Expression Grammar
    Roman R. Redziejowski 323-337
    In an earlier paper, the author adapted to Parsing Expression Grammars (PEGs) the properties FIRST and FOLLOW used in the construction of predictive top-down parsers. The purpose was to obtain warnings for possible "language hiding". It turned out that FIRST does not work well with lookahead expressions. To repair this, it is replaced here by a property named BITES that is a set of input strings instead of terminals.
  10. Function Approximation and Quality Measures in Rough-Granular Systems
    Marcin Szczuka,  Andrzej Skowron,  Jaros│aw Stepaniuk 339-354
    We discuss the problem of measuring the quality of decision support (classification) system that involves granularity based on rough set concepts. We put forward the proposal for such quality measure in the case when the underlying granular system is based on rough sets and makes use of approximation spaces. We introduce the notion of approximation, loss function, and quality measures that are inspired by empirical risk assessment for classifiers in the field of statistical learning. We further discuss the possibilities of improving the quality measure by extrapolating the loss function using function approximation methods originating in extensions of the concept of approximation space.
  11. Incomplete and Nondeterministic Information Systems: Object-Directed Semantics for Descriptor Languages
    Marcin Wolski 355-368
    In the paper we discuss logical approaches to incomplete and/or nondeterministic data. As is well-known, complete and deterministic information systems induce indiscernibility relations and the lower and upper approximations regarded as operators obey the laws of S5 modal system. In the case of incomplete and/or nondeterministic systems, this modal approach yields a few more binary relations on the set of objects (e.g. NIL-structures and NIL-logics). Anyway, in both cases, there are relations which play a dominant role. The main idea of this study is to shift the focus from relations to objects - that is why we use the term object-directed. Following well-established traditions from modal logics, we would like to consider objects with empty or non-single attribute values as a special kind of worlds. In consequence, in the object-directed approach there would be two sorts of objects and (usually) one relation in contrast to the relation-directed approach where we have one sort of objects and a number of relations. In the first part of our paper we shall discuss a global kind of non-normality and show how rough approximations can be linked to weak modal systems. In the second part we shall consider a local kind of non-normality; this time we use a multi-valued modal system Q introduced by A. N. Prior. The key idea offered by the paper is to regard incomplete and/or nondeterministic information systems as a source of non-normal models for (modal) descriptor languages.

109(4) 2011


  1. Stephen L. Bloom 1940-2010
    Zoltán Ésik and Klaus Sutner 369-381
  2. eDonkey & eMule's Kad: Measurements & Attacks
    Thomas Locher,  Stefan Schmid,  Roger Wattenhofer 383-403
    This article reports on the results of our measurement study of the Kad network. Although several fully decentralized peer-to-peer systems have been proposed in the literature, most existing systems still employ a centralized architecture. The Kad network is a notable exception. Since the demise of the Overnet network, the Kad network has become the most popular peer-to-peer system based on a distributed hash table. It is likely that its user base will continue to grow in numbers over the next few years due to the system's scalability and reliability.
    The contribution of the article is twofold. First, we compare the two networks accessed by eMule: the centralized paradigm of the eDonkey network and the structured, distributed approach pursued by the Kad network. We re-engineer the eDonkey server software and integrate two modified servers into the eDonkey network in order to monitor traffic. Additionally, we implement a Kad client exploiting a design weakness to spy on the traffic at arbitrary locations in the ID space. The collected data provides insights into the spacial and temporal distributions of the peers' activity. Moreover, it allows us to study the searched content. The article also discusses problems related to the collection of such data sets and investigates techniques to verify the representativeness of the measured data.
    Second, this article shows that today's Kad network can be attacked in several ways. Our simple attacks could be used either to hamper the correct functioning of the network itself, to censor content, or to harm other entities in the Internet not participating in the Kad network, such as ordinary web servers. While there are heuristics to improve the robustness of Kad, we believe that the attacks cannot be thwarted easily in a fully decentralized peer-to-peer system, i.e., without some kind of a centralized certification and verification authority. This result may be relevant in the context of the current debate on the design of a clean-slate network architecture for the Internet which is based on concepts known from the peer-to-peer paradigm.
  3. Transformations Between Different Models of Unranked Bottom-Up Tree Automata
    Xiaoxue Piao, Kai Salomaa 405-424
    We consider the representational state complexity of unranked tree automata. The bottom-up computation of an unranked tree automaton may be either deterministic or nondeterministic, and further variants arise depending on whether the horizontal string languages defining the transitions are represented by a DFA or an NFA. Also, we consider for unranked tree automata the alternative syntactic definition of determinism introduced by Cristau et al. (FCT'05, LNCS 3623, pp. 68-79). We establish upper and lower bounds for the state complexity of conversions between different types of unranked tree automata.
  4. Mesh Algorithms for Solving Principal Diophantine Equations, Sand-glass Tubes and Tori of Roots
    Daniel Simson 425-462
    We study integral solutions of diophantine equations q(x) = d, where x = (x1, ¼, xn), n ³ 1, d Z is an integer and q:Zn ® Z is a non-negative homogeneous quadratic form. Contrary to the negative solution of the Hilbert's tenth problem, for any such a form q(x), we give efficient algorithms describing the set q(d) of all integral solutions of the equation q(x) = d in a FA-mesh translation quiver form. We show in Section 5 that usually the set q(d) has a shape of a FA-mesh sand-glass tube or of a FA-mesh torus, see 5.8, 5.10, and 5.13. If, in addition, the subgroup Ker q={v Zn;   q(v) = 0} of Zn is infinite cyclic, we study the solutions of the equations q(x) = 1 by applying a defect A:Zn ® Z and a reduced Coxeter number \check cA N defined by means of a morsification bA:Zn×Zn ® Z of q, see Section 4. On this way we get a simple graphical algorithm that constructs all integral solutions in the shape of a mesh translation oriented graph consisting of Coxeter FA-orbits. It turns out that usually the graph has at most three infinite connected components and each of them has an infinite band shape, or an infinite horizontal tube shape, or has a sand-glass tube shape. The results have important applications in representation theory of groups, algebras, quivers and partially ordered sets, as well as in the study of derived categories (in the sense of Verdier) of module categories and categories of coherent sheaves over algebraic varieties.
  5. An Axiomatic Approach to the Roughness Measure of Rough Sets
    Ping Zhu 463-480
    In Pawlak's rough set theory, a set is approximated by a pair of lower and upper approximations. To measure numerically the roughness of an approximation, Pawlak introduced a quantitative measure of roughness by using the ratio of the cardinalities of the lower and upper approximations. Although the roughness measure is effective, it has the drawback of not being strictly monotonic with respect to the standard ordering on partitions. Recently, some improvements have been made by taking into account the granularity of partitions. In this paper, we approach the roughness measure in an axiomatic way. After axiomatically defining roughness measure and partition measure, we provide a unified construction of roughness measure, called strong Pawlak roughness measure, and then explore the properties of this measure. We show that the improved roughness measures in the literature are special instances of our strong Pawlak roughness measure and introduce three more strong Pawlak roughness measures as well. The advantage of our axiomatic approach is that some properties of a roughness measure follow immediately as soon as the measure satisfies the relevant axiomatic definition.
  6. Erratum to the paper: "A Logic-Based System for e-Tourism"
    Francesco Ricca,  Antonella Dimasi,  Giovanni Grasso, Salvatore Maria Ielpa, Salvatore Iiritano,  Marco Manna, and Nicola Leone 481