Search

1 online ID: 766 Bibliographic Level Mode of Issuance: Monograph Includes bibliographical references and index. Also issued online. Electronic reproduction. Berlin : Springer-Verlag, 2004. Mode of access: World Wide Web. System requirements: Adobe Acrobat Reader or other PDF reader (latest version recommended) Internet Explorer or other browser (latest version recommended). Title from title screen. Mode of access: World Wide Web. English Contents: EU Funded Grid Development in Europe -- Pegasus: Mapping Scientific Workflows onto the Grid -- A Low-Cost Rescheduling Policy for Dependent Tasks on Grid Computing Systems -- An Advanced Architecture for a Commercial Grid Infrastructure -- Managing MPI Applications in Grid Environments -- Flood Forecasting in CrossGrid Project -- MPICH-G2 Implementation of an Interactive Artificial Neural Network Training -- OpenMolGRID, a GRID Based System for Solving Large-Scale Drug Design Problems -- Integration of Blood Flow Visualization on the Grid: The FlowFish/GVK Approach -- A Migration Framework for Executing Parallel Programs in the Grid -- Implementations of a Service-Oriented Architecture on Top of Jini, JXTA and OGSI -- Dependable Global Computing with JaWS++ -- Connecting Condor Pools into Computational Grids by Jini -- Overview of an Architecture Enabling Grid Based Application Service Provision -- A Grid-Enabled Adaptive Problem Solving Environment -- Workflow Support for Complex Grid Applications: Integrated and Portal Solutions -- Debugging MPI Grid Applications Using Net-dbx -- Towards an UML Based Graphical Representation of Grid Workflow Applications -- Support for User-Defined Metrics in the Online Performance Analysis Tool G-PM -- Software Engineering in the EU CrossGrid Project -- Monitoring Message-Passing Parallel Applications in the Grid with GRM and Mercury Monitor -- Lhcmaster – A System for Storage and Analysis of Data Coming from the ATLAS Simulations -- Using Global Snapshots to Access Data Streams on the Grid -- SCALEA-G: A Unified Monitoring and Performance Analysis System for the Grid -- Application Monitoring in CrossGrid and Other Grid Projects -- Grid Infrastructure Monitoring as Reliable Information Service -- Towards a Protocol for the Attachment of Semantic Descriptions to Grid Services -- Semantic Matching of Grid Resource Descriptions -- Enabling Knowledge Discovery Services on Grids -- A Grid Service Framework for Metadata Management in Self-e-Learning Networks. Summary: The 2nd European AcrossGrids Conference (AxGrids 2004) aimed to examine the state ofthe artinresearchandtechnologydevelopmentsinGridComputing, and provide a forum for the presentation and exchange of views on the latest grid-related research results and future work. The conference was organized by CrossGrid, a European Union-funded project on Grid research, GRIDSTART, the EU-sponsored initiative for consolidating technical advances in grids in - rope, and the University of Cyprus. It continued on from the successful 1st European Across Grids Conference, held in Santiago de Compostela, Spain, in February 2003. AxGrids 2004 was run in conjunction with the 2nd IST Conc- tation Meeting on Grid Research, which brought together representatives from allEU-funded projectsonGridresearchforanexchangeofexperiencesandideas regarding recent developments in European grid research. TheconferencewashostedinNicosia,thecapitalofCyprus,andattracted- thorsandattendeesfromalloverEurope,theUSA,andEastAsia. TheProgram Committee of the conference consisted of 37 people from both academia and - dustry, and there were 13 external reviewers. Overall, AxGrids 2004 attracted 57 paper submissions (42 full papers and 15 short posters). Papers underwent a thorough review by several Program Committee members and external - viewers. After the review, the Program Chair decided to accept 26 papers (out of 42) for regular presentations, 8 papers for short presentations, and 13 - pers for poster presentations. Accepted papers underwent a second review for inclusion this postproceedings volume, published as part of Springer’s Lecture Notes in Computer Science series.

