Pasar al contenido principal

MODELOS Y METODOS BASADOS EN GRAFOS PARA LA COMPUTACION EN GRAN ESCALA

TIN2017-86727-C2-1-R

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos I+D+i Retos de Investigación
Año convocatoria 2017
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 125
Encontrada(s) 2 página(s)

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publicación Contribución de congreso (ConferenceOutput)

On the Value of Pedagogical Assets

  • Gabarro, Joaquim
  • Serna, Maria
[EN] University education is facing new strategical changes that will lead to deep structural changes. Course organization is evolving and the organizational decisions have an economical impact. We propose a method to measure the present value of a pedagogical asset under a return rate. We apply the method to three courses in the Computer Science curricula taught at the Facultat d’Informatica de Barcelona of the Universitat Politècnica de Catalunya, Barcelona Tech.  A large, compulsory, first year course (PRO1), a medium size undergraduate course (ALG) and a small specialized master course (AGT). Our results highlight that the present value gets higher values as a function of the size of the course and it goes in a negative relationship with respect  to the level of computer support involved in their teaching., This worok was partially supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R (GRAMM) and AGAUR under grant 2017SGR-786. M. Serna was also partially funded by MINECO under grant MDM-2014-044 (BGSMath).
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Ordocoordinación: Cómo Organizar 700 Estudiantes en un Nuevo Campus (y no Morir en el Intento)

  • Castro, Jorge
  • Farreres, Xavier
  • Gabarro, Joaquim
  • Nivela, Pilar
  • Perez-Poch, Antoni
  • Pino, Elvira
  • Rivero, Jose Miguel
A partir del Q1 de 2017 el Departamento de CS de la UPC se ocupa de la docencia de Informática I en el nuevo campus de la EEBE. Dicha docencia ha sido singular en dos aspectos. Primero, hubo que organizarla al mismo tiempo que se impartía. Segundo, todos los números son grandes. En el Q1 de 2017, hubo 686 estudiantes matriculados, 18 docentes y se prepararon 108 exámenes de laboratorio. Para tratar con estas singularidades hemos adoptado una forma de coordinación a la que hemos llamado ordocoordinación. Es una coordinación flexible y rápida en la que los docentes generan y consensúan un conjunto mínimo de reglas. Es de abajo a arriba y requiere una toma de decisiones ágil, por lo que el número de emails ha sido importante. En Q1 de 2017: 350 x 18 = 6300 emails. Creemos que esta aproximación merece ser explicada y que puede ser aplicada a otras asignaturas.
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Web apps and imprecise probabilities

  • Castro Rabal, Jorge|||0000-0002-1390-1313
  • Gabarró Vallès, Joaquim|||0000-0003-3771-2813
  • Serna Iglesias, María José|||0000-0001-9729-8648
We propose a model for the behaviour of Web apps in the unreliable WWW. Web apps are described by orchestrations. An orchestration mimics the personal use of the Web by defining the way in which Web services are invoked. The WWW is unreliable as poorly maintained Web sites are prone to fail. We model this source of unreliability trough a probabilistic approach. We assume that each site has a probability to fail. Another source of uncertainty is the traffic congestion. This can be observed as a non-deterministic behaviour induced by the variability in the response times. We model non-determinism by imprecise probabilities. We develop here an ex-ante normal to characterize the behaviour of finite orchestrations in the unreliable Web. We show the existence of a normal form under such semantics for orchestrations using asymmetric parallelism., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Approximate computation of alignments of business processes through relaxation labelling

  • Padró, Lluís|||0000-0003-4738-5019
  • Carmona Vargas, Josep|||0000-0001-9656-254X
A fundamental problem in conformance checking is aligning event data with process models. Unfortunately, existing techniques for this task are either complex, or can only be applicable to restricted classes of models. This in practice means that for large inputs, current techniques often fail to produce a result. In this paper we propose a method to approximate alignments for unconstrained process models, which relies on the use of relaxation labelling techniques on top of a partial order representation of the process model. The implementation on the proposed technique achieves a speed-up of several orders of magnitude with respect to the approaches in the literature (either optimal or approximate), often with a reasonable trade-off on the cost of the obtained alignment., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Explainable predictive process monitoring

  • Galanti, Riccardo
  • Coma Puig, Bernat|||0000-0003-3944-797X
  • de Leoni, Massimiliano
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Navarin, Nicolò
Predictive Business Process Monitoring is becoming an essential aid for organizations, providing online operational support of their processes. This paper tackles the fundamental problem of equipping predictive business process monitoring with explanation capabilities, so that not only the what but also the why is reported when predicting generic KPIs like remaining time, or activity execution. We use the game theory of Shapley Values to obtain robust explanations of the predictions. The approach has been implemented and tested on real-life benchmarks, showing for the first time how explanations can be given in the field of predictive business process monitoring., This work is supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R and by the Department of Mathematics, University of Padua, with HPC resources., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Refining the imprecise meaning of non-determinism in the Web by strategic games

  • Castro Rabal, Jorge|||0000-0002-1390-1313
  • Gabarró Vallès, Joaquim|||0000-0003-3771-2813
  • Serna Iglesias, María José|||0000-0001-9729-8648
Nowadays interactions with the World Wide Web are ubiquitous. Users interact through a number of steps consisting of site calls and handling results that can be automatized as orchestrations. Orchestration results have an inherent degree of uncertainty due to incomplete Web knowledge and orchestration semantics are characterized in terms of imprecise probabilistic choices. We consider two aspects in this imprecise semantic characterization. First, when local knowledge (even imprecise) of some part of the Web increases, this knowledge goes smoothly through the whole orchestration. We deal formally with this aspect introducing orchestration refinements. Second, we analyze refinement under uncertainty in the case of parallel composition. Uncertain knowledge is modeled by an uncertainty profile. Such profiles allow us to look at the uncertainty through a zero-sum game, called angel/daemon-game. We propose to use the structure of the Nash equilibria to refine uncertainty. In this case the information improves not through cooperation but through the angel and daemon competition., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Business process variant analysis based on mutual fingerprints of event logs

  • Taymouri, Farbod
  • La Rosa, Marcello
  • Carmona Vargas, Josep|||0000-0001-9656-254X
Comparing business process variants using event logs is a common use case in process mining. Existing techniques for process variant analysis detect statistically-significant differences between variants at the level of individual entities (such as process activities) and their relationships (e.g. directly-follows relations between activities). This may lead to a proliferation of differences due to the low level of granularity in which such differences are captured. This paper presents a novel approach to detect statistically-significant differences between variants at the level of entire process traces (i.e. sequences of directly-follows relations). The cornerstone of this approach is a technique to learn a directly-follows graph called mutual fingerprint from the event logs of the two variants. A mutual fingerprint is a lossless encoding of a set of traces and their duration using discrete wavelet transformation. This structure facilitates the understanding of statistical differences along the control-flow and performance dimensions. The approach has been evaluated using real-life event logs against two baselines. The results show that at a trace level, the baselines cannot always reveal the differences discovered by our approach, or can detect spurious differences., This research is partly funded by the Australian Research Council (DP180102839) and Spanish funds MINECO and FEDER (TIN2017-86727-C2-1-R)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

State-based encoding of large asynchronous controllers

  • Moreno, Albert
  • Cortadella, Jordi|||0000-0001-8114-250X
State encoding is one of the fundamental problems in the synthesis of asynchronous controllers. The requirement for a correct hazard-free implementation imposes severe constraints on the way encoding signals can be inserted in the specification of a controller. Even though some specification formalisms, such as Burst-mode machines or Signal Transition Graphs, enable to specify behaviors at the event level, the state encoding methods that provide the best good-quality solutions work at the state level. This imposes a severe limitation on the size of the controllers that can be handled by these methods. This paper proposes a method to solve the encoding problem for large asynchronous controllers using statebased methods. It is based on an iterative process of projection and re-composition that reduces the size specification by hiding signals, partially solves the encoding problem at the state level and re-composes the original specification using a synchronous product. The process iterates until all encoding conflicts have been solved. The method is proved to preserve the behavior of the specification (branching bisimilarity) and shown to be capable of providing good-quality solutions for controllers of more than 100 signals and 106 states., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Algorithmically efficient syntactic characterization of possibility domains

  • Díaz Cort, Josep|||0000-0003-4422-0067
  • Kirousis, Lefteris
  • Kokonezi, Sofia
  • Livieratos, John
In the field of Judgment Aggregation, a domain, that is a subset of a Cartesian power of {0, 1}, is considered to reflect abstract rationality restrictions on vectors of two-valued judgments on a number of issues. We are interested in the ways we can aggregate the positions of a set of individuals, whose positions over each issue form vectors of the domain, by means of unanimous (idempotent) functions, whose output is again an element of the domain. Such functions are called non-dictatorial, when their output is not simply the positions of a single individual. Here, we consider domains admitting various kinds of non-dictatorial aggregators, which reflect various properties of majority aggregation: (locally) non-dictatorial, generalized dictatorships, anonymous, monotone, StrongDem and systematic. We show that interesting and, in some sense, democratic voting schemes are always provided by domains that can be described by propositional formulas of specific syntactic types we define. Furthermore, we show that we can efficiently recognize such formulas and that, given a domain, we can both efficiently check if it is described by such a formula and, in case it is, construct it. Our results fall in the realm of classical results concerning the syntactic characterization of domains with specific closure properties, like domains closed under logical AND which are the models of Horn formulas. The techniques we use to obtain our results draw from judgment aggregation as well as propositional logic and universal algebra., The first two authors’ research was partially supported by TIN2017-86727-C2-1-R, GRAMM. The research of the second author was carried out while visiting the Computer Science Department of the Universitat Politècnica de Catalunya., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Buffer placement and sizing for high-performance dataflow circuits

  • Josipovic, Lana
  • Sheikhha, Shabnam
  • Guerrieri, Andrea
  • Ienne, Paolo
  • Cortadella, Jordi|||0000-0001-8114-250X
Commercial high-level synthesis tools typically produce statically scheduled circuits. Yet, effective C-to-circuit conversion of arbitrary software applications calls for dataflow circuits, as they can handle efficiently variable latencies (e.g., caches), unpredictable memory dependencies, and irregular control flow. Dataflow circuits exhibit an unconventional property: registers (usually referred to as “buffers”) can be placed anywhere in the circuit without changing its semantics, in strong contrast to what happens in traditional datapaths. Yet, although functionally irrelevant, this placement has a significant impact on the circuit’s timing and throughput. In this work, we show how to strategically place buffers into a dataflow circuit to optimize its performance. Our approach extracts a set of choice-free critical loops from arbitrary dataflow circuits and relies on the theory of marked graphs to optimize the buffer placement and sizing. Our performance optimization model supports important high-level synthesis features such as pipelined computational units, units with variable latency and throughput, and if-conversion. We demonstrate the performance benefits of our approach on a set of dataflow circuits obtained from imperative code., L. Josipović was supported by a Google Ph.D. Fellowship in Systems and Networking. J. Cortadella was supported by grants MINECO TIN2017-86727-C2-1-R and GENCAT 2017-SGR-786, Peer Reviewed, Award-winning
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Computing alignments of well-formed process models using local search

  • Taymouri, Farbod
  • Carmona Vargas, Josep|||0000-0001-9656-254X
The alignment of observed and modeled behavior is an essential element for organizations, since it opens the door for conformance checking and enhancement of processes. The state-of-the-art technique for computing alignments has exponential time and space complexity, hindering its applicability for medium and large instances. In this article, a novel approach is presented to tackle the challenge of computing an alignment for large-problem instances that correspond to well-formed process models. Given an observed trace, first it uses a novel replay technique to find an initial candidate trace in the model. Then a local search framework is applied to try to improve the alignment until no further improvement is possible. The implementation of the presented technique reveals a magnificent reduction both in computation time and in memory usage. Moreover, although the proposed technique does not guarantee the derivation of an alignment with minimal cost, the experiments show that in practice the quality of the obtained solutions is close to optimal., This work has been supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Some results of Maria Serna on strategic games: Complexity of equilibria and models

  • Álvarez Faura, M. del Carme|||0000-0003-2352-0546
  • Duch Brown, Amalia|||0000-0003-4371-1286
We survey some recent work of Maria Serna concerning strategic games. We first examine some results related to the formal representation of strategic games and the complexity of problems related to both the existence of equilibria and the equivalence of games. These results provided a better understanding of how the succinctness of the game representation affects the complexity of such problems. We then describe some work dealing with the definition of new strategic games. The study of a Network Formation Game with asymmetric players, and the introduction of Celebrity Games as well as of Strategic Search Games intend to explain the natural behaviour of agents acting in some particular environments like communication networks, social networks, or even networks that contain valuable items hidden in different nodes., This work was partially supported by funds from the AGAUR, Spain of the Government of Catalonia under project ref. 2017 SGR 786 (ALBCOM), by the Spanish Ministry for Economy and Competitiveness (MINECO), Spain and by the European Union (FEDER funds), under grants ref. TIN2017-86727-C2-1-R., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Conformance checking in UML artifact-centric business process models

  • Estañol Lamarca, Montserrat|||0000-0001-7204-932X
  • Muñoz Gama, Jorge|||0000-0002-6908-3911
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Teniente López, Ernest|||0000-0001-8890-9638
Business artifacts have appeared as a new paradigm to capture the information required for the complete execution and reasoning of a business process. Likewise, conformance checking is gaining popularity as a crucial technique that enables evaluating whether recorded executions of a process match its corresponding model. In this paper, conformance checking techniques are incorporated into a general framework to specify business artifacts. By relying on the expressive power of an artifact-centric specification, BAUML, which combines UML state and activity diagrams (among others), the problem of conformance checking can be mapped into the Petri net formalism and its results be explained in terms of the original artifact-centric specification. In contrast to most existing approaches, ours incorporates data constraints into the Petri nets, thus achieving conformance results which are more precise. We have also implemented a plug-in, within the ProM framework, which is able to translate a BAUML into a Petri net to perform conformance checking. This shows the feasibility of our approach., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Fixed partial match queries in quadtrees

  • Duch Brown, Amalia|||0000-0003-4371-1286
  • Lau Laynes-Lozada, Gustavo Salvador
  • Martínez Parra, Conrado|||0000-0003-1302-9067
