1,721,061 research outputs found
BuST-Bundled Suffix Trees
No full textWe introduce a data structure, the Bundled Suffix Tree (BUST), that is a generalization of a Suffix Tree (ST). To build a BuST we use an alphabet Σ together with a non-transitive relation ≈ among its letters. Following the path of a substring β within a BUST, constructed over a text α of length n, not only the positions of the exact occurrences of β in α are found (as in a ST), but also the positions of all the substrings α1, α2, α3 ⋯ that are related with β via the relation ≈ among the characters of ∑, for example strings at a certain “distance” from β. A BuST contains O(n 1+δ) additional nodes (δ < 1) in probability, and is constructed in O(n 1+δ) steps. In the worst case it contains O(n 2) nodes. Please use the following format when citing this chapter: Bortolussi, L., Fabris, F., Policriti, A., 2006, in International Federation for Information Processing, Volume 209, Fourth IFIP International Conference on Theoretical Computer Science-TCS 2006, eds. Navarro, G., Bertossi, L., Kohayakwa, Y., (Boston: Springer). pp. 91–102
Perspectives on Constraints, Process Algebras, and Hybrid Systems.
No full textBuilding on a technique for associating Hybrid Systems (HS) to stochastic programs written in a stochastic extension of Concurrent Constraint Programming (sCCP), we will discuss several aspects of performing such association. In particular, as we proved an sCCP program can be mapped in a HS
varying in a lattice at a level depending on the amount of actions to be simulated continuously, we will discuss what are the problems involved in a semi-automatic choice of such level. Decidability, semantic, and efficiency issues will be taken into account, with special emphasis on their links with biological applications. We will also discuss about the role of constraints and of the constraint store in this construction
Adding the power-set to description logics
No full textWe explore the relationships between Description Logics and Set Theory. The study is carried on using, on the set-theoretic side, a very rudimentary axiomatic set theory Ω, consisting of only four axioms characterizing binary union, set difference, inclusion, and the power-set. An extension of ALC, dubbed ALCΩ, is defined in which concepts are naturally interpreted as sets living in Ω-models. In ALCΩ not only membership between concepts is allowed—even admitting membership circularity—but also the power-set construct is exploited to add metamodelling capabilities. We investigate translations of ALCΩ into standard description logics as well as a set-theoretic translation. A polynomial encoding of ALCΩ in ALCOI proves the validity of the finite model property as well as an EXPTIME upper bound on the complexity of concept satisfiability. We develop a set-theoretic translation of ALCΩ in the theory Ω, exploiting a technique proposed for translating normal modal and polymodal logics into Ω. Finally, we show that the fragment LCΩ of ALCΩ not admitting roles and individual names, is as expressive as ALCΩ
Extending with the Power-Set Construct
No full textAbstract. We continue our exploration of the relationships between Description Logics and Set Theory, which started with the definition of the description logic ALCΩ. We develop a set-theoretic translation of the description logic ALCΩ in the set theory Ω, exploiting a technique originally proposed for translating normal modal and polymodal logics into Ω.
We first define a set-theoretic translation of ALC based on Schild’s correspondence with polymodal logics. Then we propose a translation of the fragment LCΩ of ALCΩ without roles and individual names. In this—simple—case the power-set concept is mapped, as expected, to the set-theoretic power-set, making clearer the real nature of the power-set concept in ALCΩ. Finally, we encode the whole language of ALCΩ into its fragment without roles, showing that such a fragment is as expres- sive as ALCΩ. The encoding provides, as a by-product, a set-theoretic translation of ALCΩ into the theory Ω, which can be used as basis for extending other, more expressive, DLs with the power-set construct
Tales of Spatiality in stochastic Concurrent Constraint Programming
No full textStochastic Concurrent Constraint Programming (sCCP) extends CCP with a stochastic semantics in continuous time. As such, it can be used to model biological systems. The characterizing feature of sCCP is its exibility, given by the computational and reasoning capabilities of the constraint store. In this paper we discuss how such features can be used to model biological systems involving dierent notions of spatiality, from compartmentalization to the position of each molecule
- …