The OpenMP specification lacks a composable shared memory concurrency mechanism: the current OpenMP concurrency mechanisms, such as OMP critical, locks, or atomics, do not support composition. In this paper, we motivate the need for transactional memory (TM) in OpenMP. The chief reason is to support composition of realistic programs, but we also consider whether TM is easier to program than locks, the use case for TM, and whether a software-only TM can outperform traditional locking through a survey of recent publications. This paper advances upon previous proposals of OpenMP TM by introducing a new construct specifically to handle irrevocable actions, which is also composable. It also proposes a pure atomic transaction construct as well as the concept of transaction safety. Further, we examine how our proposed construct integrates with current OpenMP constructs.

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-34176-2_5, Revised Selected and Invited Papers, 4th International Symposium, AGTIVE 2011, Budapest, Hungary, October 4-7, 2011, Model-Driven Engineering promotes models as the principal artefacts of the development, hence model transformation techniques – like graph transformation – become key enablers for this development paradigm. In order to increase the adoption of Model-Driven Engineering in industrial practice, techniques aimed at raising the quality and productivity in model transformation development are needed. In this paper we bring elements from generic programming into graph transformation in order to define generic graph transformations that can be reused in different contexts. In particular, we propose the definition and instantiation of graph transformation templates whose requirements from generic types are specified through so-called concepts, as well as mixin layers that extend meta-models with the extra auxiliary elements needed by templates., Work funded by the Spanish Ministry of Economy and Competitivity (project TIN2011-24139) and the Region of Madrid (project S2009/TIC-1650)

We study problems that arise in the context of covering certain geometric objects called seeds (e.g., points or disks) by a set of other geometric objects called cover (e.g., a set of disks or homothetic triangles). We insist that the interiors of the seeds and the cover elements are pairwise disjoint, respectively, but they can touch. We call the contact graph of a cover a cover contact graph (CCG). We are interested in three types of tasks, both in the general case and in the special case of seeds on a line: (a) deciding whether a given seed set has a connected CCG, (b) deciding whether a given graph has a realization as a CCG on a given seed set, and (c) bounding the sizes of certain classes of CCG's. Concerning (a) we give efficient algorithms for the case that seeds are points and show that the problem becomes hard if seeds and covers are disks. Concerning (b) we show that this problem is hard even for point seeds and disk covers (given a fixed correspondence between graph vertices and seeds). Concerning (c) we obtain upper and lower bounds on the number of CCG's for point seeds., Journal of Computational Geometry, Vol. 3 No. 1 (2012)

The final publication is available at Springer via http://dx.doi.org/10.1007/11499305_19, Proceedings of First International Work-Conference on the Interplay Between Natural and Artificial Computation, IWINAC 2005, Las Palmas, Canary Islands, Spain, June 15-18, 2005, This paper describes Attribute Grammar Evolution (AGE), a new Automatic Evolutionary Programming algorithm that extends standard Grammar Evolution (GE) by replacing context-free grammars by attribute grammars. GE only takes into account syntactic restrictions to generate valid individuals. AGE adds semantics to ensure that both semantically and syntactically valid individuals are generated. Attribute grammars make it possible to semantically describe the solution. The paper shows empirically that AGE is as good as GE for a classical problem, and proves that including semantics in the grammar can improve GE performance. An important conclusion is that adding too much semantics can make the search difficult.

We present a new classification system based on Evolutionary Algorithm (EA), OBLIC. This tool is an OBLIque Classification system whose function is to induce a set of classification rules no hierarchical from a database or training set. The core of the algorithm is a EA with real-coded and Pittsburgh approach. Each individual is composed by a no fixed classification rules set what split in regions the search space. The fitness of each classification is obtained by means of the exploration of these regions. The result of the tool is the best classification obtained in the evolutionary process.This paper describe and analyze this new method by comparing with other classification systems on UCI Repository databases. We conclude this paper with some observations and future projects.