Several recent papers in the literature have addressed the analysis of the cost P_{n,q} of partial match search for a given fixed query q - that has s out of K specified coordinates - in different multidimensional data structures. Indeed, detailed asymptotic estimates for the main term in the expected cost P_{n,q} = E {P_{n,q}} in standard and relaxed K-d trees are known (for any dimension K and any number s of specified coordinates), as well as stronger distributional results on P_{n,q} for standard 2-d trees and 2-dimensional quadtrees. In this work we derive a precise asymptotic estimate for the main order term of P_{n,q} in quadtrees, for any values of K and s, 0 < s < K, under the assumption that the limit of P_{n,q}/n^alpha when n -> infty exists, where alpha is the exponent of n in the expected cost of a random partial match query with s specified coordinates in a random K-dimensional quadtree., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Satisfaction and power in unanimous majority influence decision models

  • Molinero Albareda, Xavier|||0000-0002-5203-4347
  • Riquelme Csori, Fabian Rolando|||0000-0003-4491-0148
  • Serna Iglesias, María José|||0000-0001-9729-8648
We consider decision models associated with cooperative influence games, the oblivious and the non-oblivious influence models. In those models the satisfaction and the power measures were introduced and studied. We analyze the computational complexity of those measures when the in uence level is set to unanimity and the rule of decision is simple majority. We show that computing the satisfaction and the power measure in those systems are #P-hard., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Robustness to voltage noise with ring oscillator clocks

  • Machado, Lucas
  • Roca Pérez, Antoni|||0000-0002-1083-4565
  • Cortadella, Jordi|||0000-0001-8114-250X
© 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes,creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works., Voltage noise is the main source of dynamic variability in integrated circuits and a major concern for the design of power delivery networks (PDNs). Lower supply voltages were made possible with technology scaling, but power density was also increased. Consequently, power integrity became a key factor in the design of reliable high performance circuits. Ring oscillators clocks (ROCs) have been proposed as an alternative to mitigate the negative effects of voltage noise. However, the effectiveness highly depends on the design parameters of the PDN, power consumption patterns, and spatial locality of the ROC within the clock domain. This paper analyzes the impact of the PDN parameters and ROC location on the voltage noise and the robustness achieved by using ROCs. The capability of reacting instantaneously to large voltage droops makes ROCs an attractive solution, which also allows to relax the constraints required for the PDN design. The experiments show that up to 83% of the margins for voltage noise and up to 27% of the total leakage power can be reduced by using ROCs. In addition, PDN simplifications are possible, with fewer power interconnections or package decoupling capacitors of lower quality. Tolerance to voltage noise and related benefits can be increased with multiple ROCs., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Encoding conformance checking artefacts in SAT

  • Boltenhagen, Mathilde
  • Chatain, Thomas
  • Carmona Vargas, Josep|||0000-0001-9656-254X
Conformance checking strongly relies on the computation of artefacts, which enable reasoning on the relation between observed and modeled behavior. This paper shows how important conformance artefacts like alignments, anti-alignments or even multi-alignments, defined over the edit distance, can be computed by encoding the problem as a SAT instance. From a general perspective, the work advocates for a unified family of techniques that can compute conformance artefacts in the same way. The prototype implementation of the techniques presented in this paper show capabilities for dealing with some of the current benchmarks, and potential for the near future when optimizations similar to the ones in the literature are incorporated., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

A biased random key genetic algorithm for the weighted independent domination problem

  • Rodríguez Corominas, Guillem
  • Blum, Christian
  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
This work deals with an NP-hard problem in graphs known as the weighted independent domination problem. We propose a biased random key genetic algorithm for solving this problem. The most important part of the proposed algorithm is a decoder that translates any vector of real-values into valid solutions to the tackled problem. The experimental results, in comparison to a state-of-the-art population-based iterated greedy algorithm from the literature, show that our proposed approach has advantages over the state-of-the-art algorithm in the context of the more dense graphs in which edges have higher weights than vertices., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Generalized alignment-based trace clustering of process behavior

  • Boltenhagen, Mathilde
  • Chatain, Thomas
  • Carmona Vargas, Josep|||0000-0001-9656-254X
Process mining techniques use event logs containing real process executions in order to mine, align and extend process models. The partition of an event log into trace variants facilitates the understanding and analysis of traces, so it is a common pre-processing in process mining environments. Trace clustering automates this partition; traditionally it has been applied without taking into consideration the availability of a process model. In this paper we extend our previous work on process model based trace clustering, by allowing cluster centroids to have a complex structure, that can range from a partial order, down to a subnet of the initial process model. This way, the new clustering framework presented in this paper is able to cluster together traces that are distant only due to concurrency or loop constructs in process models. We show the complexity analysis of the different instantiations of the trace clustering framework, and have implemented it in a prototype tool that has been tested on different datasets., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Anti-alignments—Measuring the precision of process models and event logs

  • Chatain, Thomas
  • Boltenhagen, Mathilde
  • Carmona Vargas, Josep|||0000-0001-9656-254X
Processes are a crucial artifact in organizations, since they coordinate the execution of activities so that products and services are provided. The use of models to analyze the underlying processes is a well-known practice. However, due to the complexity and continuous evolution of their processes, organizations need an effective way of analyzing the relation between processes and models. Conformance checking techniques assess the suitability of a process model in representing an underlying process, observed through a collection of real executions. One important metric in conformance checking is to assess the precision of the model with respect to the observed executions, i.e., characterize the ability of the model to produce behavior unrelated to the one observed. In this paper we present the notion of anti-alignment as a concept to help unveiling runs in the model that may deviate significantly from the observed behavior. Using anti-alignments, a new metric for precision is proposed. The proposed anti-alignment based precision metric satisfies most of the required axioms highlighted in a recent publication. Moreover, a complexity analysis of the problem of computing anti-alignments is provided, which sheds light into the practicability of using anti-alignment to estimate precision. Experiments are provided that witness the validity of the concepts introduced in this paper., This work has been partially supported by funds from ENS Paris-Saclay, Spain (project ProMAut of the Farman institute), the Spanish Ministry for Economy and Competitiveness (MINECO) and the European Union (FEDER funds) under grant GRAMM (TIN2017-86727-C2-1-R)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

An agent-based model of the emergence and evolution of a language system for boolean coordination

  • Sierra Santibáñez, Josefina|||0000-0003-3529-6713
This paper presents an agent-based model for studying the emergence and evolution of a language system for Boolean coordination. The model has been implemented and tested by conducting a series of experiments that show that a language system for Boolean coordination emerges as a result of a process of self-organisation of the agents’ linguistic interactions when these agents adapt their preferences for vocabulary, syntactic categories and word order to those they observe are used more often by other agents, and that such a language system is reliably transmitted across generations., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Empowering conformance checking using Big Data through horizontal decomposition

  • Valencia Parra, Álvaro
  • Varela Vaca, Ángel Jesús
  • Gómez López, María Teresa
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Bergenthum, Robin
Conformance checking unleashes the full power of process mining: techniques from this discipline enable the analysis of the quality of a process model through the discovery of event data, the identification of potential deviations, and the projection of real traces onto process models. In this way, the insights gained from the available event data can be transferred to a richer conceptual level, amenable for human interpretation. Unfortunately, most of the aforementioned functionalities are grounded in an extremely difficult fundamental problem: given an observed trace and a process model, find the model trace that most closely resembles to the trace observed. This paper presents an architecture that supports the creation and distribution of alignment subproblems based on an innovative horizontal acyclic model decomposition, disengaged from the conformance checking algorithm applied for their solution. This is supported by a Big Data infrastructure that facilitates the customised distribution of a gross amount of data. Experiments are provided that testify to the enormous potential of the architecture proposed, thereby opening the door to further research in several directions., This work has been partially funded by the Ministry of Science and Technology of Spain ECLIPSE (RTI2018-094283-B-C33) project, the European Regional Development Fund (ERDF/FEDER), MINECO (TIN2017-86727-C2-1-R), and by the University of Seville with VI Plan Propio de Investigación y Transferencia (VI PPIT-US)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Unleashing textual descriptions of business processes

  • Sànchez-Ferreres, Josep|||0000-0002-7204-4307
  • Burattin, Andrea
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Montali, Marco
  • Padró, Lluís|||0000-0003-4738-5019
  • Quishpi Betún, Luis Hernán|||0000-0002-3539-5853
Textual descriptions of processes are ubiquitous in organizations, so that documentation of the important processes can be accessible to anyone involved. Unfortunately, the value of this rich data source is hampered by the challenge of analyzing unstructured information. In this paper we propose a framework to overcome the current limitations on dealing with textual descriptions of processes. This framework considers extraction and analysis and connects to process mining via simulation. The framework is grounded in the notion of annotated textual descriptions of processes, which represents a middle-ground between formalization and accessibility, and which accounts for different modeling styles, ranging from purely imperative to purely declarative. The contributions of this paper are implemented in several tools, and case studies are highlighted., This work has been supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Model-based trace variant analysis of event logs

  • Boltenhagen, Mathilde
  • Chatain, Thomas
  • Carmona Vargas, Josep|||0000-0001-9656-254X
The comparison of trace variants of business processes opens the door for a fine-grained analysis of the distinctive features inherent in the executions of a process in an organization. The current approaches for trace variant analysis do not consider the situation where a process model is present, and therefore, it can guide the derivation of the trace variants by considering high-level structures present in the process model. In this paper we propose a fresh alternative to trace variant analysis, which proposes a generalized notion of trace variant that incorporates concurrency and iteration. This way, the analyst may be relieved from analyzing trace variants that are essentially the same, if these aspects are disregarded. We propose a general algorithm for model based trace variant analysis which is grounded in encoding the problem into SAT, and a family of heuristic alternatives including a very light sampling technique that represents a good trade-off between quality of the trace variants identified, and the complexity of the analysis. All the techniques of the paper are implemented in two open-source tools, and experiments with publicly available benchmarks are reported., This work has been supported by Farman institute at ENS Paris-Saclay, Spain and by MINECO, Spain and FEDER, Spain funds under grant TIN2017-86727-C2-1-R., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

A quality control method for fraud detection on utility customers without an active contract

  • Coma Puig, Bernat|||0000-0003-3944-797X
  • Carmona Vargas, Josep|||0000-0001-9656-254X
Fraud detection in energy consumption has proven to be a difficult problem for current techniques. In general, the approaches used in this area are restricted to compute a fraud score for each client based on its behaviour. The problem gets much more complicated on customers with no contract, since the company does not have enough information from them to compute an accurate profile. On this paper, we introduce a semi-autonomous method that combines different machine learning algorithms and human knowledge to alleviate the lack of information to build a framework that detects fraud nimbly., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

State encoding of asynchronous controllers using pseudo-boolean optimization

  • Moreno Vega, Alberto|||0000-0001-8133-0068
  • Cortadella, Jordi|||0000-0001-8114-250X
State encoding of asynchronous controllers is a challenging problem that faces a vast space of solutions. Subtle differences in the insertion of signals may result in significant variations in the complexity of the logic. This paper proposes a novel approach that models the encoding problem as Pseudo-Boolean formula. A cost function that estimates the complexity of the logic is incorporated, where the estimator of essential literals becomes one of the most important terms of the function. The new approach has been tested in 175 benchmarks with encoding conflicts, including 127 four-phase latch controllers. The presence of logic estimators in the formula contributes to an average reduction of 43% in literals when compared to a plain SAT version of the problem, at the expense of a longer runtime. When comparing to the region-based approach in petrify, an average reduction of 14% in literals is obtained., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Sesquickselect: One and a half pivots for cache-efficient selection

  • Martínez Parra, Conrado|||0000-0003-1302-9067
  • Nebel, Markus
  • Wild, Sebastian
Because of unmatched improvements in CPU performance, memory transfers have become a bottleneck of program execution. As discovered in recent years, this also affects sorting in internal memory. Since partitioning around several pivots reduces overall memory transfers, we have seen renewed interest in multiway Quicksort. Here, we analyze in how far multiway partitioning helps in Quickselect. We compute the expected number of comparisons and scanned elements (approximating memory transfers) for a generic class of (non-adaptive) multiway Quickselect and show that three or more pivots are not helpful, but two pivots are. Moreover, we consider “adaptive” variants which choose partitioning and pivot-selection methods in each recursive step from a finite set of alternatives depending on the current (relative) sought rank. We show that “Sesquickselect”, a new Quickselect variant that uses either one or two pivots, makes better use of small samples w.r.t. memory transfers than other Quickselect variants. Copyright© (2019) by SIAM: Society for Industrial and Applied Mathematics., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Power-optimal mapping of CNN applications to cloud-based Multi-FPGA platforms

  • Shan, Junnan
  • Lazarescu, Mihai T.
  • Cortadella, Jordi|||0000-0001-8114-250X
  • Lavagno, Luciano
  • Casu, Mario R.
