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): 61
Encontrada(s) 1 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).
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 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 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 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 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 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 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 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 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 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 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 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 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
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 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 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 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 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 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 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 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 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 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 Contribución de congreso (ConferenceOutput)

Actionable conformance checking: from intuitions to code

  • Carmona Vargas, Josep
  • 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, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

On the price of anarchy for high-price links

  • Álvarez Faura, M. del Carme
  • Messegué Buisan, Arnau
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, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

The dynamic pipeline paradigm

  • Zoltán, Cristina
  • Pasarella Sánchez, Ana Edelmira
  • 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, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

RTL-aware dataflow-driven macro placement

  • Vidal Obiols, Alexandre
  • Cortadella, Jordi
  • Petit Silvestre, Jordi
  • 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, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

On bipartite sum basic equilibria

  • Álvarez Faura, M. del Carme
  • Messegué Buisan, Arnau
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, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
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
  • Carmona Vargas, Josep
  • Padró, Lluís
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, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
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
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, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

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

  • Martínez Parra, Conrado
  • 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, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Encoding conformance checking artefacts in SAT

  • Boltenhagen, Mathilde
  • Chatain, Thomas
  • Carmona Vargas, Josep
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, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

An evolutionary technique to approximate multiple optimal alignments

  • Taymouri, Farbod
  • Carmona Vargas, Josep
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, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Web apps and imprecise probabilities

  • Castro Rabal, Jorge
  • Gabarró Vallès, Joaquim
  • Serna Iglesias, María José
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, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

On list k-coloring convex bipartite graphs

  • Díaz Cort, Josep
  • Yasar Diner, Oznur
  • Serna Iglesias, María José
  • Serra Albó, Oriol
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, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

Extracting annotations from textual descriptions of processes

  • Quishpi Betún, Luis Hernán
  • Carmona Vargas, Josep
  • Padró, Lluís
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, Postprint (author's final draft)