The increasing size of container vessels is raising the complexity of daily operations of both the carrier and the terminal. This paper focuses on stowage planning, the problem of assigning container to positions in a vessel. In particular, it studies the implementation of known planning strategies within an optimisation framework. Block stowage and crane intensity are presented and mathematically modelled on a simplified version of the problem. An experimental evaluation, on a large set of novel benchmark instances, shows that even in this simplified version the problem is not trivially solved. A matheuristic based on large neighbourhood search is presented, which is able to find a solution to all instances in short computational times.

Heterogeneous systems are an important trend in the future of supercomputers, yet they can be hard to program and developers still lack powerful tools to gain understanding about how well their accelerated codes perform and how to improve them. Having different types of hardware accelerators available, each with their own specific low-level APIs to program them, there is not yet a clear consensus on a standard way to retrieve information about the accelerator’s performance. To improve this scenario, OMPT is a novel performance monitoring interface that is being considered for integration into the OpenMP standard. OMPT allows analysis tools to monitor the execution of parallel OpenMP applications by providing detailed information about the activity of the runtime through a standard API. For accelerated devices, OMPT also facilitates the exchange of performance information between the runtime and the analysis tool. We implement part of the OMPT specification that refers to the use of accelerators both in the Nanos++ parallel runtime system and the Extrae tracing framework, obtaining detailed performance information about the execution of the tasks issued to the accelerated devices to later conduct insightful analysis. Our work extends previous efforts in the field to expose detailed information from the OpenMP and OmpSs runtimes, regarding the activity and performance of task-based parallel applications. In this paper, we focus on the evaluation of FPGA devices studying the performance of two common kernels in scientific algorithms: matrix multiplication and Cholesky decomposition. Furthermore, this development is seamlessly applicable for the analysis of GPGPU accelerators and Intel®Xeon PhiTM co-processors operating under the OmpSs programming model. This work was partially supported by the European Union H2020 program through the AXIOM project (grant ICT-01-2014 GA 645496) and the Mont-Blanc 2 project, by the Ministerio de Economía y Competitividad, under contracts Computación de Altas Prestaciones VII (TIN2015-65316-P); Departament d'Innovació, Universitats i Empresa de la Generalitat de Catalunya, under projects MPEXPAR: Models de Programació i Entorns d'Execució Paral·lels (2014-SGR-1051) and 2009-SGR-980; the BSC-CNS Severo Ochoa program (SEV-2011-00067); the Intel-BSC Exascale Laboratory project; and the OMPT Working Group.

Proceeding of: Second International Conference,Networked Systems (NETYS 2014), took place 2014. May 15-17. in Marrakech, Morocco. Resource allocation is one of the most relevant problems in the area of Mechanism Design for computing systems. Devising algorithms capable of providing efficient and fair allocation is the objective of many previous research efforts. Usually, the mechanisms they propose use payments in order to deal with selfishness. Since using payments is undesirable in some contexts, a family of mechanisms without payments is proposed in this paper. These mechanisms extend the Linking Mechanism of Jackson and Sonnenschein introducing a generic concept of fairness with correlated preferences. We prove that these mechanisms have good incentive, fairness, and efficiency properties. To conclude, we provide an algorithm, based on the mechanisms, that could be used in practical computing environments. Publicado

Further results of research into graph grammar-based parsing for syntactic pattern recognition (Pattern Recognition: 21, 623-629 (1988); 23, 765-774 (1990); 26, 1-16 (1993); 43, 2249-2264 (2010), Comput. Vision Graph. Image Process. 47, 1-21 (1989), Theoret. Comp. Sci. 201, 189-231 (1998)) are presented in the paper. The bottom-up parsable ETPR(k) subclass of well-known edNLC graph grammars is defined.