Multi-FPGA platforms like Amazon Web Services F1 are perfect to accelerate multi-kernel pipelined applications, like Convolutional Neural Networks (CNNs). To reduce energy consumption, we propose to upload at runtime the best power-optimized CNN implementation for a given throughput constraint. Our design method gives the best number of parallel instances of each kernel, their allocation to the FPGAs, the number of powered-on FPGAs and their clock frequency. This is obtained by solving a mixed-integer, non-linear optimization problem that models power and performance of each component, as well as the duration of the computation phases-data transfer between a host CPU and the FPGA memory (typically DDR), data transfer between DDR and FPGA, and FPGA computation. The results show that the power saved compared to simply clock gating the fastest implementation is obviously very high, but it is also much more significant than simply scaling the frequency of the fastest implementation or replicating the slowest implementation on multiple FPGAs., This work was partially supported in part by the European Commission through the ECOSCALE Project under Grant H2020-ICT671632, in part by the Spanish Ministry for Economy and Competitiveness and the European Union (FEDER Funds) under Grant TIN2017-86727-C2-1- R and Grant FPI 2015, and in part by the Generalitat de Catalunya under Grant 2017 SGR 786., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Automated repair of process models with non-local constraints using state-based region theory

  • Kalenkova, Anna
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Polyvyanyy, Artem
  • La Rosa, Marcello
State-of-the-art process discovery methods construct free-choice process models from event logs. Consequently, the constructed models do not take into account indirect dependencies between events. Whenever the input behaviour is not free-choice, these methods fail to provide a precise model. In this paper, we propose a novel approach for enhancing free-choice process models by adding non-free-choice constructs discovered a-posteriori via region-based techniques. This allows us to benefit from the performance of existing process discovery methods and the accuracy of the employed fundamental synthesis techniques. We prove that the proposed approach preserves fitness with respect to the event log while improving the precision when indirect dependencies exist. The approach has been implemented and tested on both synthetic and real-life datasets. The results show its effectiveness in repairing models discovered from event logs., This work was partly supported by the Australian Research Council Discovery Project DP180102839. This work was supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

A tour in process mining: from practice to algorithmic challenges

  • Van der Aalst, Wil M.P.
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Chatain, Thomas
  • Dongen, Boudewijn F. van
Process mining seeks the confrontation between modeled behavior and observed behavior. In recent years, process mining techniques managed to bridge the gap between traditional model-based process analysis (e.g., simulation and other business process management techniques) and data-centric analysis techniques such as machine learning and data mining. Process mining is used by many data-driven organizations as a means to improve performance or to ensure compliance. Traditionally, the focus was on the discovery of process models from event logs describing real process executions. However, process mining is not limited to process discovery and also includes conformance checking. Process models (discovered or hand-made) may deviate from reality. Therefore, we need powerful means to analyze discrepancies between models and logs. These are provided by conformance checking techniques that first align modeled and observed behavior, and then compare both. The resulting alignments are also used to enrich process models with performance related information extracted from the event log. This tutorial paper focuses on the control-flow perspective and describes a range of process discovery and conformance checking techniques. The goal of the paper is to show the algorithmic challenges in process mining. We will show that process mining provides a wealth of opportunities for people doing research on Petri nets and related models of concurrency., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

The dynamic pipeline paradigm

  • Zoltán, Cristina
  • Pasarella Sánchez, Ana Edelmira|||0000-0001-8315-4977
  • Aráoz Durand, Julián Arturo
  • Vidal, Maria-Esther
Nowadays, in the era of Big Data and Internet of Things, large volumes of data in motion are produced in heterogeneous formats, frequencies, densities, and quantities. In general, data is continuously produced by diverse devices and most of them must be processed at real-time. Indeed, this change of paradigm in the way in which data are produced, forces us to rethink the way in which they should be processed even in presence of parallel approaches. To process continuous data, data-driven frameworks are demanded; they are required to dynamically adapt execution schedulers, reconfigure computational structures, and adjust the use of resources according to the characteristics of the input data stream. In previous work, we introduced the Dynamic Pipeline as one of these computational structures, and we experimentally showed its efficiency when it is used to solve the problem of counting triangles in a graph. In this work, our aim is to define the main components of the Dynamic Pipeline which is suitable to specify solutions to problems whose incoming data is heterogeneous data in motion. To be concrete, we define the Dynamic Pipeline Paradigm and, additionally, we show the applicability of our framework to specify different well-known problems., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

CNN-on-AWS: Efficient allocation of multikernel applications on Multi-FPGA platforms

  • Shan, Junnan
  • Lazarescu, Mihai T.
  • Cortadella, Jordi|||0000-0001-8114-250X
  • Lavagno, Luciano
  • Casu, Mario R.
Multi-FPGA platforms, like Amazon AWS F1, can run in the cloud multikernel pipelined applications, like convolutional neural networks (CNNs), with excellent performance and lower energy consumption than CPUs or GPUs. We propose a method to efficiently map these applications on multi-FPGA platforms to maximize the application throughput. Our methodology finds, for the given resources, the optimal number of parallel instances of each kernel in the pipeline and their allocation to one or more among the available FPGAs. We obtain this by formulating and solving a mixed-integer, nonlinear optimization problem, in which we model the performance of each component and the duration of the phases in which the accelerated computation can be split into, namely: 1) data transfer from a host CPU to the DDR memory of each FPGA; 2) data transfer from FPGA DDR to FPGA on-chip memory; 3) kernel computation on the FPGA; 4) data transfer from FPGA on-chip memory to FPGA DDR; and 5) data transfer from FPGA DDR to host. Finding the optimal solution using a mixed-integer nonlinear programming (MINLP) solver is often highly inefficient. Hence, we provide a fast heuristic method that according to our experiments can be much more efficient than the MINLP solver and finds comparable results. For larger problems (more CNN layers), our heuristic method can quickly find (several thousand times faster) much better solutions than the MINLP solver, even if we run the latter for a very long time., This work was supported in part by the European Commission through the ECOSCALE Project under Grant H2020-ICT671632, in part by the Spanish Ministry for Economy and Competitiveness and the European Union (FEDER funds) under Grant TIN2017-86727-C2-1-R and Grant FPI 2015, and in part by the Generalitat de Catalunya under Grant 2017 SGR 786., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

From process models to chatbots

  • López Cuenca, Francisco Anselmo
  • Sànchez-Ferreres, Josep|||0000-0002-7204-4307
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Padró, Lluís|||0000-0003-4738-5019
The effect of digital transformation in organizations needs to go beyond automation, so that human capabilities are also augmented. A possibility in this direction is to make formal representations of processes more accessible for the actors involved. On this line, this paper presents a methodology to transform a formal process description into a conversational agent, which can guide a process actor through the required steps in a user-friendly conversation. The presented system relies on dialog systems and natural language processing and generation techniques, to automatically build a chatbot from a process model. A prototype tool – accessible online – has been developed to transform a process model in BPMN into a chatbot, defined in Artificial Intelligence Marking Language (AIML), which has been evaluated over academic and industrial professionals, showing potential into improving the gap between process understanding and execution., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Actionable conformance checking: from intuitions to code

  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Weidlich, Matthias
  • Dongen, Boudewijn F. van
Conformance checking is receiving increasing attention in the last years. This is due to several reasons, that can be summarized into two: the explosion of digital information that talks about processes, and the need to use this data in order to monitor and improve processes in organizations. Naturally, conformance checking addresses this by providing techniques capable of relating modeled and recorded process information. This paper overviews in a very accessible way the main techniques and feedback of the conformance checking field. Moreover, in order to make it actionable, code snippets are provided so that an organization can start a conformance checking project on its own data., This work has been supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Automatic safe data reuse detection for the WCET analysis of systems with data caches

  • Segarra Flor, Juan
  • Cortadella, Jordi|||0000-0001-8114-250X
  • Gran Tejero, Rubén
  • Viñals Yúfera, Victor
Worst-case execution time (WCET) analysis of systems with data caches is one of the key challenges in real-time systems. Caches exploit the inherent reuse properties of programs, temporarily storing certain memory contents near the processor, in order that further accesses to such contents do not require costly memory transfers. Current worst-case data cache analysis methods focus on specific cache organizations (LRU, locked, ACDC, etc.). In this article, we analyze data reuse (in the worst case) as a property of the program, and thus independent of the data cache. Our analysis method uses Abstract Interpretation on the compiled program to extract, for each static load/store instruction, a linear expression for the address pattern of its data accesses, according to the Loop Nest Data Reuse Theory. Each data access expression is compared to that of prior (dominant) memory instructions to verify whether it presents a guaranteed reuse. Our proposal manages references to scalars, arrays, and non-linear accesses, provides both temporal and spatial reuse information, and does not require the exploration of explicit data access sequences. As a proof of concept we analyze the TACLeBench benchmark suite, showing that most loads/stores present data reuse, and how compiler optimizations affect it. Using a simple hit/miss estimation on our reuse results, the time devoted to data accesses in the worst case is reduced to 27% compared to an always-miss system, equivalent to a data hit ratio of 81%. With compiler optimization, such time is reduced to 6.5%., This work was supported in part by MINECO/AEI/ERDF (EU) under Grant TIN2016-76635-C2-1-R, Grant TIN2017-86727-C2-1-R, and Grant PID2019-105660RB-C21; in part by the Aragón Government under Grant T58_20R research group; in part by the Generalitat de Catalunya under Grant 2017 SGR 786 and Grant FI-DGR 2015; and in part by the Construyendo Europa desde Aragón under Grant ERDF 2014-2020., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Learning random points from geometric graphs or orderings

  • Díaz Cort, Josep|||0000-0003-4422-0067
  • Mcdiarmid, Colin
  • Mitsche, Dieter
Let Xv for v∈V be a family of n iid uniform points in the square (Formula presented.). Suppose first that we are given the random geometric graph (Formula presented.), where vertices u and v are adjacent when the Euclidean distance dE(Xu,Xv) is at most r. Let n3/14≪r≪n1/2. Given G (without geometric information), in polynomial time we can with high probability approximately reconstruct the hidden embedding, in the sense that “up to symmetries,” for each vertex v we find a point within distance about r of Xv; that is, we find an embedding with “displacement” at most about r. Now suppose that, instead of G we are given, for each vertex v, the ordering of the other vertices by increasing Euclidean distance from v. Then, with high probability, in polynomial time we can find an embedding with displacement (Formula presented.)., This research was supported by the grants GRAMM, TIN2017-86727-C2-1-R (J.D.), and by IDEXLYON of Université de Lyon (Programme Investissements d’Avenir, ANR16-IDEX-0005), and by LABEXMILYON (ANR-10-LABX-0070) of Université de Lyon, within the program “Investissements d’Avenir” (ANR-11-IDEX-0007) (D.M.), Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Knowledge-based segmentation to improve accuracy and explainability in non-technical losses detection

  • Calvo Ibáñez, Albert|||0000-0002-3761-9478
  • Coma Puig, Bernat|||0000-0003-3944-797X
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Arias Vicente, Marta|||0000-0001-7359-1815
Utility companies have a great interest in identifying energy losses. Here, we focus on Non-Technical Losses (NTL), which refer to losses caused by utility theft or meter errors. Typically, utility companies resort to machine learning solutions to automate and optimise the identification of such losses. This paper extends an existing NTL-detection framework: by including knowledge-based NTL segmentation, we have detected some opportunities for improving the accuracy and the explanations provided to the utility company. Our improved models focus on specific types of NTL and therefore, the explanations provided are easier to interpret, allowing stakeholders to make more informed decisions. The improvements and results presented in the article may benefit other industrial frameworks., This work has been supported by MINECO and FEDER funds under grants TIN2017-86727-C2-1-R and TIN2017-89244-R, the recognition 2017SGR-856 (MACDA) from AGAUR (Generalitat de Catalunya)., Peer Reviewed, Objectius de Desenvolupament Sostenible::9 - Indústria, Innovació i Infraestructura
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Incremental concurrent model synchronization using triple graph grammars

  • Orejas Valdés, Fernando|||0000-0002-3023-4006
  • Pino Blanco, Elvira|||0000-0003-3376-5096
  • Navarro Gómez, Marisa
In the context of software model-driven development, artifacts are specified by several models describing different aspects, e.g., different views, dynamic behavior, structure, distributed information, etc. Then, maintaining and repairing consistency of the whole specification are crucial issues if the models can be separately developed and updated. Model Synchronization is the process of restoring consistency after the update of one or several of the models. In the present work, we approach the case when conflicts may arise due to concurrently updating different models. Specifically, based on the Triple Graph Grammar approach, we propose an incremental algorithm CSynch for solving conflicts and repairing consistency. In addition, we identify and formalize when a synchronizing solution can be considered adequate and show that our procedure CSynch is sound and complete., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Maria Serna’s contributions to adversarial queuing theory

  • Blesa Aguilera, Maria Josep|||0000-0001-8246-9926
  • Fernández Anta, Antonio