© 2014 Springer International Publishing Switzerland. OmpSs is a task-based programming model that aims to provide portability and flexibility for sequential codes while the performance is achieved by the dynamic exploitation of the parallelism at task level. OmpSs targets the programming of heterogeneous and multi-core architectures and offers asynchronous parallelism in the execution of the tasks. The main extension of OmpSs, now incorporated in the recent OpenMP 4.0 standard, is the concept of data dependences between tasks. Tasks in OmpSs are annotated with data directionality clauses that specify the data used by it, and how it will be used (read, write or read&write). This information is used during the execution by the underlying OmpSs runtime to control the synchronization of the different instances of tasks by creating a dependence graph that guarantees the proper order of execution. This mechanism provides a simple way to express the order in which tasks must be executed, without the need of adding explicit synchronization. Additionally, OmpSs syntax offers the flexibility to express that given tasks can be executed on heterogeneous target architectures (i.e., regular processors, GPUs, or FPGAs). The runtime is able to schedule and run these tasks, taking care of the required data transfers and synchronizations. OmpSs is a promising programming model for future exascale systems, with the potential to exploit unprecedented amounts of parallelism while coping with memory latency, network latency and load imbalance. The paper covers the basics of OmpSs and some recent new developments to support a family of embedded DSLs (eDSLs) on top of the compiler and runtime, including an prototype implementation of a Partial Differential Equations DSL.

Non-malleable codes, defined by Dziembowski, Pietrzak, and Wichs (ICS ’10), provide roughly the following guarantee: if a codeword $c$ encoding some message $x$ is tampered to $c' = f(c)$ such that $c' \neq c$ , then the tampered message $x'$ contained in $c'$ reveals no information about $x$ . The non-malleable codes have applications to immunizing cryptosystems against tampering attacks and related-key attacks. One cannot have an efficient non-malleable code that protects against all efficient tampering functions $f$ . However, in this paper we show “the next best thing”: for any polynomial bound $s$ given a-priori, there is an efficient non-malleable code that protects against all tampering functions $f$ computable by a circuit of size $s$ . More generally, for any family of tampering functions $ \mathcal {F}$ of size $| \mathcal {F}| \leq 2^{s}$ , there is an efficient non-malleable code that protects against all $f \in \mathcal {F} $ . The rate of our codes, defined as the ratio of message to codeword size, approaches 1. Our results are information-theoretic and our main proof technique relies on a careful probabilistic method argument using limited independence. As a result, we get an efficiently samplable family of efficient codes, such that a random member of the family is non-malleable with overwhelming probability. Alternatively, we can view the result as providing an efficient non-malleable code in the “common reference string” model. We also introduce a new notion of non-malleable key derivation, which uses randomness $x$ to derive a secret key $y = h(x)$ in such a way that, even if $x$ is tampered to a different value $x' = f(x)$ , the derived key $y' = h(x')$ does not reveal any information about $y$ . Our results for non-malleable key derivation are analogous to those for non-malleable codes. As a useful tool in our analysis, we rely on the notion of “leakage-resilient storage” of Davi, Dziembowski, and Venturi (SCN ’10), and, as a result of independent interest, we also significantly improve on the parameters of such schemes.

In an era of overwhelming choices, recommender systems aim at recommending the most suitable items to the user. Preference handling is one of the core issues in the design of recommender systems and so it is important for them to catch and model the user's preferences as accurately as possible. In previous work, comparative preferences-based patterns were developed to handle preferences deduced by the system. These patterns assume there are only two values for each feature. However, real-world features can be multi-valued. In this paper, we develop preference induction methods which aim at capturing several preference nuances from the user feedback when features have more than two values. We prove the efficiency of the proposed methods through an experimental study.

In this paper, we consider the extension of multi-objective constraint optimization algorithms to the case where there are additional tradeoffs, reducing the number of optimal solutions. We focus especially on branch-and-bound algorithms which use a mini-buckets algorithm for generating the upper bound at each node (in the context of maximizing values of objectives). Since the main bottleneck of these algorithms is the very large size of the guiding upper bound sets we introduce efficient methods for reducing these sets, yet still maintaining the upper bound property. We also propose much faster dominance checks with respect to the preference relation induced by the tradeoffs. Furthermore, we show that our tradeoffs approach which is based on a preference inference technique can also be given an alternative semantics based on the well known Multi-Attribute Utility Theory. Our comprehensive experimental results on common multi-objective constraint optimization benchmarks demonstrate that the proposed enhancements allow the algorithms to scale up to much larger problems than before.

International audience; The design and analysis of lightweight block ciphers has been a very active research area over the last couple of years, with many innovative proposals trying to optimize di erent performance gures. However, since these block ciphers are dedicated to low-cost embedded devices, their implementation is also a typical target for side-channel adversaries. As preventing such attacks with countermeasures usually implies signi cant performance overheads, a natural open problem is to propose new algorithms for which physical security is considered as an optimization criteria, hence allowing better performances again. We tackle this problem by studying how much we can tweak standard block ciphers such as the AES Rijndael in order to allow e cient masking (that is one of the most frequently considered solutions to improve security against side-channel attacks). For this purpose, we rst investigate alternative S- boxes and round structures. We show that both approaches can be used separately in order to limit the total number of non-linear operations in the block cipher, hence allowing more e cient masking. We then combine these ideas into a concrete instance of block cipher called Zorro. We further provide a detailed security analysis of this new cipher taking its design speci cities into account, leading us to exploit innovative techniques borrowed from hash function cryptanalysis (that are sometimes of independent interest). Eventually, we conclude the paper by evaluating the e ciency of masked Zorro implementations in an 8-bit microcontroller, and exhibit their interesting performance gures.

Current key sizes for symmetric cryptography are usually required to be at least 80-bit long for short-term protection, and 128-bit long for long-term protection. However, current tools for security evaluations against side-channel attacks do not provide a precise estimation of the remaining key strength after some leakage has been observed, e.g. in terms of number of candidates to test. This leads to an uncomfortable situation, where the security of an implementation can be anywhere between enumerable values (i.e. 210 − 250 key candidates to test) and the full key size (i.e. 260 − 2128 key candidates to test). In this paper, we propose a solution to this issue, and describe a key rank estimation algorithm that provides tight bounds for the security level of leaking cryptographic devices. As a result and for the first time, we are able to analyze the full complexity of “standard” (i.e. divide-and-conquer) side-channel attacks, in terms of their tradeoff between time, data and memory complexity.

Date du colloque: 06/2012; International audience; The unconstrained binary quadratic programming (UBQP) problem is a general NP-hard problem with various applications. In this paper, we present a multilevel algorithm designed to approximate large UBQP instances. The proposed multilevel algorithm is composed of a backbone-based coarsening phase, an asymmetric uncoarsening phase and a memetic refinement phase, where the backbone-based procedure and the memetic refinement procedure make use of tabu search to obtain improved solutions. Evaluated on a set of 11 largest instances from the literature (with 5000 to 7000 variables), the proposed algorithm proves to be able to attain all the best known values with a computing effort less than any existing approach.

Emerging MPI libraries, such as VolpexMPI and P2P MPI, allow message passing parallel programs to execute effectively in heterogeneous volunteer environments despite frequent failures. However, the performance of message passing codes varies widely in a volunteer environment, depending on the application characteristics and the computation and communication characteristics of the nodes and the interconnection network. This paper has the dual goal of developing and validating a tool chain to estimate performance of MPI codes in a volunteer environment and analyzing the suitability of the class of computations represented by NAS benchmarks for volunteer computing. The framework is deployed to estimate performance in a variety of possible volunteer configurations, including some based on the measured parameters of a campus volunteer pool. The results show slowdowns by factors between 2 and 10 for different NAS benchmark codes for execution on a realistic volunteer campus pool as compared to dedicated clusters.

Date du colloque: 09/2012; International audience; The max-cut problem is to partition the vertices of a weighted graph G = (V,E) into two subsets such that the weight sum of the edges crossing the two subsets is maximized. This paper presents a memetic max-cut algorithm (MACUT) that relies on a dedicated multi-parent crossover operator and a perturbation-based tabu search procedure. Experiments on 30 G-set benchmark instances show that MACUT competes favorably with 6 state-of-the-art max-cut algorithms, and for 10 instances improves on the best known results ever reported in the literature.

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-15928-2_18, Proceedings of 5th International Conference, ICGT 2010, Enschede, The Netherlands, September 27–October 2, 2010, Graph transformation is being increasingly used to express the semantics of domain specific visual languages since its graphical nature makes rules intuitive. However, many application domains require an explicit handling of time in order to represent accurately the behaviour of the real system and to obtain useful simulation metrics. Inspired by the vast knowledge and experience accumulated by the discrete event simulation community, we propose a novel way of adding explicit time to graph transformation rules. In particular, we take the event scheduling discrete simulation world view and incorporate to the rules the ability of scheduling the occurrence of other rules in the future. Hence, our work combines standard, efficient techniques for discrete event simulation (based on the handling of a future event set) and the intuitive, visual nature of graph transformation. Moreover, we show how our formalism can be used to give semantics to other timed approaches., Work partially sponsored by the Spanish Ministry of Science and Innovation, under project “METEORIC” (TIN2008-02081) and mobility grants JC2009-00015 and PR2009-0019, as well as by the R&D programme of the Community of Madrid, project “e-Madrid” (S2009/TIC-1650). We are grateful to the anonymous reviewers, which helped in improving the paper

Comunicació presentada a: PKC 2010. 13th International Conference on Practice and Theory in Public Key Cryptography, celebrada del 26 al 28 de maig de 2010 a París, França. Attribute-based cryptography has emerged in the last years as a promising primitive for digital security. For instance, it provides good solutions to the problem of anonymous access control. In a ciphertext- policy attribute-based encryption scheme, the secret keys of the users de- pend on their attributes. When encrypting a message, the sender chooses which subset of attributes must be held by a receiver in order to be able to decrypt. All current attribute-based encryption schemes that admit reasonably expressive decryption policies produce ciphertexts whose size depends at least linearly on the number of attributes involved in the policy. In this paper we propose the first scheme whose ciphertexts have constant size. Our scheme works for the threshold case: users authorized to decrypt are those who hold at least t attributes among a certain universe of attributes, for some threshold t chosen by the sender. An extension to the case of weighted threshold decryption policies is possible. The security of the scheme against selective chosen plaintext attacks can be proven in the standard model by reduction to the augmented multi-sequence of exponents decisional Di e-Hellman (aMSE-DDH) problem. The work of Javier Herranz is supported by a Ramón y Cajal grant, partially funded by the European Social Fund (ESF) of the Spanish MICINN Ministry. Carla Ràfols holds an FPI grant of the Spanish MICINN Ministry. The work of both these authors is partially supported by the Spanish MICINN Ministry under project MTM2009-07694. The work of Fabien Laguillaumie is supported by the French ANR-07-TCOM-013-04 PACE Project.

Date du colloque: 04/2009; International audience; The Maximum Parsimony problem aims at reconstructing a phylogenetic tree from DNA, RNA or protein sequences while minimizing the number of evolutionary changes. Much work has been devoted by the research community to solve this NP-complete problem and many algorithms and techniques have been devised in order to find high quality solutions with reasonable computational resources. In this paper we present a memetic algorithm (implemented in the software Hydra) which is based on an integration of an effective local search operator with a specific topological tree crossover operator. We report computational results of Hydra on a set of 12 benchmark instances from the literature and demonstrate its effectiveness with respect to one of the most powerful software (TNT). We also study the behavior of the algorithm with respect to some fundamental ingredients.

Membrane Computing is a new paradigm inspired from cellular communication. Until now, P systems have been used in research areas like modeling chemical process, several ecosystems, etc. In this paper, we apply P systems to Computational Topology within the context of the Digital Image. We work with a variant of P systems called tissue-like P systems to calculate in a general maximally parallel manner the homology groups of 2D images. In fact, homology computation for binary pixel-based 2D digital images can be reduced to connected component labeling of white and black regions. Finally, we use a software called Tissue Simulator to show with some examples how these systems work.

Date du colloque: 04/2009; International audience; In this paper, we study the perturbation operator of Iterated Local Search. To guide more efficiently the search to move towards new promising regions of the search space, we introduce a Critical Element-Guided Perturbation strategy (CEGP). This perturbation approach consists of the identification of critical elements and then focusing on these critical elements within the perturbation operator. Computational experiments on two case studies—graph coloring and course timetabling—give evidence that this critical element-guided perturbation strategy helps reinforce the performance of Iterated Local Search.

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-540-87405-8_29, Proceedings of 4th International Conference, ICGT 2008, Leicester, United Kingdom, September 7-13, 2008, We present a new, high-level approach for the specification of model-to-model transformations based on declarative patterns. These are (atomic or composite) constraints on triple graphs declaring the allowed or forbidden relationships between source and target models. In this way, a transformation is defined by specifying a set of triple graph constraints that should be satisfied by the result of the transformation. The description of the transformation is then compiled into lower-level operational mechanisms to perform forward or backward transformations, as well as to establish mappings between two existent models. In this paper we study one of such mechanisms based on the generation of operational triple graph grammar rules. Moreover, we exploit deduction techniques at the specification level in order to generate more specialized constraints (preserving the specification semantics) reflecting pattern dependencies, from which additional rules can be derived., Work supported by the Spanish Ministry of Education and Science, projects TSI2005-08225-C07-06 and TIN2006-09678.

The final publication is available at Springer via http://dx.doi.org/10.1007/11841883_25, Proceedings of Third International Conference, ICGT 2006 Natal, Rio Grande do Norte, Brazil, September 17-23, 2006, In this paper, we present our approach for model view management in the context of Multi-View Visual Languages (MVVLs). These are made of a number of diagram types (or viewpoints) that can be used for the specification of the different aspects of a system. Therefore, the user can build different system views conform to the viewpoints, which are merged in a repository in order to perform consistency checking. In addition, the user can define derived views by means of graph query patterns in order to extract information from a base model (a system view or the repository). We have provided automatic mechanisms to keep synchronized the base model and the derived view when the former changes. Predefined queries by the MVVL designer result in so-called audience-oriented views. Finally, semantic views are used for analysing the system by its translation into a semantic domain. Our approach is based on meta-modelling to describe the syntax of the MVVL and each viewpoint, and on triple graph transformation systems to synchronize and maintain correspondences between the system views and the repository, as well as between the derived, audience-oriented and semantic views and the base models. We illustrate these concepts by means of an example in the domain of security for web systems., This work has been sponsored by the Spanish Ministry of Science and Education, projects TSI2005-08225-C07-06 and TSI2004-03394.

Let Λ be a commutative ring, A an augmented differential graded algebra over Λ (briefly, DGA-algebra) and X be a relatively free resolution of Λ over A. The standard bar resolution of Λ over A, denoted by B(A), provides an example of a resolution of this kind. The comparison theorem gives inductive formulae f : B(A)→X and g : X→B(A) termed comparison maps. In case that fg=1 X and A is connected, we show that X is endowed a A ∞ -tensor product structure. In case that A is in addition commutative then (X,μ X ) is shown to be a commutative DGA-algebra with the product μ X =f*(g⊗g) (* is the shuffle product in B(A)). Furthermore, f and g are algebra maps. We give an example in order to illustrate the main results of this paper.

In this paper, algorithms for computing integer (co)homology of a simplicial complex of any dimension are designed, extending the work done in [1,2,3]. For doing this, the homology of the object is encoded in an algebraic-topological format (that we call AM-model). Moreover, in the case of 3D binary digital images, having as input AM-models for the images I and J, we design fast algorithms for computing the integer homology of I ∪J, I ∩J and I ∖J.

In this paper, we deal with the problem of the computation of the homology of a finite simplicial complex after an “elementary simplicial perturbation” process such as the inclusion or elimination of a maximal simplex or an edge contraction. To this aim we compute an algebraic topological model that is a special chain homotopy equivalence connecting the simplicial complex with its homology (working with a field as the ground ring).

This paper introduces an algebraic framework for a topological analysis of time-varying 2D digital binary–valued images, each of them defined as 2D arrays of pixels. Our answer is based on an algebraic-topological coding, called AT–model, for a nD (n=2,3) digital binary-valued image I consisting simply in taking I together with an algebraic object depending on it. Considering AT–models for all the 2D digital images in a time sequence, it is possible to get an AT–model for the 3D digital image consisting in concatenating the successive 2D digital images in the sequence. If the frames are represented in a quadtree format, a similar positive result can be derived.

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-540-30212-4_15, Revised and Selected Papers of ECCV 2004 Workshop SMVP 2004, Prague, Czech Republic, May 16, 2004, The lack of sufficient machine readable images makes impossible the direct computation of natural image 4 × 4 block statistics and one has to resort to indirect approximated methods to reduce their domain space. A natural approach to this is to collect statistics over compressed images; if the reconstruction quality is good enough, these statistics will be sufficiently representative. However, a requirement for easier statistics collection is that the method used provides a uniform representation of the compression information across all patches, something for which codebook techniques are well suited. We shall follow this approach here, using a fractal compression–inspired quantization scheme to approximate a given patch B by a triplet (D B , μ B , σ B ) with σ B the patch’s contrast, μ B its brightness and D B a codebook approximation to the mean–variance normalization (B – μ B )/σ B of B. The resulting reduction of the domain space makes feasible the computation of entropy and mutual information estimates that, in turn, suggest a factorization of the approximation of p(B) ≃ p(D B , μ B , σ B ) as p(D B , μ B , σ B ) ≃ p(D B )p(μ)p(σ)Φ(|| ∇ ||), with Φ being a high contrast correction., With partial support of Spain’s CICyT, TIC 01–572

Graphical features on map, charts, diagrams and graph drawings usually must be annotated with text labels in order to convey their meaning. In this paper we focus on a problem that arises when labeling schematized maps, e.g. for subway networks. We present algorithms for labeling points on a line with axis-parallel rectangular labels of equal height. Our aim is to maximize label size under the constraint that all points must be labeled. Even a seemingly strong simplification of the general point-labeling problem, namely to decide whether a set of points on a horizontal line can be labeled with sliding rectangular labels, turns out to be weakly NPcomplete. This is the first labeling problem that is known to belong to this class. We give a pseudo-polynomial time algorithm for it. In case of a sloping line points can be labeled with maximum-size square labels in O(n log n) time if four label positions per point are allowed and in O(n 3 log n) time if labels can slide. We also investigate rectangular labels.

This paper is devoted to the study of graph embeddings in the grid of non-planar surfaces. We provide an adequate model for those embeddings and we study the complexity of minimizing the number of bends. In particular, we prove that testing whether a graph admits a rectilinear (without bends) embedding essentially equivalent to a given embedding, and that given a graph, testing if there exists a surface such that the graph admits a rectilinear embedding in that surface are NP-complete problems and hence the corresponding optimization problems are NP-hard.

Performance analysis is very important to understand the applications’ behavior and to identify bottlenecks. Performance analysis tools should facilitate the exploration of the data collected and help to identify where the analyst has to look. While this functionality can promote the tools usage on small and medium size environments, it becomes mandatory for large-scale and many-core systems where the amount of data is dramatically increased. This paper proposes a new methodology based on the integration of profilers and timeline tools to improve and facilitate the performance analysis process.