Adversarial Queuing Theory (aqt) is one of the areas to which Maria Serna has deeply contributed in her scientific career. Most of her research in this area took place during the lustrum 2001–2005, while advising the Ph.D. of Maria J. Blesa (2006) [1], and also in conjunction with other researchers. aqt is an adversarial model for the study of packet-switching communication networks under worst case conditions. In this model a fundamental concept is that of stability of a combination of network and packet scheduling protocol in front of an adversary that controls the arrival of packets. There is stability if the adversary cannot cause the number of packets in the network to grow unbounded. Maria’s contributions, summarized in this document, include results in the stability of networks and protocols, and the definition and study of aqt models with important new characteristics, like priorities, failures, or networks with different bandwidths and packet lengths. These results keep impacting the new research currently done in the aqt model., This research has been partially supported by the Agency for Management of University and Research Grants (AGAUR) of the Government of Catalonia under project 2017 SGR 786 (ALBCOM) and by MINECO and FEDER funds under grant GRAMM (ref. TIN2017-86727-C2-1-R)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Computation of alignments of business processes through relaxation labelling and local optimal search

  • Padró, Lluís|||0000-0003-4738-5019
  • Carmona Vargas, Josep|||0000-0001-9656-254X
A fundamental problem in conformance checking is aligning event data with process models. Unfortunately, existing techniques for this task are either complex, or can only be applicable to restricted classes of models. This in practice means that for large inputs, current techniques often fail to produce a result. In this paper we propose a method to compute alignments for unconstrained process models, which relies on the use of relaxation labelling techniques on top of a partial order representation of the process model. The technique proposed in this paper precomputes information used in the search for alignments, and is able to produce real alignments that may be close to optimal ones by combining the aforementioned techniques with a locally applied A strategy. Remarkably, the implementation on the proposed technique achieves a speed-up of several orders of magnitude with respect to the approaches in the literature (either optimal, sup-optimal or approximate), often with a reasonable trade-off on the cost of the obtained alignment., This work has been supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Multi-level dataflow-driven macro placement guided by RTL structure and analytical methods

  • Vidal Obiols, Alexandre|||0000-0002-7016-0160
  • Cortadella, Jordi|||0000-0001-8114-250X
  • Petit Silvestre, Jordi|||0000-0001-8331-8126
  • Galcerán Oms, Marc
  • Martorell Cid, Ferran
When RTL designers define the hierarchy of a system, they exploit their knowledge about the conceptual abstractions devised during the design and the functional interactions between the logical components. This valuable information is often lost during physical synthesis. This paper proposes HiDaP, a novel multi-level algorithm that uses RTL information and analytical methods for the macro placement problem of modern designs dominated by multi-cycle connection pipelines. By taking advantage of the hierarchy tree, the netlist is divided into blocks containing macros and standard cells, and their dataflow affinity is inferred considering the register latency and flow width of their interaction. The layout is represented using slicing structures and generated with a top-down algorithm capable of handling blocks with both hard and soft components. An adaptive multi-objective cost function is used to simultaneously minimize wirelength, timing, overlap and distance to preferred locations, which can be user-defined or generated by analytic methods (spectral and force-directed). These techniques have been applied to a set of large industrial circuits and compared against state-of-theart commercial and academic placers, and also to handcrafted floorplans generated by expert back-end engineers. The proposed approach outperforms previous algorithmic methods and can produce solutions with better wirelength and timing than the best handcrafted floorplans. Post-routing layouts are almost brought to timing closure and DRC cleanness with minimal engineer modification, showing that the generated floorplans provide an excellent starting point for the physical design flow and contribute to reduce turn-around time significantly., This work has been partially supported by a grant from Inphi Corporation and funds from the Spanish Ministry for Economy and Competitiveness and the European Union (FEDER funds) under grant TIN2017-86727-C2-1-R, and the Generalitat de Catalunya (2017 SGR 786)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

On bipartite sum basic equilibria

  • Álvarez Faura, M. del Carme|||0000-0003-2352-0546
  • Messegué Buisan, Arnau|||0000-0002-7425-7592
A connected and undirected graph G of size n≥1 is said to be a sum basic equilibrium iff for every edge uv from G and any node v′ from G, when performing the swap of the edge uv for the edge uv′ the sum of the distances from u to all the other nodes is not strictly reduced. This concept comes from the so called Network Creation Games, a wide subject inside Algorithmic Game Theory that tries to better understand how Internet-like networks behave. It has been shown that the diameter of sum basic equilibria is 2O(logn√) in general and at most 2 for trees. In this paper we see that the upper bound of 2 not only holds for trees but for bipartite graphs, too. Specifically, we show that the only bipartite sum basic equilibrium networks are the complete bipartite graphs Kr,s with r,s≥1 ., This work has been partially supported by funds from the Spanish Ministry for Economy and Competitiveness (MINECO) and the European Union (FEDER funds) under grant GRAMM (TIN2017-86727-C2-1-R) and from the Catalan Agency for Management of University and Research Grants (AGAUR, Generalitat de Catalunya) under project ALBCOM 2017-SGR-786., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On the PoA conjecture: Trees versus biconnected components

  • Álvarez Faura, M. del Carme|||0000-0003-2352-0546
  • Messegué Buisan, Arnau|||0000-0002-7425-7592
In the classical model of network creation games introduced by Fabrikant et al. [Ona network creation game, in Proceedings of the Twenty-Second Annual Symposium on Principlesof Distributed Computing (PODC`03), 2003, pp. 347--351],nplayers correspond to the nodes of anetwork buying links of price\alpha and to the other players with the goal of being well-connected tothe resulting network. Still as an open problem, theconstantPoAconjecturestates that thePriceof Anarchy(PoA) is constant for any\alpha . When tackling this problem distinct behaviors must betaken into the account depending on whether\alpha has either large or low value. It is known that for\alpha >4n - 13 everyneis a tree and for\alpha =O(n1 - \delta ) with\delta \geq 1/lognthe diameter of networks thatare in equilibrium when restricting to deviations that consist only in buying links (buying equilibria)is at most a constant. These results imply that the PoA is constant for the disjoint union of thetwo ranges, and thus the constant PoA conjecture seems to be true for most of all the possiblevalues\alpha . In this paper we study the PoA for the remaining range of\alpha and we show the following:(i) For\alpha > n(1 +\epsilon ) the PoA is constant by proving that the size of any biconnected componentof an equilibrium graph is constant. (ii) For\alpha \leq n(1 +\epsilon ) we have that PoA = \Theta (dmax), wheredmaxis the maximum diameter of an equilibrium graph for the same range of\alpha . Therefore if theconstant PoA conjecture was false, it would suffice to construct equilibria of nonconstant diameter.Towards this direction we find nontrivialbuying equilibriaof nonconstant diameter when\alpha > n1 - \delta and\delta =O(2 - \surd \mathrm{l}\mathrm{o}\mathrm{g}n), exploring new intimate relationships betweendistance-uniform graphsandbuying equilibria., This work was partially supported by funds from the Spanish Ministry for Economy and Competitiveness (MINECO) and the European Union (FEDER funds) under grant GRAMM (TIN2017-86727-C2-1-R), from the European Union-NextGenerationEU under Margarita Salas, from UPC grant 2021UPC-MS-66935, and from the Catalan Agency for Management of University and Research Grants (AGAUR, Generalitat de Catalunya) under project ALBCOM 2017-SGR-786., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Refining indeterministic choice: Imprecise probabilities and strategic thinking

  • Castro Rabal, Jorge|||0000-0002-1390-1313
  • Gabarró Vallès, Joaquim|||0000-0003-3771-2813
  • Serna Iglesias, María José|||0000-0001-9729-8648
Often, uncertainty is present in processes that are part of our routines. Having tools to understand the consequences of unpredictability is convenient. We introduce a general framework to deal with uncertainty in the realm of distribution sets that are descriptions of imprecise probabilities. We propose several non-biased refinement strategies to obtain sensible forecasts about results of uncertain processes. Initially, uncertainty on a system is modeled as the non-deterministic choice of its possible behaviors. Our refinement hypothesis translates non-determinism into imprecise probabilistic choices. Imprecise probabilities allow us to propose a notion of uncertainty refinement in terms of set inclusions. Later on, unpredictability is tackled through a strategic approach using uncertainty profiles and angel/daemon games ([Formula: see text]-games). Here, imprecise probabilities form the set of mixed strategies and Nash equilibria corresponds to natural uncertainty refinements. We use this approach to study the performance of Web applications — in terms of response times — under stress conditions., J. Castro was partially supported by MINECO and EU FEDER funds grant TIN2017-89244-R and AGAUR grant 2017 SGR-856.J. Gabarro and M. Serna were partially supported by MINECO and EU FEDER funds grant TIN2017-86727-C2-1-R and AGAUR 2017 SGR 786., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Formal reasoning on natural language descriptions of processes

  • Sànchez-Ferreres, Josep|||0000-0002-7204-4307
  • Burattin, Andrea
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Montali, Marco
  • Padró, Lluís|||0000-0003-4738-5019
The existence of unstructured information that describes processes represents a challenge in organizations, mainly because this data cannot be directly referred into process-aware ecosystems due to ambiguities. Still, this information is important, since it encompasses aspects of a process that are left out when formalizing it on a particular modelling notation. This paper picks up this challenge and faces the problem of ambiguities by acknowledging its existence and mitigating it. Specifically, we propose a framework to partially automate the elicitation of a formal representation of a textual process description, via text annotation techniques on top of natural language processing. The result is the ATDP language, whose syntax and semantics are described in this paper. ATDP allows to explicitly cope with several interpretations of the same textual description of a process model. Moreover, we link the ATDP language to a formal reasoning engine and show several use cases. A prototype tool enabling the complete methodology has been implemented, and several examples using the tool are provided., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Online conformance checking using behavioural patterns

  • Burattin, Andrea
  • Zelst, Sebastiaan J. van
  • Armas Cervantes, Abel
  • Dongen, Boudewijn F. van
  • Carmona Vargas, Josep|||0000-0001-9656-254X
New and compelling regulations (e.g., the GDPR in Europe) impose tremendous pressure on organizations, in order to adhere to standard procedures, processes, and practices. The field of conformance checking aims to quantify the extent to which the execution of a process, captured within recorded corresponding event data, conforms to a given reference process model. Existing techniques assume a post-mortem scenario, i.e. they detect deviations based on complete executions of the process. This limits their applicability in an online setting. In such context, we aim to detect deviations online (i.e., in-vivo), in order to provide recovery possibilities before the execution of a process instance is completed. Also, current techniques assume cases to start from the initial stage of the process, whereas this assumption is not feasible in online settings. In this paper, we present a generic framework for online conformance checking, in which the underlying process is represented in terms of behavioural patterns and no assumption on the starting point of cases is needed. We instantiate the framework on the basis of Petri nets, with an accompanying new unfolding technique. The approach is implemented in the process mining tool ProM, and evaluated by means of several experiments including a stress-test and a comparison with a similar technique., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

An evolutionary technique to approximate multiple optimal alignments

  • Taymouri, Farbod
  • Carmona Vargas, Josep|||0000-0001-9656-254X
The alignment of observed and modeled behavior is an essential aid for organizations, since it opens the door for root-cause analysis and enhancement of processes. The state-of-the-art technique for computing alignments has exponential time and space complexity, hindering its applicability for medium and large instances. Moreover, the fact that there may be multiple optimal alignments is perceived as a negative situation, while in reality it may provide a more comprehensive picture of the model’s explanation of observed behavior, from which other techniques may benefit. This paper presents a novel evolutionary technique for approximating multiple optimal alignments. Remarkably, the memory footprint of the proposed technique is bounded, representing an unprecedented guarantee with respect to the state-of-the-art methods for the same task. The technique is implemented into a tool, and experiments on several benchmarks are provided., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Structural computation of alignments of business processes over partial orders

  • Taymouri, Farbod
  • Carmona Vargas, Josep|||0000-0001-9656-254X
Relating event data and process models is becoming an important element for organizations. This paper presents a novel approach for aligning traces and process models. The approach is based on the structural theory of Petri nets (the marking equation), applied over an unfolding of the initial process model. Given an observed trace, the approach adopts an iterative optimization mechanism on top of the unfolding, computing at each iteration part of the resulting alignment. In contrast to the previous work that is primarily grounded in the marking equation, this approach is guaranteed to provide real solutions, and tries to mimic as much as possible the events observed in the trace. Experiments witness the significance of this approach both in quality and execution time perspectives., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

RTL-aware dataflow-driven macro placement

  • Vidal Obiols, Alexandre|||0000-0002-7016-0160
  • Cortadella, Jordi|||0000-0001-8114-250X
  • Petit Silvestre, Jordi|||0000-0001-8331-8126
  • Galcerán Oms, Marc
  • Martorell Cid, Ferran
© 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes,creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works., When RTL designers define the hierarchy of a system, they exploit their knowledge about the conceptual abstractions devised during the design and the functional interactions between the logical components. This valuable information is often lost during physical synthesis. This paper proposes a novel multi-level approach for the macro placement problem of complex designs dominated by macro blocks, typically memories. By taking advantage of the hierarchy tree, the netlist is divided into blocks containing macros and standard cells, and their dataflow affinity is inferred considering the latency and flow width of their interaction. The layout is represented using slicing structures and generated with a top-down algorithm capable of handling blocks with both hard and soft components, aimed at wirelength minimization. These techniques have been applied to a set of large industrial circuits and compared against both a commercial floorplanner and handcrafted floorplans by expert back-end engineers. The proposed approach outperforms the commercial tool and produces solutions with similar quality to the best handcrafted floorplans. Therefore, the generated floorplans provide an excellent starting point for the physical design iterations and contribute to reduce turn-around time significantly., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

A navigational logic for reasoning about graph properties

  • Navarro Gómez, Marisa
  • Orejas Valdés, Fernando|||0000-0002-3023-4006
  • Pino Blanco, Elvira|||0000-0003-3376-5096
  • Lambers, Leen
Graphs play an important role in many areas of Computer Science. In particular, our work is motivated by model-driven software development and by graph databases. For this reason, it is very important to have the means to express and to reason about the properties that a given graph may satisfy. With this aim, in this paper we present a visual logic that allows us to describe graph properties, including navigational properties, i.e., properties about the paths in a graph. The logic is equipped with a deductive tableau method that we have proved to be sound and complete., This work was supported by the Spanish Ministry of Economy and Competitiveness and the European Union (FEDER funds) under grant GRAMM (ref. TIN2017-86727-C2-1-R, TIN2017-86727-C2-2-R) and by the Basque Project GIU15/30, and grant UFI11/45., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Dynamic pipelining of multidimensional range queries

  • Duch Brown, Amalia|||0000-0003-4371-1286
  • Lugosi, Daniel
  • Pasarella Sánchez, Ana Edelmira|||0000-0001-8315-4977
  • Zoltan Torres, Ana Cristina
The problem of evaluating orthogonal range queries efficiently has been studied widely in the data structures community. It has been common wisdom for several years that for queries containing more than 20% of the elements of the dataset a linear scanning of the data was the most efficient solution. In recent experimental works using modern hardware –with main memory and parallelism– the conclusion is that linear scan is preferable for almost every query configuration (even containing a 1% of the data). In this work we propose an alternative approach to evaluate multidimensional range queries based on the dynamic pipeline paradigm –using main memory and concurrency. Our aim is to prove that under this framework, it is possible to beat the performance of linear scanning by the one of hierarchical multidimensional data structures –such as kd trees, quad trees, Rtrees or similar., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Extracting annotations from textual descriptions of processes

  • Quishpi Betún, Luis Hernán|||0000-0002-3539-5853
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Padró, Lluís|||0000-0003-4738-5019
Organizations often have textual descriptions as a way to document their main processes. These descriptions are primarily used by the company’s personnel to understand the processes, specially for those ones that cannot interpret formal descriptions like BPMN or Petri nets. In this paper we present a technique based on Natural Language Processing and a query language for tree-based patterns, that extracts annotations describing key process elements like actions, events, agents/patients, roles and control-flow relations. Annotated textual descriptions of processes are a good compromise between understandability (since at the end, it is just text), and behavior. Moreover, as it has been recently acknowledged, obtaining annotated textual descriptions of processes opens the door to unprecedented applications, like formal reasoning or simulation on the underlying described process. Applying our technique on several publicly available texts shows promising results in terms of precision and recall with respect to the state-of-the art approach for a similar task., This work has been supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R, and by the Ecuadorian National Secretary of Higher Education, Science and Technology (SENESCYT)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Improving the extraction of process annotations from text with inter-sentence analysis

  • Quishpi Betún, Luis Hernán|||0000-0002-3539-5853
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Padró, Lluís|||0000-0003-4738-5019
The automatic extraction of formal process information from textual descriptions of processes is a challenging problem, but worth exploring, since it enables organizations to align complementary information that talks about processes. In this paper we continue our previous work on this area, based on defining hierarchical/tree patterns on the dependency trees that arise from the linguistic analysis. We now incorporate a new abstraction layer on these patterns, that consider relationships between nearby sentences. The aim of this extension is to capture inter-sentence relationships that typically arise in textual descriptions of processes. The experiments done on publicly available benchmarks corroborate this intuition, showing a significant rise in the ability to capture all the important control-flow relationships defined in the text., This work has been supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R, and by the Ecuadorian National Secretary of Higher Education, Science and Technology (SENESCYT)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

On list k-coloring convex bipartite graphs

  • Díaz Cort, Josep|||0000-0003-4422-0067
  • Yasar Diner, Oznur
  • Serna Iglesias, María José|||0000-0001-9729-8648
  • Serra Albó, Oriol|||0000-0001-8561-4631
List k–Coloring (LI k-COL) is the decision problem asking if a given graph admits a proper coloring compatible with a given list assignment to its vertices with colors in {1,2,..., k}. The problem is known to be NP-hard even for k = 3 within the class of 3–regular planar bipartite graphs and for k = 4 within the class of chordal bipartite graphs. In 2015 Huang, Johnson and Paulusma asked for the complexity of LI 3-COL in the class of chordal bipartite graphs. In this paper, we give a partial answer to this question by showing that LI k-COL is polynomial in the class of convex bipartite graphs. We show first that biconvex bipartite graphs admit a multichain ordering, extending the classes of graphs where a polynomial algorithm of Enright, Stewart and Tardos (2014) can be applied to the problem. We provide a dynamic programming algorithm to solve the LI k-COL in the class of convex bipartite graphs. Finally, we show how our algorithm can be modified to solve the more general LI H-COL problem on convex bipartite graphs., J. Díaz and M. Serna are partially supported by funds from MINECO and EU FEDER under grant TIN 2017-86727-C2-1-R AGAUR project ALBCOM 2017- SGR-786. O. Y. Diner is partially supported by the Scientific and Technological Research Council Tubitak under project BIDEB 2219-1059B191802095 and by Kadir Has University under project 2018-BAP-08. O. Serra is supported by the Spanish Ministry of Science under project MTM2017-82166-P., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Power to invest

  • Castro Rabal, Jorge|||0000-0002-1390-1313
  • Gabarró Vallès, Joaquim|||0000-0003-3771-2813
  • Serna Iglesias, María José|||0000-0001-9729-8648
In this post recession time it is important to measure the possibilities offered by a society in relation to investments. To do that, we consider an investment schema I= (R;R_1,...,R_n) where R is a lower bound on the desired return and the R_i's are the return of the assets (to invest in). We introduce, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Bridging the gap between energy consumption and distribution through non-technical loss detection

  • Coma Puig, Bernat|||0000-0003-3944-797X
  • Carmona Vargas, Josep|||0000-0001-9656-254X
The application of Artificial Intelligence techniques in industry equips companies with new essential tools to improve their principal processes. This is especially true for energy companies, as they have the opportunity, thanks to the modernization of their installations, to exploit a large amount of data with smart algorithms. In this work we explore the possibilities that exist in the implementation of Machine-Learning techniques for the detection of Non-Technical Losses in customers. The analysis is based on the work done in collaboration with an international energy distribution company. We report on how the success in detecting Non-Technical Losses can help the company to better control the energy provided to their customers, avoiding a misuse and hence improving the sustainability of the service that the company provides., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Flexible process model mapping using relaxation labeling

  • Delicado Alcántara, Luis
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Padró, Lluís|||0000-0003-4738-5019
Computing a mapping between two process models is a crucial technique, since it enables reasoning and operating across processes, like providing a similarity score between two processes, or merging different process variants to generate a consolidated process model. In this paper we present a new flexible technique for process model mapping, based on the relaxation labeling constraint satisfaction algorithm. The technique can be instantiated so that different modes are devised, depending on the context. For instance, it can be adapted to the case where one of the mapped process models is incomplete, or it can be used to ground an adaptable similarity measure between process models. The approach has been implemented inside the open platform NLP4BPM, providing a visualization of the performed mappings and computed similarity scores. The experimental results witness the flexibility and usefulness of the technique proposed., This work has been supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Optimized SAT encoding of conformance checking artefacts

  • Boltenhagen, Mathilde
  • Chatain, Thomas
  • Carmona Vargas, Josep|||0000-0001-9656-254X
Conformance checking is a growing discipline that aims at assisting organizations in monitoring their processes. On its core, conformance checking relies on the computation of particular artefacts which enable reasoning on the relation between observed and modeled behavior. It is widely acknowledge that the computation of these artifacts is the lion’s share of conformance checking techniques. This paper shows how important conformance artefacts like alignments, anti-alignments or multi-alignments, defined over the Levenshtein edit distance, can be efficiently computed by encoding the problem as an optimized SAT instance. From a general perspective, the work advocates for a unified family of techniques that can compute conformance artefacts in the same way. The implementation of the techniques presented in this paper show capabilities for dealing with both synthetic and real-life instances, which may open the door for a fresh way of applying conformance checking in the near future., This work has been supported by Farman institute at ENS Paris-Saclay and by MINECO and FEDER funds under Grant TIN2017-86727-C2-1-R., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

CC4Spark: Distributing event logs and big complex conformance checking problems

  • Valencia Parra, Álvaro
  • Varela Vaca, Ángel Jesús
  • Gómez López, María Teresa
  • Carmona Vargas, Josep|||0000-0001-9656-254X
Conformance checking is one of the disciplines that best exposes the power of process mining, since it allows detecting anomalies and deviations in business processes, helping to assess and improve the quality of these. This is an indispensable task, especially in Big Data environments where large amounts of data are generated, and where the complexity of the processes is increasing. CC4Spark enables companies to face this challenging scenario in twofold. First, it supports distributing conformance checking alignment problems by means of a Big Data infrastructure based on Apache Spark, allowing users to import, transform and prepare event logs stored in distributed data sources, and solve them in a distributed environment. Secondly, this tool supports decomposed Petri nets. This helps to noticeably reduce the complexity of the models. Both characteristics help companies in facing increasingly frequent scenarios with large amounts of logs with highly complex business processes. CC4Spark is not tied to any particular conformance checking algorithm, so that users can employ customised algorithms., Ministry of Science and Technology of Spain: ECLIPSE (RTI2018-094283-B-C33) project; European Regional Development Fund (ERDF/FEDER); MINECO (TIN2017-86727-C2-1-R); University of Seville: VI Plan Propio de Investigación y Transferencia (VI PPIT-US)., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

Measuring investment opportunities under uncertainty

  • Castro Rabal, Jorge|||0000-0002-1390-1313
  • Gabarró Vallès, Joaquim|||0000-0003-3771-2813
  • Serna Iglesias, María José|||0000-0001-9729-8648
In order to make sound economic decisions it is important to measure the possibilities offered by a market in relation to investments. Provided an investment scheme S = (r; R1, . . . , Rn), where r is a lower bound on the desired investment return and the Ri’s are the asset yields, the power to invest measures the capability of the scheme to fulfill requirement r. The power to invest is inspired in the Coleman’s power of a collectivity to act. We exemplify this approach considering subsets of companies from stock indexes IBEX35 and DAX. We extend the power to invest to investment schemata with imprecise yields. We prove basic relations with the precise yields case and we also show that good monotonicity properties hold. Finally, we propose an analysis, through integrals of the power function, for the case of an unspecific desired return r., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Support-reducing decomposition for FPGA mapping

  • Machado, Lucas
  • Cortadella, Jordi|||0000-0001-8114-250X
Decomposition is a technology-independent process, in which a large complex function is broken into smaller, less complex functions. The costs of two-level or factored-form representations (cubes and literals) are used in most decomposition methods, as they have a high correlation with the area of cell-based designs. However, this correlation is weaker for field-programmable gate arrays (FPGAs) based on look-up tables. Furthermore, local optimizations have limited power due to the structural bias of the circuit descriptions. This paper tries to reduce the structural biasing by remapping the LUT network and decomposing the derived functions using the support as cost function. The proposed method improves the FPGA mapping results of a commercial tool for the 20 largest MCNC benchmarks, with gains of 28% in delay plus 18% in area when targeting delay, and a reduction of 28% in area plus 14% in delay with area as cost function. Results with 23% less area and 6% less delay are obtained after physical synthesis (post place-and-route). Moreover, 12 of the best known results for delay (and 3 for area) of the EPFL benchmarks are improved., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Supporting the process of learning and teaching process models

  • Sànchez-Ferreres, Josep|||0000-0002-7204-4307
  • Delicado Alcántara, Luis
  • Andaloussi, Amine Abbad
  • Burattin, Andrea
  • Calderón Ruiz, Guillermo
  • Weber, Barbara
  • Carmona Vargas, Josep|||0000-0001-9656-254X
  • Padró, Lluís|||0000-0003-4738-5019
The creation of a process model faces the challenge of constructing a syntactically correct entity which accurately reflects the semantics of the reality, and is understandable. This paper proposes a framework called ModelJudge , focused towards the two main actors in the process of learning process model creation: novice modellers and instructors. For modellers, the platform enables the automatic validation of the process models created from the textual description, providing explanations about quality issues in the model. ModelJudge can provide diagnostics regarding model structure, writing style, and seman- tics by aligning annotated textual descriptions to models. For instructors, the platform facilitates the creation of modelling exercises by providing an editor to annotate the main parts of a textual description, that is empowered with Natural Language Processing (NLP) capabilities so that the annotation effort is minimized. So far around 300 students, in process modelling courses of five different universities around the world have used the platform. The feedback gathered from some of these courses shows good potential in helping students to improve their learning experience, which might, in turn, impact process model quality and understandability. Moreover, our results show that instructors can benefit from getting insights into the evolution of modeling processes including arising quality issues of single students, but also discover tendencies in groups of students. Although the framework has been applied to process model creation, it could be extrapolated to other contexts where the creation of models based on a textual description plays an important role., This work has been partially supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

On the price of anarchy for high-price links

  • Álvarez Faura, M. del Carme|||0000-0003-2352-0546
  • Messegué Buisan, Arnau|||0000-0002-7425-7592
We study Nash equilibria and the price of anarchy in the classic model of Network Creation Games introduced by Fabrikant, Luthra, Maneva, Papadimitriou and Shenker in 2003. This is a selfish network creation model where players correspond to nodes in a network and each of them can create links to the other n−1 players at a prefixed price α>0. The player’s goal is to minimise the sum of her cost buying edges and her cost for using the resulting network. One of the main conjectures for this model states that the price of anarchy, i.e. the relative cost of the lack of coordination, is constant for all α. This conjecture has been confirmed for α=O(n1−δ) with δ≥1/logn and for α>4n−13. The best known upper bound on the price of anarchy for the remaining range is 2O(logn√) . We give new insights into the structure of the Nash equilibria for α>n and we enlarge the range of the parameter α for which the price of anarchy is constant. Specifically, we prove that for any small ϵ>0, the price of anarchy is constant for α>n(1+ϵ) by showing that any biconnected component of any non-trivial Nash equilibrium, if it exists, has at most a constant number of nodes., This work has been partially supported by funds from the Spanish Ministry for Economy and Competitiveness (MINECO) and the European Union (FEDER funds) under grant GRAMM (TIN2017-86727-C2-1-R) and from the Catalan Agency for Management of University and Research Grants (AGAUR, Generalitat de Catalunya) under project ALBCOM 2017-SGR-786., Peer Reviewed
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publicación Artículo científico (JournalArticle)

Automatic Safe Data Reuse Detection for the WCET Analysis of Systems With Data Caches

  • Segarra, J.
  • Cortadella, J.
  • Gran Tejero, R.
  • Viñals-Yufera, V.
Worst-case execution time (WCET) analysis of systems with data caches is one of the key challenges in real-time systems. Caches exploit the inherent reuse properties of programs, temporarily storing certain memory contents near the processor, in order that further accesses to such contents do not require costly memory transfers. Current worst-case data cache analysis methods focus on specific cache organizations (LRU, locked, ACDC, etc.). In this article, we analyze data reuse (in the worst case) as a property of the program, and thus independent of the data cache. Our analysis method uses Abstract Interpretation on the compiled program to extract, for each static load/store instruction, a linear expression for the address pattern of its data accesses, according to the Loop Nest Data Reuse Theory. Each data access expression is compared to that of prior (dominant) memory instructions to verify whether it presents a guaranteed reuse. Our proposal manages references to scalars, arrays, and non-linear accesses, provides both temporal and spatial reuse information, and does not require the exploration of explicit data access sequences. As a proof of concept we analyze the TACLeBench benchmark suite, showing that most loads/stores present data reuse, and how compiler optimizations affect it. Using a simple hit/miss estimation on our reuse results, the time devoted to data accesses in the worst case is reduced to 27% compared to an always-miss system, equivalent to a data hit ratio of 81%. With compiler optimization, such time is reduced to 6.5%.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Formal reasoning on natural language descriptions of processes

  • Sànchez-Ferreres, Josep
  • Burattin, Andrea
  • Carmona Vargas, Josep
  • Montali, Marco
  • Padró, Lluís
The existence of unstructured information that describes processes represents a challenge in organizations, mainly because this data cannot be directly referred into process-aware ecosystems due to ambiguities. Still, this information is important, since it encompasses aspects of a process that are left out when formalizing it on a particular modelling notation. This paper picks up this challenge and faces the problem of ambiguities by acknowledging its existence and mitigating it. Specifically, we propose a framework to partially automate the elicitation of a formal representation of a textual process description, via text annotation techniques on top of natural language processing. The result is the ATDP language, whose syntax and semantics are described in this paper. ATDP allows to explicitly cope with several interpretations of the same textual description of a process model. Moreover, we link the ATDP language to a formal reasoning engine and show several use cases. A prototype tool enabling the complete methodology has been implemented, and several examples using the tool are provided., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Refining indeterministic choice: Imprecise probabilities and strategic thinking

  • Castro Rabal, Jorge
  • Gabarró Vallès, Joaquim
  • Serna Iglesias, María José
Often, uncertainty is present in processes that are part of our routines. Having tools to understand the consequences of unpredictability is convenient. We introduce a general framework to deal with uncertainty in the realm of distribution sets that are descriptions of imprecise probabilities. We propose several non-biased refinement strategies to obtain sensible forecasts about results of uncertain processes. Initially, uncertainty on a system is modeled as the non-deterministic choice of its possible behaviors. Our refinement hypothesis translates non-determinism into imprecise probabilistic choices. Imprecise probabilities allow us to propose a notion of uncertainty refinement in terms of set inclusions. Later on, unpredictability is tackled through a strategic approach using uncertainty profiles and angel/daemon games ([Formula: see text]-games). Here, imprecise probabilities form the set of mixed strategies and Nash equilibria corresponds to natural uncertainty refinements. We use this approach to study the performance of Web applications — in terms of response times — under stress conditions., J. Castro was partially supported by MINECO and EU FEDER funds grant TIN2017-89244-R and AGAUR grant 2017 SGR-856.J. Gabarro and M. Serna were partially supported by MINECO and EU FEDER funds grant TIN2017-86727-C2-1-R and AGAUR 2017 SGR 786., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Support-reducing decomposition for FPGA mapping

  • Machado, Lucas
  • Cortadella, Jordi
Decomposition is a technology-independent process, in which a large complex function is broken into smaller, less complex functions. The costs of two-level or factored-form representations (cubes and literals) are used in most decomposition methods, as they have a high correlation with the area of cell-based designs. However, this correlation is weaker for field-programmable gate arrays (FPGAs) based on look-up tables. Furthermore, local optimizations have limited power due to the structural bias of the circuit descriptions. This paper tries to reduce the structural biasing by remapping the LUT network and decomposing the derived functions using the support as cost function. The proposed method improves the FPGA mapping results of a commercial tool for the 20 largest MCNC benchmarks, with gains of 28% in delay plus 18% in area when targeting delay, and a reduction of 28% in area plus 14% in delay with area as cost function. Results with 23% less area and 6% less delay are obtained after physical synthesis (post place-and-route). Moreover, 12 of the best known results for delay (and 3 for area) of the EPFL benchmarks are improved., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Explainable predictive process monitoring

  • Galanti, Riccardo
  • Coma Puig, Bernat
  • de Leoni, Massimiliano
  • Carmona Vargas, Josep
  • Navarin, Nicolò
Predictive Business Process Monitoring is becoming an essential aid for organizations, providing online operational support of their processes. This paper tackles the fundamental problem of equipping predictive business process monitoring with explanation capabilities, so that not only the what but also the why is reported when predicting generic KPIs like remaining time, or activity execution. We use the game theory of Shapley Values to obtain robust explanations of the predictions. The approach has been implemented and tested on real-life benchmarks, showing for the first time how explanations can be given in the field of predictive business process monitoring., This work is supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R and by the Department of Mathematics, University of Padua, with HPC resources., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Knowledge-based segmentation to improve accuracy and explainability in non-technical losses detection

  • Calvo Ibáñez, Albert
  • Coma Puig, Bernat
  • Carmona Vargas, Josep
  • Arias Vicente, Marta
Utility companies have a great interest in identifying energy losses. Here, we focus on Non-Technical Losses (NTL), which refer to losses caused by utility theft or meter errors. Typically, utility companies resort to machine learning solutions to automate and optimise the identification of such losses. This paper extends an existing NTL-detection framework: by including knowledge-based NTL segmentation, we have detected some opportunities for improving the accuracy and the explanations provided to the utility company. Our improved models focus on specific types of NTL and therefore, the explanations provided are easier to interpret, allowing stakeholders to make more informed decisions. The improvements and results presented in the article may benefit other industrial frameworks., This work has been supported by MINECO and FEDER funds under grants TIN2017-86727-C2-1-R and TIN2017-89244-R, the recognition 2017SGR-856 (MACDA) from AGAUR (Generalitat de Catalunya)., Peer Reviewed, Objectius de Desenvolupament Sostenible::9 - Indústria, Innovació i Infraestructura, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

CC4Spark: Distributing event logs and big complex conformance checking problems

  • Valencia Parra, Álvaro
  • Varela Vaca, Ángel Jesús
  • Gómez López, María Teresa
  • Carmona Vargas, Josep
Conformance checking is one of the disciplines that best exposes the power of process mining, since it allows detecting anomalies and deviations in business processes, helping to assess and improve the quality of these. This is an indispensable task, especially in Big Data environments where large amounts of data are generated, and where the complexity of the processes is increasing. CC4Spark enables companies to face this challenging scenario in twofold. First, it supports distributing conformance checking alignment problems by means of a Big Data infrastructure based on Apache Spark, allowing users to import, transform and prepare event logs stored in distributed data sources, and solve them in a distributed environment. Secondly, this tool supports decomposed Petri nets. This helps to noticeably reduce the complexity of the models. Both characteristics help companies in facing increasingly frequent scenarios with large amounts of logs with highly complex business processes. CC4Spark is not tied to any particular conformance checking algorithm, so that users can employ customised algorithms., Ministry of Science and Technology of Spain: ECLIPSE (RTI2018-094283-B-C33) project; European Regional Development Fund (ERDF/FEDER); MINECO (TIN2017-86727-C2-1-R); University of Seville: VI Plan Propio de Investigación y Transferencia (VI PPIT-US)., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Fixed partial match queries in quadtrees

  • Duch Brown, Amalia
  • Lau Laynes-Lozada, Gustavo Salvador
  • Martínez Parra, Conrado
Several recent papers in the literature have addressed the analysis of the cost P_{n,q} of partial match search for a given fixed query q - that has s out of K specified coordinates - in different multidimensional data structures. Indeed, detailed asymptotic estimates for the main term in the expected cost P_{n,q} = E {P_{n,q}} in standard and relaxed K-d trees are known (for any dimension K and any number s of specified coordinates), as well as stronger distributional results on P_{n,q} for standard 2-d trees and 2-dimensional quadtrees. In this work we derive a precise asymptotic estimate for the main order term of P_{n,q} in quadtrees, for any values of K and s, 0 < s < K, under the assumption that the limit of P_{n,q}/n^alpha when n -> infty exists, where alpha is the exponent of n in the expected cost of a random partial match query with s specified coordinates in a random K-dimensional quadtree., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

From process models to chatbots

  • López Cuenca, Francisco Anselmo
  • Sànchez-Ferreres, Josep
  • Carmona Vargas, Josep
  • Padró, Lluís
The effect of digital transformation in organizations needs to go beyond automation, so that human capabilities are also augmented. A possibility in this direction is to make formal representations of processes more accessible for the actors involved. On this line, this paper presents a methodology to transform a formal process description into a conversational agent, which can guide a process actor through the required steps in a user-friendly conversation. The presented system relies on dialog systems and natural language processing and generation techniques, to automatically build a chatbot from a process model. A prototype tool – accessible online – has been developed to transform a process model in BPMN into a chatbot, defined in Artificial Intelligence Marking Language (AIML), which has been evaluated over academic and industrial professionals, showing potential into improving the gap between process understanding and execution., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Evolutionary trajectories of new duplicated and putative de novo genes

  • Montañés Domínguez, José Carlos
  • Huertas Pulido, Marta
  • Messeguer Peypoch, Xavier
  • Albà Soler, Maria del Mar
The formation of new genes during evolution is an important motor of functional innovation, but the rate at which new genes originate and the likelihood that they persist over longer evolutionary periods are still poorly understood questions. Two important mechanisms by which new genes arise are gene duplication and de novo formation from a previously noncoding sequence. Does the mechanism of formation influence the evolutionary trajectories of the genes? Proteins arisen by gene duplication retain the sequence and structural properties of the parental protein, and thus they may be relatively stable. Instead, de novo originated proteins are often species specific and thought to be more evolutionary labile. Despite these differences, here we show that both types of genes share a number of similarities, including low sequence constraints in their initial evolutionary phases, high turnover rates at the species level, and comparable persistence rates in deeper branchers, in both yeast and flies. In addition, we show that putative de novo proteins have an excess of substitutions between charged amino acids compared with the neutral expectation, which is reflected in the rapid loss of their initial highly basic character. The study supports high evolutionary dynamics of different kinds of new genes at the species level, in sharp contrast with the stability observed at later stages., We acknowledge funding from Ministerio de Ciencia e Innovación Agencia Estatal de Investigación grant PGC2018-094091-B-I00 (cofunded by Fondo Europeo de Desarrollo Regional), as well as grants PID2021-122726NB-I00 and PID2021-122830OB-C43 funded by MCIN/AEI/10.13039/501100011033 and by “ERDF: A way of making Europe”, by the “European Union”. We also acknowledge funding from Generalitat de Catalunya, grant 2021SGR00042. The work was also funded by the European Union (ERC, NovoGenePop, project number 101052538)., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Power-optimal mapping of CNN applications to cloud-based Multi-FPGA platforms

  • Shan, Junnan
  • Lazarescu, Mihai T.
  • Cortadella, Jordi
  • Lavagno, Luciano
  • Casu, Mario R.
Multi-FPGA platforms like Amazon Web Services F1 are perfect to accelerate multi-kernel pipelined applications, like Convolutional Neural Networks (CNNs). To reduce energy consumption, we propose to upload at runtime the best power-optimized CNN implementation for a given throughput constraint. Our design method gives the best number of parallel instances of each kernel, their allocation to the FPGAs, the number of powered-on FPGAs and their clock frequency. This is obtained by solving a mixed-integer, non-linear optimization problem that models power and performance of each component, as well as the duration of the computation phases-data transfer between a host CPU and the FPGA memory (typically DDR), data transfer between DDR and FPGA, and FPGA computation. The results show that the power saved compared to simply clock gating the fastest implementation is obviously very high, but it is also much more significant than simply scaling the frequency of the fastest implementation or replicating the slowest implementation on multiple FPGAs., This work was partially supported in part by the European Commission through the ECOSCALE Project under Grant H2020-ICT671632, in part by the Spanish Ministry for Economy and Competitiveness and the European Union (FEDER Funds) under Grant TIN2017-86727-C2-1- R and Grant FPI 2015, and in part by the Generalitat de Catalunya under Grant 2017 SGR 786., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Computing alignments of well-formed process models using local search

  • Taymouri, Farbod
  • Carmona Vargas, Josep
The alignment of observed and modeled behavior is an essential element for organizations, since it opens the door for conformance checking and enhancement of processes. The state-of-the-art technique for computing alignments has exponential time and space complexity, hindering its applicability for medium and large instances. In this article, a novel approach is presented to tackle the challenge of computing an alignment for large-problem instances that correspond to well-formed process models. Given an observed trace, first it uses a novel replay technique to find an initial candidate trace in the model. Then a local search framework is applied to try to improve the alignment until no further improvement is possible. The implementation of the presented technique reveals a magnificent reduction both in computation time and in memory usage. Moreover, although the proposed technique does not guarantee the derivation of an alignment with minimal cost, the experiments show that in practice the quality of the obtained solutions is close to optimal., This work has been supported by MINECO and FEDER funds under grant TIN2017-86727-C2-1-R., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Automatic safe data reuse detection for the WCET analysis of systems with data caches

  • Segarra Flor, Juan
  • Cortadella, Jordi
  • Gran Tejero, Rubén
  • Viñals Yúfera, Victor
Worst-case execution time (WCET) analysis of systems with data caches is one of the key challenges in real-time systems. Caches exploit the inherent reuse properties of programs, temporarily storing certain memory contents near the processor, in order that further accesses to such contents do not require costly memory transfers. Current worst-case data cache analysis methods focus on specific cache organizations (LRU, locked, ACDC, etc.). In this article, we analyze data reuse (in the worst case) as a property of the program, and thus independent of the data cache. Our analysis method uses Abstract Interpretation on the compiled program to extract, for each static load/store instruction, a linear expression for the address pattern of its data accesses, according to the Loop Nest Data Reuse Theory. Each data access expression is compared to that of prior (dominant) memory instructions to verify whether it presents a guaranteed reuse. Our proposal manages references to scalars, arrays, and non-linear accesses, provides both temporal and spatial reuse information, and does not require the exploration of explicit data access sequences. As a proof of concept we analyze the TACLeBench benchmark suite, showing that most loads/stores present data reuse, and how compiler optimizations affect it. Using a simple hit/miss estimation on our reuse results, the time devoted to data accesses in the worst case is reduced to 27% compared to an always-miss system, equivalent to a data hit ratio of 81%. With compiler optimization, such time is reduced to 6.5%., This work was supported in part by MINECO/AEI/ERDF (EU) under Grant TIN2016-76635-C2-1-R, Grant TIN2017-86727-C2-1-R, and Grant PID2019-105660RB-C21; in part by the Aragón Government under Grant T58_20R research group; in part by the Generalitat de Catalunya under Grant 2017 SGR 786 and Grant FI-DGR 2015; and in part by the Construyendo Europa desde Aragón under Grant ERDF 2014-2020., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Refining the imprecise meaning of non-determinism in the Web by strategic games

  • Castro Rabal, Jorge
  • Gabarró Vallès, Joaquim
  • Serna Iglesias, María José
Nowadays interactions with the World Wide Web are ubiquitous. Users interact through a number of steps consisting of site calls and handling results that can be automatized as orchestrations. Orchestration results have an inherent degree of uncertainty due to incomplete Web knowledge and orchestration semantics are characterized in terms of imprecise probabilistic choices. We consider two aspects in this imprecise semantic characterization. First, when local knowledge (even imprecise) of some part of the Web increases, this knowledge goes smoothly through the whole orchestration. We deal formally with this aspect introducing orchestration refinements. Second, we analyze refinement under uncertainty in the case of parallel composition. Uncertain knowledge is modeled by an uncertainty profile. Such profiles allow us to look at the uncertainty through a zero-sum game, called angel/daemon-game. We propose to use the structure of the Nash equilibria to refine uncertainty. In this case the information improves not through cooperation but through the angel and daemon competition., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Learning random points from geometric graphs or orderings

  • Díaz Cort, Josep
  • Mcdiarmid, Colin
  • Mitsche, Dieter
Let Xv for v∈V be a family of n iid uniform points in the square (Formula presented.). Suppose first that we are given the random geometric graph (Formula presented.), where vertices u and v are adjacent when the Euclidean distance dE(Xu,Xv) is at most r. Let n3/14≪r≪n1/2. Given G (without geometric information), in polynomial time we can with high probability approximately reconstruct the hidden embedding, in the sense that “up to symmetries,” for each vertex v we find a point within distance about r of Xv; that is, we find an embedding with “displacement” at most about r. Now suppose that, instead of G we are given, for each vertex v, the ordering of the other vertices by increasing Euclidean distance from v. Then, with high probability, in polynomial time we can find an embedding with displacement (Formula presented.)., This research was supported by the grants GRAMM, TIN2017-86727-C2-1-R (J.D.), and by IDEXLYON of Université de Lyon (Programme Investissements d’Avenir, ANR16-IDEX-0005), and by LABEXMILYON (ANR-10-LABX-0070) of Université de Lyon, within the program “Investissements d’Avenir” (ANR-11-IDEX-0007) (D.M.), Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Business process variant analysis based on mutual fingerprints of event logs

  • Taymouri, Farbod
  • La Rosa, Marcello
  • Carmona Vargas, Josep
Comparing business process variants using event logs is a common use case in process mining. Existing techniques for process variant analysis detect statistically-significant differences between variants at the level of individual entities (such as process activities) and their relationships (e.g. directly-follows relations between activities). This may lead to a proliferation of differences due to the low level of granularity in which such differences are captured. This paper presents a novel approach to detect statistically-significant differences between variants at the level of entire process traces (i.e. sequences of directly-follows relations). The cornerstone of this approach is a technique to learn a directly-follows graph called mutual fingerprint from the event logs of the two variants. A mutual fingerprint is a lossless encoding of a set of traces and their duration using discrete wavelet transformation. This structure facilitates the understanding of statistical differences along the control-flow and performance dimensions. The approach has been evaluated using real-life event logs against two baselines. The results show that at a trace level, the baselines cannot always reveal the differences discovered by our approach, or can detect spurious differences., This research is partly funded by the Australian Research Council (DP180102839) and Spanish funds MINECO and FEDER (TIN2017-86727-C2-1-R)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Some results of Maria Serna on strategic games: Complexity of equilibria and models

  • Álvarez Faura, M. del Carme
  • Duch Brown, Amalia
We survey some recent work of Maria Serna concerning strategic games. We first examine some results related to the formal representation of strategic games and the complexity of problems related to both the existence of equilibria and the equivalence of games. These results provided a better understanding of how the succinctness of the game representation affects the complexity of such problems. We then describe some work dealing with the definition of new strategic games. The study of a Network Formation Game with asymmetric players, and the introduction of Celebrity Games as well as of Strategic Search Games intend to explain the natural behaviour of agents acting in some particular environments like communication networks, social networks, or even networks that contain valuable items hidden in different nodes., This work was partially supported by funds from the AGAUR, Spain of the Government of Catalonia under project ref. 2017 SGR 786 (ALBCOM), by the Spanish Ministry for Economy and Competitiveness (MINECO), Spain and by the European Union (FEDER funds), under grants ref. TIN2017-86727-C2-1-R., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Structural computation of alignments of business processes over partial orders

  • Taymouri, Farbod
  • Carmona Vargas, Josep
Relating event data and process models is becoming an important element for organizations. This paper presents a novel approach for aligning traces and process models. The approach is based on the structural theory of Petri nets (the marking equation), applied over an unfolding of the initial process model. Given an observed trace, the approach adopts an iterative optimization mechanism on top of the unfolding, computing at each iteration part of the resulting alignment. In contrast to the previous work that is primarily grounded in the marking equation, this approach is guaranteed to provide real solutions, and tries to mimic as much as possible the events observed in the trace. Experiments witness the significance of this approach both in quality and execution time perspectives., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Power to invest

  • Castro Rabal, Jorge
  • Gabarró Vallès, Joaquim
  • Serna Iglesias, María José
In this post recession time it is important to measure the possibilities offered by a society in relation to investments. To do that, we consider an investment schema I= (R;R_1,...,R_n) where R is a lower bound on the desired return and the R_i's are the return of the assets (to invest in). We introduce, Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Anti-alignments—Measuring the precision of process models and event logs

  • Chatain, Thomas
  • Boltenhagen, Mathilde
  • Carmona Vargas, Josep
Processes are a crucial artifact in organizations, since they coordinate the execution of activities so that products and services are provided. The use of models to analyze the underlying processes is a well-known practice. However, due to the complexity and continuous evolution of their processes, organizations need an effective way of analyzing the relation between processes and models. Conformance checking techniques assess the suitability of a process model in representing an underlying process, observed through a collection of real executions. One important metric in conformance checking is to assess the precision of the model with respect to the observed executions, i.e., characterize the ability of the model to produce behavior unrelated to the one observed. In this paper we present the notion of anti-alignment as a concept to help unveiling runs in the model that may deviate significantly from the observed behavior. Using anti-alignments, a new metric for precision is proposed. The proposed anti-alignment based precision metric satisfies most of the required axioms highlighted in a recent publication. Moreover, a complexity analysis of the problem of computing anti-alignments is provided, which sheds light into the practicability of using anti-alignment to estimate precision. Experiments are provided that witness the validity of the concepts introduced in this paper., This work has been partially supported by funds from ENS Paris-Saclay, Spain (project ProMAut of the Farman institute), the Spanish Ministry for Economy and Competitiveness (MINECO) and the European Union (FEDER funds) under grant GRAMM (TIN2017-86727-C2-1-R)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Robustness to voltage noise with ring oscillator clocks

  • Machado, Lucas
  • Roca Pérez, Antoni
  • Cortadella, Jordi
© 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes,creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works., Voltage noise is the main source of dynamic variability in integrated circuits and a major concern for the design of power delivery networks (PDNs). Lower supply voltages were made possible with technology scaling, but power density was also increased. Consequently, power integrity became a key factor in the design of reliable high performance circuits. Ring oscillators clocks (ROCs) have been proposed as an alternative to mitigate the negative effects of voltage noise. However, the effectiveness highly depends on the design parameters of the PDN, power consumption patterns, and spatial locality of the ROC within the clock domain. This paper analyzes the impact of the PDN parameters and ROC location on the voltage noise and the robustness achieved by using ROCs. The capability of reacting instantaneously to large voltage droops makes ROCs an attractive solution, which also allows to relax the constraints required for the PDN design. The experiments show that up to 83% of the margins for voltage noise and up to 27% of the total leakage power can be reduced by using ROCs. In addition, PDN simplifications are possible, with fewer power interconnections or package decoupling capacitors of lower quality. Tolerance to voltage noise and related benefits can be increased with multiple ROCs., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

State encoding of asynchronous controllers using pseudo-boolean optimization

  • Moreno Vega, Alberto
  • Cortadella, Jordi
State encoding of asynchronous controllers is a challenging problem that faces a vast space of solutions. Subtle differences in the insertion of signals may result in significant variations in the complexity of the logic. This paper proposes a novel approach that models the encoding problem as Pseudo-Boolean formula. A cost function that estimates the complexity of the logic is incorporated, where the estimator of essential literals becomes one of the most important terms of the function. The new approach has been tested in 175 benchmarks with encoding conflicts, including 127 four-phase latch controllers. The presence of logic estimators in the formula contributes to an average reduction of 43% in literals when compared to a plain SAT version of the problem, at the expense of a longer runtime. When comparing to the region-based approach in petrify, an average reduction of 14% in literals is obtained., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Measuring investment opportunities under uncertainty

  • Castro Rabal, Jorge
  • Gabarró Vallès, Joaquim
  • Serna Iglesias, María José
In order to make sound economic decisions it is important to measure the possibilities offered by a market in relation to investments. Provided an investment scheme S = (r; R1, . . . , Rn), where r is a lower bound on the desired investment return and the Ri’s are the asset yields, the power to invest measures the capability of the scheme to fulfill requirement r. The power to invest is inspired in the Coleman’s power of a collectivity to act. We exemplify this approach considering subsets of companies from stock indexes IBEX35 and DAX. We extend the power to invest to investment schemata with imprecise yields. We prove basic relations with the precise yields case and we also show that good monotonicity properties hold. Finally, we propose an analysis, through integrals of the power function, for the case of an unspecific desired return r., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

A biased random key genetic algorithm for the weighted independent domination problem

  • Rodríguez Corominas, Guillem
  • Blum, Christian
  • Blesa Aguilera, Maria Josep
This work deals with an NP-hard problem in graphs known as the weighted independent domination problem. We propose a biased random key genetic algorithm for solving this problem. The most important part of the proposed algorithm is a decoder that translates any vector of real-values into valid solutions to the tackled problem. The experimental results, in comparison to a state-of-the-art population-based iterated greedy algorithm from the literature, show that our proposed approach has advantages over the state-of-the-art algorithm in the context of the more dense graphs in which edges have higher weights than vertices., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Incremental concurrent model synchronization using triple graph grammars

  • Orejas Valdés, Fernando
  • Pino Blanco, Elvira
  • Navarro Gómez, Marisa
In the context of software model-driven development, artifacts are specified by several models describing different aspects, e.g., different views, dynamic behavior, structure, distributed information, etc. Then, maintaining and repairing consistency of the whole specification are crucial issues if the models can be separately developed and updated. Model Synchronization is the process of restoring consistency after the update of one or several of the models. In the present work, we approach the case when conflicts may arise due to concurrently updating different models. Specifically, based on the Triple Graph Grammar approach, we propose an incremental algorithm CSynch for solving conflicts and repairing consistency. In addition, we identify and formalize when a synchronizing solution can be considered adequate and show that our procedure CSynch is sound and complete., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Dynamic pipelining of multidimensional range queries

  • Duch Brown, Amalia
  • Lugosi, Daniel
  • Pasarella Sánchez, Ana Edelmira
  • Zoltan Torres, Ana Cristina
The problem of evaluating orthogonal range queries efficiently has been studied widely in the data structures community. It has been common wisdom for several years that for queries containing more than 20% of the elements of the dataset a linear scanning of the data was the most efficient solution. In recent experimental works using modern hardware –with main memory and parallelism– the conclusion is that linear scan is preferable for almost every query configuration (even containing a 1% of the data). In this work we propose an alternative approach to evaluate multidimensional range queries based on the dynamic pipeline paradigm –using main memory and concurrency. Our aim is to prove that under this framework, it is possible to beat the performance of linear scanning by the one of hierarchical multidimensional data structures –such as kd trees, quad trees, Rtrees or similar., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Generalized alignment-based trace clustering of process behavior

  • Boltenhagen, Mathilde
  • Chatain, Thomas
  • Carmona Vargas, Josep
Process mining techniques use event logs containing real process executions in order to mine, align and extend process models. The partition of an event log into trace variants facilitates the understanding and analysis of traces, so it is a common pre-processing in process mining environments. Trace clustering automates this partition; traditionally it has been applied without taking into consideration the availability of a process model. In this paper we extend our previous work on process model based trace clustering, by allowing cluster centroids to have a complex structure, that can range from a partial order, down to a subnet of the initial process model. This way, the new clustering framework presented in this paper is able to cluster together traces that are distant only due to concurrency or loop constructs in process models. We show the complexity analysis of the different instantiations of the trace clustering framework, and have implemented it in a prototype tool that has been tested on different datasets., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Empowering conformance checking using Big Data through horizontal decomposition

  • Valencia Parra, Álvaro
  • Varela Vaca, Ángel Jesús
  • Gómez López, María Teresa
  • Carmona Vargas, Josep
  • Bergenthum, Robin
Conformance checking unleashes the full power of process mining: techniques from this discipline enable the analysis of the quality of a process model through the discovery of event data, the identification of potential deviations, and the projection of real traces onto process models. In this way, the insights gained from the available event data can be transferred to a richer conceptual level, amenable for human interpretation. Unfortunately, most of the aforementioned functionalities are grounded in an extremely difficult fundamental problem: given an observed trace and a process model, find the model trace that most closely resembles to the trace observed. This paper presents an architecture that supports the creation and distribution of alignment subproblems based on an innovative horizontal acyclic model decomposition, disengaged from the conformance checking algorithm applied for their solution. This is supported by a Big Data infrastructure that facilitates the customised distribution of a gross amount of data. Experiments are provided that testify to the enormous potential of the architecture proposed, thereby opening the door to further research in several directions., This work has been partially funded by the Ministry of Science and Technology of Spain ECLIPSE (RTI2018-094283-B-C33) project, the European Regional Development Fund (ERDF/FEDER), MINECO (TIN2017-86727-C2-1-R), and by the University of Seville with VI Plan Propio de Investigación y Transferencia (VI PPIT-US)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Bridging the gap between energy consumption and distribution through non-technical loss detection

  • Coma Puig, Bernat
  • Carmona Vargas, Josep
The application of Artificial Intelligence techniques in industry equips companies with new essential tools to improve their principal processes. This is especially true for energy companies, as they have the opportunity, thanks to the modernization of their installations, to exploit a large amount of data with smart algorithms. In this work we explore the possibilities that exist in the implementation of Machine-Learning techniques for the detection of Non-Technical Losses in customers. The analysis is based on the work done in collaboration with an international energy distribution company. We report on how the success in detecting Non-Technical Losses can help the company to better control the energy provided to their customers, avoiding a misuse and hence improving the sustainability of the service that the company provides., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Optimized SAT encoding of conformance checking artefacts

  • Boltenhagen, Mathilde
  • Chatain, Thomas
  • Carmona Vargas, Josep
Conformance checking is a growing discipline that aims at assisting organizations in monitoring their processes. On its core, conformance checking relies on the computation of particular artefacts which enable reasoning on the relation between observed and modeled behavior. It is widely acknowledge that the computation of these artifacts is the lion’s share of conformance checking techniques. This paper shows how important conformance artefacts like alignments, anti-alignments or multi-alignments, defined over the Levenshtein edit distance, can be efficiently computed by encoding the problem as an optimized SAT instance. From a general perspective, the work advocates for a unified family of techniques that can compute conformance artefacts in the same way. The implementation of the techniques presented in this paper show capabilities for dealing with both synthetic and real-life instances, which may open the door for a fresh way of applying conformance checking in the near future., This work has been supported by Farman institute at ENS Paris-Saclay and by MINECO and FEDER funds under Grant TIN2017-86727-C2-1-R., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Maria Serna’s contributions to adversarial queuing theory

  • Blesa Aguilera, Maria Josep
  • Fernández Anta, Antonio
Adversarial Queuing Theory (aqt) is one of the areas to which Maria Serna has deeply contributed in her scientific career. Most of her research in this area took place during the lustrum 2001–2005, while advising the Ph.D. of Maria J. Blesa (2006) [1], and also in conjunction with other researchers. aqt is an adversarial model for the study of packet-switching communication networks under worst case conditions. In this model a fundamental concept is that of stability of a combination of network and packet scheduling protocol in front of an adversary that controls the arrival of packets. There is stability if the adversary cannot cause the number of packets in the network to grow unbounded. Maria’s contributions, summarized in this document, include results in the stability of networks and protocols, and the definition and study of aqt models with important new characteristics, like priorities, failures, or networks with different bandwidths and packet lengths. These results keep impacting the new research currently done in the aqt model., This research has been partially supported by the Agency for Management of University and Research Grants (AGAUR) of the Government of Catalonia under project 2017 SGR 786 (ALBCOM) and by MINECO and FEDER funds under grant GRAMM (ref. TIN2017-86727-C2-1-R)., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Conformance checking in UML artifact-centric business process models

  • Estañol Lamarca, Montserrat
  • Muñoz Gama, Jorge
  • Carmona Vargas, Josep
  • Teniente López, Ernest
Business artifacts have appeared as a new paradigm to capture the information required for the complete execution and reasoning of a business process. Likewise, conformance checking is gaining popularity as a crucial technique that enables evaluating whether recorded executions of a process match its corresponding model. In this paper, conformance checking techniques are incorporated into a general framework to specify business artifacts. By relying on the expressive power of an artifact-centric specification, BAUML, which combines UML state and activity diagrams (among others), the problem of conformance checking can be mapped into the Petri net formalism and its results be explained in terms of the original artifact-centric specification. In contrast to most existing approaches, ours incorporates data constraints into the Petri nets, thus achieving conformance results which are more precise. We have also implemented a plug-in, within the ProM framework, which is able to translate a BAUML into a Petri net to perform conformance checking. This shows the feasibility of our approach., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

A quality control method for fraud detection on utility customers without an active contract

  • Coma Puig, Bernat
  • Carmona Vargas, Josep
Fraud detection in energy consumption has proven to be a difficult problem for current techniques. In general, the approaches used in this area are restricted to compute a fraud score for each client based on its behaviour. The problem gets much more complicated on customers with no contract, since the company does not have enough information from them to compute an accurate profile. On this paper, we introduce a semi-autonomous method that combines different machine learning algorithms and human knowledge to alleviate the lack of information to build a framework that detects fraud nimbly., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Approximate computation of alignments of business processes through relaxation labelling

  • Padró, Lluís
  • Carmona Vargas, Josep
A fundamental problem in conformance checking is aligning event data with process models. Unfortunately, existing techniques for this task are either complex, or can only be applicable to restricted classes of models. This in practice means that for large inputs, current techniques often fail to produce a result. In this paper we propose a method to approximate alignments for unconstrained process models, which relies on the use of relaxation labelling techniques on top of a partial order representation of the process model. The implementation on the proposed technique achieves a speed-up of several orders of magnitude with respect to the approaches in the literature (either optimal or approximate), often with a reasonable trade-off on the cost of the obtained alignment., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

State-based encoding of large asynchronous controllers

  • Martínez Moreno, Albert
  • Cortadella, Jordi
State encoding is one of the fundamental problems in the synthesis of asynchronous controllers. The requirement for a correct hazard-free implementation imposes severe constraints on the way encoding signals can be inserted in the specification of a controller. Even though some specification formalisms, such as Burst-mode machines or Signal Transition Graphs, enable to specify behaviors at the event level, the state encoding methods that provide the best good-quality solutions work at the state level. This imposes a severe limitation on the size of the controllers that can be handled by these methods. This paper proposes a method to solve the encoding problem for large asynchronous controllers using statebased methods. It is based on an iterative process of projection and re-composition that reduces the size specification by hiding signals, partially solves the encoding problem at the state level and re-composes the original specification using a synchronous product. The process iterates until all encoding conflicts have been solved. The method is proved to preserve the behavior of the specification (branching bisimilarity) and shown to be capable of providing good-quality solutions for controllers of more than 100 signals and 106 states., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Online conformance checking using behavioural patterns

  • Burattin, Andrea
  • Zelst, Sebastiaan J. van
  • Armas Cervantes, Abel
  • Dongen, Boudewijn F. van
  • Carmona Vargas, Josep
New and compelling regulations (e.g., the GDPR in Europe) impose tremendous pressure on organizations, in order to adhere to standard procedures, processes, and practices. The field of conformance checking aims to quantify the extent to which the execution of a process, captured within recorded corresponding event data, conforms to a given reference process model. Existing techniques assume a post-mortem scenario, i.e. they detect deviations based on complete executions of the process. This limits their applicability in an online setting. In such context, we aim to detect deviations online (i.e., in-vivo), in order to provide recovery possibilities before the execution of a process instance is completed. Also, current techniques assume cases to start from the initial stage of the process, whereas this assumption is not feasible in online settings. In this paper, we present a generic framework for online conformance checking, in which the underlying process is represented in terms of behavioural patterns and no assumption on the starting point of cases is needed. We instantiate the framework on the basis of Petri nets, with an accompanying new unfolding technique. The approach is implemented in the process mining tool ProM, and evaluated by means of several experiments including a stress-test and a comparison with a similar technique., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On the PoA conjecture: Trees versus biconnected components

  • Álvarez Faura, M. del Carme
  • Messegué Buisan, Arnau
In the classical model of network creation games introduced by Fabrikant et al. [Ona network creation game, in Proceedings of the Twenty-Second Annual Symposium on Principlesof Distributed Computing (PODC`03), 2003, pp. 347--351],nplayers correspond to the nodes of anetwork buying links of price\alpha and to the other players with the goal of being well-connected tothe resulting network. Still as an open problem, theconstantPoAconjecturestates that thePriceof Anarchy(PoA) is constant for any\alpha . When tackling this problem distinct behaviors must betaken into the account depending on whether\alpha has either large or low value. It is known that for\alpha >4n - 13 everyneis a tree and for\alpha =O(n1 - \delta ) with\delta \geq 1/lognthe diameter of networks thatare in equilibrium when restricting to deviations that consist only in buying links (buying equilibria)is at most a constant. These results imply that the PoA is constant for the disjoint union of thetwo ranges, and thus the constant PoA conjecture seems to be true for most of all the possiblevalues\alpha . In this paper we study the PoA for the remaining range of\alpha and we show the following:(i) For\alpha > n(1 +\epsilon ) the PoA is constant by proving that the size of any biconnected componentof an equilibrium graph is constant. (ii) For\alpha \leq n(1 +\epsilon ) we have that PoA = \Theta (dmax), wheredmaxis the maximum diameter of an equilibrium graph for the same range of\alpha . Therefore if theconstant PoA conjecture was false, it would suffice to construct equilibria of nonconstant diameter.Towards this direction we find nontrivialbuying equilibriaof nonconstant diameter when\alpha > n1 - \delta and\delta =O(2 - \surd \mathrm{l}\mathrm{o}\mathrm{g}n), exploring new intimate relationships betweendistance-uniform graphsandbuying equilibria., This work was partially supported by funds from the Spanish Ministry for Economy and Competitiveness (MINECO) and the European Union (FEDER funds) under grant GRAMM (TIN2017-86727-C2-1-R), from the European Union-NextGenerationEU under Margarita Salas, from UPC grant 2021UPC-MS-66935, and from the Catalan Agency for Management of University and Research Grants (AGAUR, Generalitat de Catalunya) under project ALBCOM 2017-SGR-786., Peer Reviewed, Postprint (published version), This work is the extended version of the conference paper ``On the Price of Anarchy for High-Price Links"" from Web and Internet Economics 15thInternational Conference, WINE 2019, New York, NY, 2019, Proceedings.