Anna Kocurova
email: anna.kocurova@uwl.ac.uk

Samia Oussena
email: samia.oussena@uwl.ac.uk

Peter Komisarczuk
email: peter.komisarczuk@uwl.ac.uk

Tony Clark
email: t.n.clark@mdx.ac.uk

Dean Kramer
email: dean.kramer@uwl.ac.uk

Towards Distributed Collaborative Workflow Management for Mobile Devices

Keywords: Distributed workflow management system, context-awareness, content lifecycle, mobile collaboration

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The demand for an intelligent electronic environment which responds to people s needs is growing with worldwide proliferation of portable mobile electronic products. With mobile devices such as smartphones, tablets or PDAs becoming ubiquitous, people are more and more dependent on using mobile computing capabilities in everyday's life. The unique mobile's benefits are that the mobile devices are the always-on and always-carried mass media with ability to create and distribute content, take and upload a picture, capture an important event and publish the video in near real time [START_REF] Fling | Mobile Design and Development[END_REF]. People often want to share content or information privately by using mobile devices in various situations such as in business meetings. They expect to have tools to collaborate, share and publish content as required by the situation [START_REF] Erickson | Content-Centered Collaboration Spaces in the Cloud[END_REF].

Workflow management is a technology that can support collaboration and content sharing between participants in mobile settings. Mobile devices reside in extremely dynamic contexts. Frequent changes of user, device or environment state can influence behaviour of mobile information systems. Mobile workflow capabilities can be enhanced by making workflow systems more context-aware and adaptable to changing conditions. Context awareness might have a number of meanings, depending on the domain to which it is applied. We use the following definition of context [START_REF] Dey | A Conceptual Framework and A Toolkit For Supporting the Rapid Prototyping of Context-Aware Applications[END_REF]:

'Context is any information that can be used to characterize the situation of an entity. An entity is a person, place, or object that is considered relevant to the interaction between a user and an application, including the user and applications themselves. Context is typically the location, identity, and state of people, groups, and computational and physical objects.'

In this paper, context is mainly related to two workflow concepts: contentrelated context and context driven collaboration. The concepts are examined in details below.

Content-related context: Content shared by mobile devices differs from content circulated in traditional systems. Mobile content such as image, document or video/audio file is usually user-generated or adapted for use on mobile devices and can be context-aware. Context-aware content is content semantically enriched by context. For example, a picture is associated with information about the physical location or time when it was taken. Creating, processing and disposition of context-aware content are the basic stages of its lifecycle. However, content can flow through a more complex management process. The process might involve content editing, reviewing or publishing. In addition, context information associated with content can be changed at any time. The context change can trigger an action, cause content movement between two different states or influence content behaviour. In process-centric workflows, there is only a little support for recognition of context-aware content lifecycle. Integration of the lifecycle into workflows and extending mobile workflow management systems by additional context-aware content management functionalities can enhance content manipulation and sharing. In this paper, a context-aware content-centric approach with focus on key collaboration-related context-aware contents, their lifecycles and management is described.

Context driven collaboration: Content sharing between collaborators might be a costly operation in terms of transfer cost, devices resource usage and users time consumption, especially when task can be performed by a number of participants with the same role but not all of them can really accomplish it within a required time. Moreover, collaborators expect to have solutions for content sharing adapted for their current needs, preferences and situation. Collaboration driven by collaborator's current context can improve team work. However, the underlying management topology has a significant impact on the way how context can drive collaboration. In centralised workflow management approaches, management decisions are made by servers and context driven collaboration would be hardly achievable. In peer-to-peer (P2P) workflow management, management decisions are made by mobile devices. The decision can be based on local context-related information. By using the P2P management topology, workflows can become more context oriented processes adapted for collaborators needs.

The P2P management topology requires the development of a mobile distributed management system that consists of a set of mobile devices, connected through wireless links. High-speed wireless connections (Wi-Fi) and open wireless technology standards such as Bluetooth enable connection between devices in various environments. In P2P workflow management, data and content are exchanged directly; administration and responsibility for operations are distributed among the devices [START_REF] Stephanos | A survey of peer-to-peer content distribution technologies[END_REF]. No device has complete information about the workflow state. By using P2P management technology, communication processes can be accelerated and collaboration costs are reduced through the ad hoc administration of working groups [START_REF] Schoder | Peer-to-peer prospects[END_REF]. Moreover, each device can consider a variety of local information to determine what will happen next.

In this paper, a context-aware content-centric collaborative workflow tailored for mobile P2P collaboration is introduced and a reference framework for its definition, management and execution is elaborated. This framework can bring benefits to designers and developers of mobile collaborative applications who will be able to define own workflows according to their needs. In particular, the integration of a context-aware content-centric perspective into a workflow process is examined. Content behaviour is expressed by its lifecycle. The content lifecycle is composed of content states and transitions between content states. The transitions are driven by context guard conditions. A logical architecture of a workflow management system which is capable of executing such workflows is outlined.

The structure of the paper is as follows. Section 2 describes related work. The research methodology is highlighted in Section 3. A case study is described in Section 4. Context categorisation and management are presented in Section 5. Section 6 offers the definition of context-aware content-centric workflows. The logical architecture of the workflow management system is discussed in Section 7. The final section 8 summarizes the current research stage and results achieved so far.

Related Work

The need for adaptive workflow management demanded by practical situations is widely known and acknowledged. We review related work to workflow adaptation according to three categories: context-aware workflow modelling, context-aware workflow adaptation and artifact-centric workflow approaches.

Wieland et al. pointed out that workflow meta-models should support context modelling and its use in workflows [START_REF] Wieland | Towards Context-aware Workflows[END_REF]. Earlier works such as Context Toolkit [START_REF] Dey | A Conceptual Framework and A Toolkit For Supporting the Rapid Prototyping of Context-Aware Applications[END_REF] provided rather simple frameworks for context modelling. Later, more structured and complex frameworks that facilitate the development of context-aware applications were presented [START_REF] Henricksen | Developing context-aware pervasive computing applications: Models and approach[END_REF][START_REF] Reichle | A comprehensive context modeling framework for pervasive computing systems[END_REF][START_REF] Bardram | The Java Context Awareness Framework (JCAF)a service infrastructure and programming framework for context-aware applications[END_REF]. The frameworks address concepts of context management such as differentiation of lower-level raw context data from higherlevel derived context information, context aggregation and context querying. Recently with increased context data dissemination, shared global context models for context-aware applications in large-scale scenarios such as Nexus approach have been developed [START_REF] Grossmann | Efficiently managing context information for large-scale scenarios[END_REF]. However, we believe that a context modelling approach need to be customised and adapted for the problem it is applied to. In this paper, no new domain concept is introduced but a customised modularisation approach to context management is proposed.

Workflow contextualisation has been addressed in a number of works, however, there are many research challenges to make context-aware workflow systems ready for practical use. From the modelling perspective, COMPRO, a methodological approach for context-aware business process modelling and discovering relevant properties and variants has been developed [START_REF] Vara | COMPRO: A Methodological Approach for Business Process Contextualisation[END_REF]. A more role-driven process contextualisation and an explicit definition of the context related knowledge for adequate role-based business process modelling has been addressed in another work [START_REF] Saidani | Context-awareness for adequate business process modelling[END_REF]. The works offer methodological, general or abstract approaches for context awareness which are tailored to a wide spectrum of business processes. However, context awareness should be domain-related with focus on the execution environment. Thus we propose a contextualised workflow definition designed for mobile devices.

In early stages, adaptive workflows have been described as workflows able to deal with certain changes. Later, process flexibility has been seen as the ability to deal with foreseen and unforeseen changes and four types of flexibility have been recognised: flexibility by design, flexibility by deviation, flexibility by underspecification and flexibility by change [START_REF] Schonenberg | Process Flexibility: A Survey of Contemporary Approaches[END_REF]. Three objectives for contextaware workflow adaptation have been identified: customisation, correction and optimisation [START_REF] Smanchat | A survey on context-aware workflow adaptations[END_REF]. Process flexibility can be related to design time, configuration time, instantiation time or run time. No modification of process definition at build-time is needed in the case of the flexibility by selection (a priori), as opposed to the flexibility of adaptation (a posteriori) in which modification of the process definition or its instances at run-time is allowed [START_REF] Nurcan | A survey on the flexibility requirements related to business processes and modeling artifacts[END_REF]. It has been pointed out that despite to a large number of proposals for flexible workflow support, the workflow models are still composed of activities and flexibility is usually achieved by two specific approaches: allowing runtime deviations or minimalistic specification of flow dependencies [START_REF] Redding | A flexible, objectcentric approach for business process modelling[END_REF]. Various techniques for workflow flexibility have been designed. We do not propose another approach, rather we combine existing techniques in a specific way. Our objective is to customise workflows to user's needs with focus on workflow flexibility at run-time.

Context adaptation in a distributed collaborative execution environment is challenging because a context-aware data dissemination technique needs to be considered. Reachability, availability and roles of workflow participants are the factors that should be monitored. Ghayam et al. adopted a mobile agent paradigm and proposed a distributed solution for context management by using a decision tree-based approach [START_REF] El Ghayam | Distributed Context Management in Collaborative Environment[END_REF]. A notification-token mechanism for dynamic data dissemination for Vehicular Ad Hoc Networks (VANETs) is based on oppor-tunistic publish/subscribe system [START_REF] Lei | Dynamic distribution-aware data dissemination for Vehicular Ad Hoc Networks[END_REF]. However, the mechanisms are not entirely role-based. Importance how local mobility and context awareness can influence interactions among the hospital workers is shown in [START_REF] Mejia | Understanding and Supporting Lightweight Communication in Hospital Work[END_REF]. The work offers a conceptual insight and outlines the significance of the inquiry for context aware collaboration but lacks in providing more details.

Workflows have become complex and better solutions are needed to manage complexity and event-driven behaviour. Whilst process-centric models are still used for most workflows, a data-centric approach to workflows has become more popular. Focus on key business-relevant objects, their lifecycles and how services invoke on them has emerged [START_REF] Hull | Artifact-centric business process models: Brief survey of research results and challenges. On the Move to Meaningful Internet Systems[END_REF], howbeit, object-awareness in workflow processes is still very limited [START_REF] Künzle | PHILharmonicFlows: towards a framework for objectaware process management[END_REF][START_REF] Vanderfeesten | Product based workflow support: dynamic workflow execution[END_REF]. The duality of information-centric and activity-centric workflow models has been emphasised as a sophisticated solution for workflow management [START_REF] Kumaran | On the duality of information-centric and activitycentric models of business processes[END_REF]. Content integration is usually limited on the inputs and outputs of certain workflow activities, and impact on its content lifecycle would be neglected or hardly visible; therefore, a basis for an artifactcentric workflow model comprising four concepts has been proposed [START_REF] Bhattacharya | A data-centric design methodology for business processes[END_REF]. The four concepts are: business artifact information model, business artifact macrolevel lifecycle, services (tasks), and the association of services to business artifact. In our work, the aim is to integrate a context-aware content-centric perspective into the mobile collaborative workflow process in order to support content management and context-driven behaviour.

So, in summary, there is no existing mobile workflow approach for day-to-day collaborative activities that would support context-aware content manipulation, integrate a context-aware content lifecycle and operate in a P2P context driven manner. We present our conceptual framework that can be used to define, manage and execute mobile context-aware content-centric workflow processes.

Research Methodology

The objective of the paper is to introduce a conceptual reference framework. The framework outlines information needed for the mobile context-aware contentcentric workflow process definition, management and execution.

Firstly, we describe a case study to illustrate the use of the framework and targeted class of workflows. Secondly, context related to that class of workflows is determined. A modularisation approach to context management and aggregation is proposed. Thirdly, a workflow can be seen as an abstraction of real work. A workflow definition is basically an abstraction of phenomena in the real world and is used to create actual workflow operational instances. Workflow needs to be well defined because the success of a workflow management system is based on the quality of the workflow models put into it [START_REF] Aalst | Workflow Management: Models, Methods, and Systems[END_REF]. In this paper, we describe all constituents that form the context-aware content-centric workflows at a metamodel level. Finally, workflows are carried out by a mobile workflow management system. Therefore, we describe a logical architecture of the system.

The framework is expressed at a higher level of abstraction, therefore, it can be used as a tool for application domain experts who will be able to define the concrete workflow cases for a particular domain. The area of framework's application is exemplified in the following scenario.

Case Study

In this section, we present an example scenario to illustrate the motivation for utilising workflow management technology for mobile devices. The framework is tailored specifically to a certain class of workflows and this simplified scenario describes a particular workflow case that belongs to the class.

Consider a small business which focuses on residential and commercial interior design of houses, schools, offices, hotels and shops. Design projects are carried out by a team of six interior designers. Business success depends on close cooperation between designers and close collaboration with customers. Designers usually work out in the field and communicate with each other by using their smart phones. With mobile devices, designers can make important decisions right away, share images of design patterns with as little delay as possible.

Designers work on a number of concurrent projects. Although each project is assigned to a particular designer, design decisions are never done by a single person. Jane, as a specialist on private houses, has been assigned to a project to redesign a living room for a private client. The client wishes to optically enlarge the room by repositioning the furniture. In order to successfully complete the project, the following steps need to be taken:

1. Jane knows few tricks how to optically enlarge rooms so the furniture is repositioned according to her ideas. Jane takes a picture of the new room design by using her smart phone. 2. A simple rating system is used to quickly assess design ideas. Jane adds her own rating to the picture. 3. The picture is sent to her fellow co-workers. They work out in the field so receive the picture on their phones. Each of them can review the picture. 4. Reviewer's subjective opinion can be captured by adding a comment. 5. Reviews and comments are sent back to Jane. She finally reassesses her idea according to opinions of other designers. 6. If the idea is good, the picture is sent for final approval to client. 7. Approved picture is added to Jane's completed work.

From a user's point of view, the real pattern can be abstracted into a collaborative workflow as illustrated in the middle in Fig. 1.

It illustrates how a picture lifecycle can be integrated with the collaborative workflow and how the workflow can be context-driven. For example, context information about location and time are needed when the picture is taken. Latitude and longitude are coordinates that are usually captured as default by most mobile devices. However, high-level context information such as name of place or building might be more useful. Secondly, the picture goes through a number of states such as Initial, Reviewed, Assessed, Approved or Final. Jane can specify that only pictures with rating larger than her Rating User Preference can move from the Initial state to the Reviewed state. So if the Rating User Preference is set to 3 and the rating added to the picture is 4, then the picture can be sent for review. A similar situation is between the Reviewed and the Assessed states. The picture can move to the Assessed state only if a number of obtained reviews has reached Jane's requirement. Jane sets User Preference for no. of reviews to 2, so two reviews are needed for her to assess the picture. Finally, sending the picture only to reviewers who are currently available would make content sharing more efficient (Reviewer's Availability = YES ).

Context

Context Categorisation

People use mobile devices in a more personalised way and mobile information systems need to be more customisable and adaptable to user behaviour and needs. Personalisation and adaptation of information systems is usually accomplished by considering additional information about user, for example, by including more detailed information based on personal preferences [START_REF] Bierig | Event and map content personalisation in a mobile and context-awareenvironment[END_REF]. Using user preferences in the workflow concept can lead to more flexible and dynamic workflow structures that can respond to collaborators' needs.

Secondly, smart mobile phones are capable of capturing various types of contextual information. Context information can be related to the context of device or environment. Connectivity and battery level are examples of device's context. Environmental context might be time, location or information about surrounding devices. Finally, significant context to establish cooperative effort is social context. Social context awareness relies on knowing the work context of fellow collaborators, such as their availability, current activity and location [START_REF] Bardram | The AWARE Architecture: Supporting Contextmediated Social Awareness in Mobile Cooperation[END_REF].

Fig. 2. Context Categorisation for the Framework

Context categorisation considered in the framework is shown in Fig. 2. We assume that whilst environmental and device's context information can influence overall workflow execution, coordinated social context-dependent workflow activities can effectively mediate the constraints of content sharing between workflow participants.

Context Management

Context management itself is not a trivial concept. We have separated context acquisition and aggregation from context adaptation. Whilst context adaptation can be considered workflow specific, context acquisition and aggregation can be workflow independent. Therefore, context acquisition and aggregation can be handled by a generic standalone mechanism that monitors, manages, aggregates and disseminates contextual information to a workflow management system and other systems running on the same mobile device. Describing the mechanism is out of scope of the paper but can be found in our previous work [START_REF] Kramer | An Extensible, Self Contained, Layered Approach to Context Acquisition[END_REF]. In the mechanism, context is described by its name and is associated with a finite set of context values. For example, context values for Bluetooth state are {ON, OFF }. In case of numeric data, high level context values are derived from raw values, e.g. if battery level is between 0 -10%, its context value is defined as LOW. Context values for Battery level can be defined as {LOW, MEDIUM, FULL}. High-level context values can be defined by user. Context information is broadcasted in a unified form as a (KEY-VALUE) pair.

Context Aggregation

Context aggregation is not a new concept in the research field. This section describes its accommodation in this framework by illustrating the following examples (Fig. 3). These examples of context aggregations are illustrative and the context aggregation hierarchy can be uniquely defined for each workflow case as shown later.

6 Context-Aware Content-Centric Workflow Process Definition This section describes a context-aware content-centric workflow process definition designed for mobile P2P workflows. The anatomy of the workflow definition is depicted in Fig. 4. The workflow definition is composed of a roleindependent part which is same for all workflow participants and a role-specific part which needs to be explicitly defined for each participating role. The parts are in details described in the remainder of this section.

Role-Independent Part

The role-independent part of the workflow definition includes a list of roles, collaborators, and content lifecycles. These workflow constituents are same for all participants. Roles/Collaborators: In collaborative workflows, tasks are performed by collaborators. In this concept, workflow collaborator is a person who uses a mobile device to collaborate, share content and communicate with other team members in order to achieve a common goal. Each collaborator has a mobile device which is identifiable by its phone number, Wi-Fi and Bluetooth MAC addresses (assuming that SIM card is not changed). In order to execute workflows, the participating devices are aware of other fellow devices and their identifiable elements. A list of participating collaborators and their devices is predefined and available on each device. The workflow definition includes a set of collaborators as shown in Fig. 5.

Fig. 6. Roles

A collaborator can play a number of roles in various workflow processes. For instance, Jane with the role of Interior Designer takes a picture and creates a workflow instance. In the meanwhile, another team member can take a picture that needs to be reviewed by Jane and creates another workflow instance. Jane will have a role of Reviewer in the coexisting workflow instance. Our workflow definition includes a list of roles. Each role is associated with a certain group of collaborators who can play the role (Fig. 6).

Content Lifecycle: A number of content pieces can be managed in a workflow. A set of states that each content moves through is described by a content lifecycle (Fig. 7). Transitions between a source and a target content state are associated with conditions. A condition depends on particular context. By using this structure, content management and behaviour can be context driven. A content lifecycle describes content processing across multiple mobile devices.

Role-Specific Parts

The workflow definition includes a number of role-specific parts specified for each participating role. A role-specific part in the workflow definition is defined for each participating role and comprises three levels: process level, context definition level and context adaptation level. The process level contains a standard workflow process definition. We use the Business Process Execution Language (BPEL) to describe our workflow processes but any workflow executable language can be used. Describing the process level in details is out of scope of the paper.

Context Definition: Context is described by its name, type and a context values set as shown in Fig. 8. For example, context can have name: Status, type: User Preference and context values set: {Busy, Available, Not Set}. However, in certain cases, only raw context data are obtained from context sources and high level context values need to be derived. We use Values Descriptor to associate high context values with raw data. Two examples: Range and Coordinates are outlined. For instance, LOW as a high-level context value for battery can be defined for a range: 0 to 10%. Composite context, dedicated for context aggregation, is designed as a context container that inherits all constructs of context. The role of the context definition constituent is to specify all atomic and aggregated contexts which influence workflow behaviour. Corresponding context values sets can be also identified. Using this constituent, context structures and hierarchies can be modelled.

Context Adaptation: As mentioned, often only aggregated context values influence behaviour of workflows. We call contexts which influence workflow execution as active contexts. We defined four active context types: content context, communication context, user and collaborator context ( Fig. 9). Content context specifies context associated with content and its lifecycle. Communication Context Adaptation-Content Context: Integration of content lifecycles with a particular workflow process is done by specifying content aware activities. A content-aware activity is a special type of a workflow activity. It processes content according to an action and changes its content state (Fig. 10).

Workflow Management

The context-aware content-centric workflows are interpreted and carried out by a system that needs to be deployed on each participating device. The system is based on cooperation between a mobile workflow management system and a [START_REF] Hollinsworth | The Workflow Reference Model[END_REF], is outlined in Fig. 11. In the remainder of this section, we describe its logical architecture and key components.

Context Provisioning Layer

A context provisioning engine is built upon the context acquisition and aggregation mechanism. As mentioned, the details about the mechanism can be found in our previous work. The engine interprets the context definition part of workflow and operates as a context provisioning platform. The context engine supports asynchronous and synchronous communication. If a context change occurs, it is broadcasted to all listening systems and applications. On the other hand, other systems and applications can query context values at any time. A prototype of the context provisioning engine is being developed on the Android platform and is available as an open source software1 .

Workflow Management System

Fig. 12. The Architectural Model A workflow management system needs to be deployed on each participating device. This section offers a logical architectural overview of the system. Describing the details of its run-time architecture is out of scope of the paper. P2P workflow management is more complex, therefore, key components grouping semantically related functions and data have been identified. The independent but interoperable components of the mobile distributed workflow management system are shown in Fig. 12. The system needs to detect, consume, and react to context events. To cope with context events, the architecture is based on an event-driven architecture pattern.

Context Handler: Interaction with the context provisioning layer is ensured by a context handler. The handler supports synchronous and asynchronous communication. The synchronous communication mechanism enables real-time interaction and context querying. Asynchronous communication is achieved by using a listener. The listener receives messages broadcasted by the context engine.

Context Adaptation: The component processes the received context messages further. Its role is to provide a run-time context adaptation support to all dependent components. Data and Content Management Layer: In P2P workflow management, each device needs to administer the following data and content sets: Data Management: Most likely a mobile device will participate in a reasonable number of small-scaled workflow processes. Workflow definitions are pre-loaded on each device. As outlined, a workflow consists from a roleindependent part which has to be deployed to all participating devices and a role-based part which is deployed only to the devices assigned to the role. Each workflow can have more operational instances running at the same time. In P2P collaboration, each device executes only an allocated partition of the workflow. Each device persists operational, instance and control data. Content Provider: Sharing and manipulating of mobile content becomes a part of workflow execution. To prevent content duplication on a single device, content is stored in a read-only mode in a mobile s default file system. This ensures that content can be seen by user at any time but cannot be modified.

Only the content provider can encapsulate contents and manage access to them. Content Lifecycle State Machine: A state machine is used to interpret a content lifecycle part of workflow and manages the content lifecycle. Content Integration: Extended management functionalities for context-aware content are provided. Content-related context information is associated with content.

Event Handler: This component handles incoming text/media messages or events triggered by user.

Workflow Engine: The mobile workflow management system needs to be based on a good execution engine. Havey recommends the adoption of the Business Process Execution Language (BPEL) [START_REF] Havey | Essential business process modeling[END_REF]. A workflow execution engine interprets workflow process definitions, instantiate them and provides logistic facilities for their completion. An existing mobile BPEL workflow engine called Sliver has been adapted [START_REF]Sliver -A SOAP and BPEL execution engine for mobile devices[END_REF]. Adding context awareness means that the engine must react on context changes and act upon them. This component must be flexible in order to enable realization of workflow modifications.

Distribution Manager: Distribution Manager is a component that manages collaboration between participants and dissemination of data and content. It functions as a task allocation manager and scheduler, therefore, it makes decisions what content and data need to be sent and when to send it.

Identity Management: In general, certain tasks within the process can be performed only by collaborators with a specified role. A list of collaborators is available on each device. This component interprets roles/collaborators part of workflow and provides access management to information about workflow participants.

The data structure includes the following fields:

enum State -identifies the workflow state: NEW -informing about a new process instance; RUNNING -indicating that the message is related to an existing instance; END -informing about termination of an instance; enum DataType -specifies a type of data attached to the message: CONTEXT -context data such as location or time; CONTROL -data that drives the correct execution of decentralized workflow; VARIABLE -inputs or outputs of the tasks; processInstanceID and processID -unique identifiers of process and process instance; senderPhoneID -identifies the sender of the message; contentName and contentType -are optional. If a piece of content is shared between devices, these fields are filled with corresponding information about content name and its type like picture, video etc.; workflowData -data associated with the message; the 'repeated' word indicates that more than one workflowData can be added; message Data -determines the structure of workflowData; message TaskDataCollection -allows packing of more than one TaskData within one message.

Communication middleware is used to exchange messages between mobile devices. It needs to support various communication protocols for information passing and content sharing over Wi-Fi, Bluetooth or by using SMS/MMS. However, communication middleware is not part of the workflow management system. The mobile workflow management systemuses only services provided by communication middleware.

Conclusion

This paper presents a conceptual reference framework for definition, management and execution of mobile context-aware content-centric collaborative workflows. The workflow definition has been specified in a form of metamodel. The logical architecture of the workflow management system has been described.

The development of the framework is in progress. As a proof of concept that the theory is functional, a realistic artifact is being developed on the Android platform. Its run-time architecture will be described in our future work.

The integration of content lifecycles with a workflow process presented in this work has been only an initial step towards more advanced content integration. In our future work, our aim is to extend the workflow process in the following way. The workflow process should be capable of reacting on particular changes in content lifecycles in two ways. Firstly, querying of a content lifecycle should be supported at specific places in the workflow process. Based on the obtained current content state, decisions should be made. Secondly, certain activities in the workflow process should be able to register their interest and act only when content reaches a required content state.

Fig. 1 .

 1 Fig. 1. Collaborative Workflow Case

Fig. 3 .

 3 Fig. 3. Examples of Context Aggregation

Fig. 4 .

 4 Fig. 4. Anatomy of the workflow definition

Fig. 5 .

 5 Fig. 5. Collaborators

Fig. 7 .

 7 Fig. 7. Content Lifecycles

Fig. 8 .Fig. 9 .

 89 Fig. 8. Context Definition

Fig. 10 .Fig. 11 .

 1011 Fig. 10. Content Activities

https://github.com/deankramer/ContextEngine

Communication Manager: Communication manager cooperates with the distribution manager and communication middleware. Its role is to define a preferred communication method between mobile devices and decide how content or data should be sent.

The manager contains a mechanism to serialise and deserialise data. A mechanism for serializing structured data has been created by using Protocol Buffers -Google's data interchange format. By using Protocol Buffers, structured data are encoded in an efficient, language-neutral and platform-neutral format. The data structure for the workflow management system has been identified in the .proto file as shown in Listing 1.


Wil Van Der Aalst

Joos Buijs

Boudewijn Van Dongen
email: v.dongen@tue.nl

J C A M Aalst

B F Buijs

Towards Improving the Representational Bias of Process Mining

Process mining techniques are able to extract knowledge from event logs commonly available in today's information systems. These techniques provide new means to discover, monitor, and improve processes in a variety of application domains. Process discoverydiscovering a process model from example behavior recorded in an event log-is one of the most challenging tasks in process mining. A variety of process discovery techniques have been proposed. Most techniques suffer from the problem that often the discovered model is internally inconsistent (i.e., the model has deadlocks, livelocks or other behavioral anomalies). This suggests that the search space should be limited to sound models. In this paper, we propose a tree representation that ensures soundness. We evaluate the impact of the search space reduction by implementing a simple genetic algorithm that discovers such process trees. Although the result can be translated to conventional languages, we ensure the internal consistency of the resulting model while mining, thus reducing the search space and allowing for more efficient algorithms.

Introduction

More and more events are being recorded. Over the last decade we have witnessed an exponential growth of event data. Information systems already record lots of transactional data. Moreover, in the near future an increasing number of devices will be connected to the internet and products will be monitored using sensors and RFID tags. At the same time, organizations are required to improve their processes (reduce costs and response times) while ensuring compliance with respect to a variety of rules. Process mining techniques can help organizations facing such challenges by exploiting hidden knowledge in event logs. Process mining is an emerging research discipline that provides techniques to discover, monitor and improve processes based on event data [START_REF] Van Der Aalst | Process Mining: Discovery, Conformance and Enhancement of Business Processes[END_REF].

Starting point for process mining is an event log. All process mining techniques assume that it is possible to sequentially record events such that each event refers to an activity (i.e., a well-defined step in the process) and is related to a particular case (i.e., a process instance). Event logs may store additional information such as the resource (i.e., person or device) executing or initiating an activity, the timestamp of an event, or data elements recorded with an event (e.g., the size of an order). We often distinguish three main types of process mining:

-Discovery: take an event log and produce a model without using any other apriori information. There are dozens of techniques to extract a process model from raw event data. For example, the classical α algorithm is able to discover a Petri net by identifying basic process patterns in an event log [START_REF] Van Der Aalst | Workflow Mining: Discovering Process Models from Event Logs[END_REF]. For many organizations it is surprising to see that existing techniques are indeed able to discover real processes based on merely example executions recorded in event logs. Process discovery is often used as a starting point for other types of analysis. -Conformance: an existing process model is compared with an event log of the same process. The comparison shows where the real process deviates from the modeled process. Moreover, it is possible to quantify the level of conformance and differences can be diagnosed. Conformance checking can be used to check whether reality, as recorded in the log, conforms to the model and vice versa.

There are various applications for this (compliance checking, auditing, sixsigma, etc.) [START_REF] Rozinat | Conformance Checking of Processes Based on Monitoring Real Behavior[END_REF]. -Enhancement : take an event log and process model and extend or improve the model using the observed events. Whereas conformance checking measures the alignment between model and reality, this third type of process mining aims at changing or extending the a-priori model. For instance, by using timestamps in the event log one can extend the model to show bottlenecks, service levels, throughput times, and frequencies [START_REF] Van Der Aalst | Process Mining: Discovery, Conformance and Enhancement of Business Processes[END_REF].

In this paper we focus on process discovery. However, we would like to stress that process discovery is only the starting point for other types of analysis. After linking events to process model elements it becomes possible to check conformance, analyze bottlenecks, predict delays, and recommend actions to minimize the expected flow time.

To illustrate the notion of process discovery see Fig. 1(a-b). Based on the event log shown in Fig. 1(a), we can discover the Petri net shown in Fig. 1(b). For simplicity we use a rather abstract description of the event log: process instances are represented by sequences of activity names (traces). For example, there are 42 cases that followed trace abce, 38 cases that followed trace acbe, and 20 cases that followed trace ade. This small event log consists of 380 events describing 100 process instances. There are 80 events corresponding to the execution of activity b. Here we abstract from additional information such as the person executing or initiating an activity, the timestamp of an event, and associated data elements. The Petri net shown in Fig. 1(b) describes a process model able to explain the observed behavior.

Process discovery can be seen as a search process, i.e., given an event log search for the model that describes the observed behavior best. When using Petri nets to describe process models, the search space consists of all possible Petri nets. However, even when we discard the event log, we can identify Petri nets that are clearly undesirable. Figure 1(c-d the state with just a token in place p2 . Transition e is not enabled because there have to be tokens in both input places (p2 and p3 ) in order for e to occur. Hence, N 2 gets "stuck" after executing the partial trace ab. A similar deadlock is encountered after executing ac. Only after executing partial trace ad, transition e becomes enabled and the process can successfully terminate with a token in end . N 3 in Fig. 1(d) has another problem. It is possible to execute trace abe that puts a token in place end . However, a token is left in p2 . Although the process seems to have completed (token in end ), it is still possible to execute c. Whereas N 2 was unable to replay the event log in Fig. 1(a), N 3 is able to replay the event log but 80 of the 100 cases do not reach the desired final state with just a token in place end .

The anomalies illustrated by N 2 and N 3 in Fig. 1(c-d) are not specific for Petri nets. Any of the main business process modeling languages (EPC, BPMN, UML, YAWL, etc.) [START_REF] Weske | Business Process Management: Concepts, Languages, Architectures[END_REF] allows for deadlocks, livelocks, and improper termination. These anomalies exist independent of the event log, e.g., the event log is not needed to see that N 2 has a deadlock. Nevertheless, most process discovery techniques consider such incorrect models as possible candidates. This means that the search space is composed of both correct and incorrect models. It is not easy to limit the search space to only correct models. For common notations such as Petri nets, EPCs, BPMN, UML activity diagrams, and YAWL models it is only possible to check correctness afterwards. Note that deadlocks and livelocks are non-local properties. Hence, simple syntactical correctness-preserving restrictions are not possible without severely crippling expressiveness.

In earlier work, we used genetic algorithms to discover process models [START_REF] Van Der Aalst | Genetic Process Mining[END_REF][START_REF] Alves De Medeiros | Genetic Process Mining: An Experimental Evaluation[END_REF]. However, these algorithms suffered from the problem that the majority of process models considered during the search process has anomalies such as deadlocks, livelocks, and improper termination. Therefore, we propose to use process trees for process mining. Process trees such as the one shown in Fig. 1(e) cannot have any of the anomalies mentioned before (deadlocks, livelocks, etc.) as they are sound by design [START_REF] Kopp | The Difference Between Graph-Based and Block-Structured Business Process Modelling Languages[END_REF]. Process trees are discussed in more detail in Section 3. Using process trees as a new representational bias, we propose a new generation of genetic process discovery algorithms. By limiting the search space to process trees, we can improve the quality of the discovered results and speed up the search process.

The remainder of this paper is organized as follows. Section 2 elaborates on the importance of selecting the right representational bias. Section 3 formalizes the representational bias used in this paper and Section 5 introduces a new genetic algorithm. The first experimental results are presented in Section 6. Section 7 concludes the paper.

On the Representational Bias of Process Mining

In this section we discuss challenges related to process discovery and explain why an appropriate representational bias [START_REF] Van Der Aalst | On the Representational Bias in Process Mining (Keynote Paper)[END_REF] needs to be selected.

Process Discovery as a Search Problem

Starting point for process mining is an event log composed of individual events. Each event refers to a case (process instance). Events corresponding to a case are ordered. Therefore, a case can be described by a trace, i.e., a sequence of activity names. Recall that in this paper we abstract from attributes such as timestamps, resources and additional data elements, and focus on activity names only. Different cases may have the same trace. Therefore, an event log can be formalized as a multiset of traces (rather than a set). A denotes the set of activities that may be recorded in the log. σ ∈ A * is a trace, i.e., a sequence of events. L ∈ IB(A * ) is an event log, i.e., a multiset of traces. For example, the event log shown in Fig. 1(a) can be formalized as follows: L = [abce 42 , acbe 38 , ade 20 ]. Note that the trace abce appears 42 times in this event log.

A process discovery algorithm can be seen as a function f that, given an event log L, produces a model M , i.e., f ∈ IB(A * ) → M where M is the class of process models considered. M is the representational bias, i.e., the set of possible candidate models. For example, the α algorithm can be seen a function that produces Petri net N 1 shown in Fig. 1(a) based on event log L = [abce 42 , acbe 38 , ade 20 ]. In this example, the representational bias M is the class of Petri nets where all transitions have unique labels (there cannot be two transitions with the same label).

Since the mid-nineties several groups have been working on techniques for process mining [START_REF] Van Der Aalst | Business Process Mining: An Industrial Application[END_REF][START_REF] Van Der Aalst | Workflow Mining: Discovering Process Models from Event Logs[END_REF][START_REF] Agrawal | Mining Process Models from Workflow Logs[END_REF][START_REF] Cook | Discovering Models of Software Processes from Event-Based Data[END_REF][START_REF] Datta | Automating the Discovery of As-Is Business Process Models: Probabilistic and Algorithmic Approaches[END_REF][START_REF] Van Dongen | Multi-Phase Process Mining: Building Instance Graphs[END_REF][START_REF] Van Dongen | Multi-Phase Mining: Aggregating Instances Graphs into EPCs and Petri Nets[END_REF][START_REF] Weijters | Rediscovering Workflow Models from Event-Based Data using Little Thumb[END_REF], i.e., discovering process models based on observed events. In [START_REF] Van Der Aalst | Workflow Mining: A Survey of Issues and Approaches[END_REF] an overview is given of the early work in this domain. The idea to apply process mining in the context of workflow management systems was introduced in [START_REF] Agrawal | Mining Process Models from Workflow Logs[END_REF]. In parallel, Datta [START_REF] Datta | Automating the Discovery of As-Is Business Process Models: Probabilistic and Algorithmic Approaches[END_REF] looked at the discovery of business process models. Cook et al. investigated similar issues in the context of software engineering processes [START_REF] Cook | Discovering Models of Software Processes from Event-Based Data[END_REF]. Herbst [START_REF] Herbst | A Machine Learning Approach to Workflow Management[END_REF] was one of the first to tackle more complicated processes, e.g., processes containing duplicate tasks.

Most of the classical approaches have problems dealing with concurrency. The α-algorithm [START_REF] Van Der Aalst | Workflow Mining: Discovering Process Models from Event Logs[END_REF] is an example of a simple technique that takes concurrency as a starting point. However, this simple algorithm has problems dealing with complicated routing constructs and noise (like most of the other approaches described in literature). In [START_REF] Van Dongen | Multi-Phase Process Mining: Building Instance Graphs[END_REF][START_REF] Van Dongen | Multi-Phase Mining: Aggregating Instances Graphs into EPCs and Petri Nets[END_REF] a more robust but less precise approach is presented.

Region-based approaches are able to express more complex control-flow structures without underfitting. State-based regions were introduced by Ehrenfeucht and Rozenberg [START_REF] Ehrenfeucht | Partial (Set) 2-Structures -Part 1 and Part 2[END_REF] in 1989 and generalized by Cortadella et al. [START_REF] Cortadella | Deriving Petri Nets from Finite Transition Systems[END_REF]. In [START_REF] Van Der Aalst | Process Mining: A Two-Step Approach to Balance Between Underfitting and Overfitting[END_REF][START_REF] Van Dongen | An Iterative Algorithm for Applying the Theory of Regions in Process Mining[END_REF] it is shown how these state-based regions can be applied to process mining. In parallel, several authors applied language-based regions to process mining [START_REF] Bergenthum | Process Mining Based on Regions of Languages[END_REF][START_REF] Van Der Werf | Process Discovery using Integer Linear Programming[END_REF]. In [START_REF] Carmona | Process Mining Meets Abstract Interpretation[END_REF] a related approach based on convex polyhedra is presented.

For practical applications of process discovery it is essential that noise and incompleteness are handled well. Surprisingly, only few discovery algorithms focus on addressing these issues. Notable exceptions are heuristic mining [START_REF] Weijters | Rediscovering Workflow Models from Event-Based Data using Little Thumb[END_REF], fuzzy mining [START_REF] Günther | Fuzzy Mining: Adaptive Process Simplification Based on Multi-perspective Metrics[END_REF], and genetic process mining [START_REF] Van Der Aalst | Genetic Process Mining[END_REF][START_REF] Alves De Medeiros | Genetic Process Mining: An Experimental Evaluation[END_REF].

See [START_REF] Van Der Aalst | Process Mining: Discovery, Conformance and Enhancement of Business Processes[END_REF] for a more elaborate introduction to the various process discovery approaches described in literature.

Balancing Between Quality Criteria such as Fitness, Simplicity, Precision, and Generalization

Generally, we use four quality dimensions for judging the quality of the discovered process model: fitness, simplicity, precision, and generalization. As illustrated by Fig. 2(a), the different criteria may be competing.

A model with good fitness allows for the behavior seen in the event log. A model has a perfect fitness if all traces in the log can be replayed by the model from beginning to end. There are various ways of defining fitness [START_REF] Van Der Aalst | Process Mining: Discovery, Conformance and Enhancement of Business Processes[END_REF]. It can be defined at the case level, e.g., the fraction of traces in the log that can be fully replayed. It can also be defined at the event level, e.g., the fraction of events in the log that are indeed possible according to the model. Fitness is not sufficient as it is easy to construct process models that allow for all imaginable behavior ("underfitting") or simply encode the example behaviors stored in the event log ("overfitting").

A model is precise if it does not allow for "too much" behavior. A model that is not precise is "underfitting". Underfitting is the problem that the model overgeneralizes the example behavior in the log, i.e., the model allows for behaviors very different from what was seen in the log. For example, a Petri net without places and just transactions {a, b, c, d, e} is able to replay the example event log, but also any other event log referring to the same set of activities.

A model should generalize and not restrict behavior to the examples seen in the log. A model that does not generalize is "overfitting". Overfitting is the problem that a very specific model is generated whereas it is obvious that the log only holds example behavior, i.e., the model explains the particular sample log, but a next sample log of the same process may produce a completely different process model.

The simplicity dimension refers to Occam's Razor ; the simplest model that can explain the behavior seen in the log, is the best model. The complexity of the model can be defined by the number of nodes and arcs in the underlying graph. Also more sophisticated metrics can be used, e.g., metrics that take the "structuredness" or "entropy" of the model into account.

Choosing the Right Representation Bias

The four main quality dimensions mentioned in Fig. 2(a) illustrate that process discovery is a non-trivial problem. For an event log there may be a simple model with a fitness of 80% and a more complex model with a fitness of 95%. Both models can be useful. Therefore, most process discovery algorithms provide parameters to guide the discovery process. However, the search process is bounded by the representational bias M [START_REF] Van Der Aalst | On the Representational Bias in Process Mining (Keynote Paper)[END_REF].

It is important to separate the visualization of process mining results from the representation used during the actual discovery process. The selection of the representational bias M should be a conscious choice and should not be (only) driven by the preferred graphical representation. To illustrate the importance of this choice, we discuss implications related to correctness and expressiveness.

The three Petri nets shown in Fig. 1(b-d) are so-called WF-nets (workflow nets) [START_REF] Van Der Aalst | The Application of Petri Nets to Workflow Management[END_REF]. A WF-net is a Petri net with a designated source place (start ) and sink place (end ). All nodes in the net need to be on a path from start to end. A commonly used correctness notion for WF-nets is soundness [START_REF] Van Der Aalst | Soundness of Workflow Nets: Classification, Decidability, and Analysis[END_REF]. A WF-net is sound if from any reachable state it is possible to reach the desired final state with just a token in end. Moreover, there should be no dead parts that can never be executed. WF-net N 1 in Fig. 1 is sound. WF-net N 2 is not sound because of the potential deadlocks: after executing b or c it is no longer possible to reach the desired final state. WF-net N 3 is not sound because only the trace ade results in the desired final state. The notion of soundness is not specific for WF-nets and similar notions can be defined for all mainstream process modeling languages [START_REF] Van Der Aalst | The Application of Petri Nets to Workflow Management[END_REF][START_REF] Van Der Aalst | Soundness of Workflow Nets: Classification, Decidability, and Analysis[END_REF]. Similar anomalies can be encountered in EPCs, BPMN models and the like [START_REF] Weske | Business Process Management: Concepts, Languages, Architectures[END_REF].

Figure 2(b) shows the implications of having a representational bias M that allows for unsound models. Consider for example a genetic process mining algorithm. Initially, process models are generated randomly. Obviously, most of such models will not be sound. In each generation of a genetic process mining algorithm new models (called individuals) are created using mutation and crossover. When using conventional languages, such genetic operators are likely to create models with anomalies such as deadlocks and livelocks. As a result, the search process may take unnecessarily long because irrelevant models are considered (cf. Fig. 2(b)). The representational bias M also has implications on the expressiveness of the resulting model. To illustrate this, consider event log L ′ = [abce 42 , acbe 38 , ae 20 ] shown in Fig. 3(a). Note that this is original event log where activity d is filtered out. WF-net N 4 in Fig. 3(b) has a silent step τ to model that after executing a it is possible to immediately enable e, i.e., the execution of τ is invisible and not recorded in the event log. WF-net N 5 has two a labeled transitions to model the three observed scenarios. Both N 4 and N 5 are able to reproduce the behavior seen in event log L ′ . However, there is no WF-net with unique visible labels having the visible behavior reflected in L ′ . Hence, any process discovery algorithm that has a representational bias limited to WF-nets with unique visible labels is destined to fail. The α algorithm [START_REF] Van Der Aalst | Workflow Mining: Discovering Process Models from Event Logs[END_REF] uses such a representational bias. Therefore, it is unable to discover the underlying process properly. The α algorithm produces WF-net N 6 shown in Fig. 3(d). This model does not allow for trace ae.

The example shows that the representational bias M may exclude desirable models. It is important that M supports at least the basic workflow patterns.

Process Trees

In this paper, we choose to use a representational bias called process trees that satisfy two important properties: (i) all process trees correspond to sound models, (ii) even the most basic process trees support the basic control flow patterns.

A process tree is a directed connected graph without cycles. A node V in the graph is either a branch node or a leaf node. Each leaf node represents an activity from the collection of activities A. Each branch node, or operator node, has two children. These children can be either another operator node or a leaf. The labeling function ℓ assigns each operator node an operator from O and each leaf node an activity from A. Currently, we have defined basic operators for the sequence (→), exclusive choice (×) and parallel (∧) constructs. Furthermore, operators for loop ( ) and OR (∨) are available. The order of the children matters for the operators sequence and loop. The order of the children of a sequence operator specify the order in which they are executed (from left to right). For a loop, the left child is the 'do' part of the loop. After the execution of this 'do' part the right child, the 'redo' part, might be executed. After this execution the 'do' part is again enabled. The loop in Fig. 4 for instance is able to produce the traces A , A, B, A , A, B, A, B, A and so on. Therefore, the children of an operator node are ordered using a sorting function s. All operator nodes represent both the split and the join construction in other process modeling languages. The sequence, exclusive choice and parallel operators together cover all five basic Control Flow Patterns [START_REF] Van Der Aalst | Workflow Patterns[END_REF] which is one of the requirements as discussed in Section 2.3. Furthermore, by adding the loop and or operators, process trees are able to express any event log.

In contrast to Petri nets, process trees always represent sound models [START_REF] Kopp | The Difference Between Graph-Based and Block-Structured Business Process Modelling Languages[END_REF] and a straightforward translation from process trees to Petri nets exists. Figure 4 shows how each of the operators can be translated to a Petri net construct. The children of the sequential operator are ordered from left to right. In order to correctly translate the parallelism operator to a Petri net, new transitions need to be added. Since these transitions do not represent an observable activity these are marked as invisible or τ -transitions (as is for example the case in the Petri net of Figure 3 Unlike frequent pattern mining and episode mining [START_REF] Han | Frequent pattern mining: current status and future directions[END_REF], process tree discovery aims to discover end-to-end processes rather than frequent patterns. The goal is to find "complete process models" and not just process fragments that are executed frequently. Moreover, traditional data mining techniques are not considering all four quality dimensions and tend to focus on just two dimensions (e.g., fitness and simplicity).

(b)).

To determine the quality of a process tree, we need metrics to measure the four dimensions. While plenty of metrics exist [START_REF] De Weerdt | A critical evaluation study of model-log metrics in process discovery[END_REF][START_REF] Weidlich | Process compliance measurement based on behavioural profiles[END_REF] to measure the quality of a Petri net, we are not aware of any metrics for process trees. Therefore, to measure the quality of process trees, we measure the quality of the corresponding Petri net translation, where we focus on fitness and precision. For the fitness dimension we use the cost-based fitness as defined by [START_REF] Adriansyah | Conformance Checking using Cost-Based Fitness Analysis[END_REF] and precision is covered by behavioral appropriateness metric which is currently under development by the same authors.

The overall quality of a process tree is computed by taking the harmonic mean of the fitness and precision metric. For two inputs (x 1 and x 2 ) the harmonic mean H is defined as H = 2x1x2

x1+x2 . The harmonic mean ensures a 'pessimistic' fitness value when the two quality metrics are more apart. This ensures that if one metric scores very high but the other very low, the overall quality is relatively low since the two metrics should be more balanced.

Searching for Process Trees

In the introduction, we stated that the goal of selecting the right representational bias was to limit the size of the search space. Therefore, when comparing process trees to Petri nets, we should compare the size of the search space for a given number of activities (i.e. a given number of transitions in a Petri net, or a given number of leaf nodes in a process tree).

Since a place in a Petri net can have any transition as input or as output, or is not connected to that transition, there are 3 n different places and a Petri net contains any number of places (where we neglect the initial marking).

Definition 1 (Number of Petri nets on n activities). The number of different Petri nets on n activities is defined as:

#P N ets(n) = 2 3 n
The number of possible binary process trees having 5 types of operations (AN D,XOR,SEQ,OR and LOOP ) and n leafs for the activities depends on the number of operator nodes (n -1), the selection of the operator type of each node (5 n-1 ) and the possible orderings of the leaf nodes (n!), as well as the number of ordered rooted trees with n leaves: Definition 2 (Number of binary process trees). The number of binary process trees with three types of operator nodes can be defined as a function of the number of leaf nodes n as follows:

#T rees(n) = #StructuralCombinations • #OperatorChoices • #Leaf Orders = C(n -1) • 5 (n-1) • n! = (2(n -1))! (n)! (n -1)! • 5 (n-1) • n!
where C(n): the Catalan number sequence [START_REF]The On-Line Encyclopedia of Integer Sequences[END_REF] which specifies the number of ordered rooted trees with n operator nodes.

Table 1 shows the number of different Petri nets and process trees for a number of activities ranging from 1 to 6. It shows the number of process trees that are possible using three operators (SEQ,XOR and AN D) and when using all 5 operators. The table clearly shows that there are far less possible trees than there are Petri nets, even when using all 5 operator types. Furthermore all of the process trees represent sound models, while of the Petri nets, only a fraction is actually sound. Since any process tree that can be generated represents a sound model, a naive process mining algorithm could simply generate random trees, test their quality and if the quality is not good enough, try again. To see how many of such experiments would have to be conducted, we look at a simple example with 6 activities and three different logs. Furthermore, we only consider the SEQ, XOR and AN D operators. The first event log contains only one trace which describes a sequential process model, L SEQ = [abcdef ]. The next event log describes 6 activities in an exclusive choice, L XOR = [a, b, c, d, e, f ]. The third event log contains all 720 possible permutations of the 6 activities A -F and thus describes the process model where these 6 activities are executed in parallel.

For the sequential log containing 6 activities we iterated over all 7, 348, 320 possible trees and found there are 42 trees describing this behavior with an overall quality of 1. This can be also be calculated using Definition 2 by observing that there is only one correct order of the leaf nodes (namely A to F from left to right) and that all operator nodes should be of the type sequence. For both the exclusive choice and parallel event logs there are 30, 240 trees that describe this behavior. This implies that for the sequential case one out of 174, 960 trees is correct where for the exclusive choice and parallel case this is one out of 243 trees.

Generating random trees until the first tree is found with quality 1 can be seen as the repetition of a Bernoulli experiment until the first success, and hence this process follows a geometric distribution. Table 2 shows how many trees we expect to generate, when doing such an experiment 100 times, i.e. in order to randomly find a process tree with perfect quality for our sequential log, the number of trees that we expect to need to generate is 174, 960 with a 99% confidence interval of 4506.66. Clearly, just randomly searching for a process tree is not a good idea when mining a process model. Therefore, in Section 5 we investigated the use of genetic algorithms to more efficiently search for a process tree.

Genetic mining for process trees

Genetic process mining is a technique to discover process models from an event log of observed behavior. Instead of using a deterministic approach, as most discovery algorithms do, an evolutionary algorithm is applied [START_REF] Eiben | Introduction to Evolutionary Computing[END_REF]. This approach has first been applied to process mining in [START_REF] Van Der Aalst | Genetic Process Mining[END_REF][START_REF] Alves De Medeiros | Genetic Process Mining: An Experimental Evaluation[END_REF].

The main idea of evolutionary algorithms is that one of the following is unknown [START_REF] Eiben | Introduction to Evolutionary Computing[END_REF]: the input to the problem, the model or algorithm, or the desired output. In the case of genetic mining the input, the event log, is known and provided. The desired output given the input is not known exactly, but we can determine which solutions are better or worse than others by providing a fitness value for each candidate model. Therefore the goal of the genetic mining algorithm is to provide a (process) model that describes the observed behavior in the event log 'best' given a certain fitness. The fitness function can be used to emphasize desired characteristics of the resulting process model.

A genetic algorithm is a search heuristic where a suitable solution needs to be found among possible candidates. The search space is searched by (semi-) randomly creating and changing candidates until certain stop criteria are fulfilled. In general a genetic algorithm follows the flow as shown in Figure 5. The initial population, or set of candidate solutions, can be created completely random or using some simple heuristics. In the next step the fitness of each candidate is calculated. If the algorithm should continue then the candidates are changed. In general there are two types of change operations: crossover mixes elements of two candidates creating two children; mutation changes one or more details of a candidate. These change operations are applied to a selection of the fitter candidates. Furthermore, for a small group with the highest fitness values a copy is created, which is not changed, to make sure that a copy of the fittest candidates survive. Each cycle of fitness calculation and population changes is called a generation. When a specified minimum fitness value is achieved, or when a specified maximum number of generations or execution time has been reached, the algorithm stops. The fittest candidate is now returned as the output of the algorithm. In [START_REF] Van Der Aalst | Genetic Process Mining[END_REF][START_REF] Alves De Medeiros | Genetic Process Mining: An Experimental Evaluation[END_REF], a genetic algorithm is presented to mine Petri nets. This genetic algorithm uses an internal matrix representation that can easily be translated to a Petri net and vice versa. In essence the authors represent a Petri net as a matrix which makes it easier to define correct mutation and crossover functions. Since the matrix representation is almost as expressive as Petri nets and is able to describe unsound Petri nets, the search space is equivalent in size as the search space of Petri nets, shown in Table 1.

The fitness function, which specifies how 'good' a certain candidate is considering the event log, is the second most important part of a genetic algorithm. The fitness function determines the main characteristics of the output. It can for instance consider all, or a selection of, the quality dimensions shown in Figure 2. It is important however to correctly balance the different quality dimensions. If the fitness function for instance only considered the 'fitness' dimension, the resulting model is likely to have a very low 'precision' on the event log. Furthermore, if the event log contains a lot of noise, aiming for a perfect 'fitness' might not result in the desired process model. For simplicity, our fitness calculation directly uses the quality metrics discussed in Section 3 which cover the fitness and precision dimensions.

Another important aspect of the genetic algorithm are the crossover and mutation functions specified on the internal representation. The main purpose of the crossover function is to combine two good parts from two candidates together in a single candidate. The mutation function randomly modifies a candidate to introduce possibly new behavior that might be beneficial for the fitness. Together the crossover and mutation functions need to make sure that all possible candidates can be discovered.

In order to change the process tree candidates we define 4 mutation functions on process trees. The single node mutation selects a single vertex and modifies the labeling function ℓ on that node. This means that an operator node gets a different operator assigned and a leaf node represent a different activity. The second mutation function adds a leaf node with a randomly selected activity to a randomly selected operator node. In a similar way the third mutation function removes a randomly selected vertex, which might be an operator node. The most complicated mutation function is the 'internal crossover' mutation which swaps subtrees within a single process tree.

Our implementation currently does not use crossover since initial experiments showed that this was not beneficial for the performance. For the future we plan to add a guided crossover.

The performance of any genetic algorithm is determined mainly by the size of the search space and the time needed to compute the fitness of an individual. By using process trees as the internal representation we drastically reduce the search space as we only consider sound models and therefore we improve performance of the genetic algorithm. In this paper, we did not try to optimize the fitness computations.

Experimental Results

In this section we discuss the first experimental results of the initial version of the genetic algorithm. For these experiments we ran the genetic mining algorithm 100 times and recorded how many trees it created in order to find a candidate with an overall fitness of 1. We used a small population of 10 candidates in each generation. In each next generation the 2 fittest candidates of the last generation are copied without mutation. The 8 other candidates are created by first copying one of the candidates of the previous generation and then applying one of the mutation functions. Initialization of the 10 trees in the first generation was done completely random in order to test the mutation functions.

We applied the genetic algorithm on the three event logs introduced before. We compare the performance of our genetic algorithm to the case where trees are created completely random until a suitable candidate has been found. All of our experiments are independent and identically distributed. Therefore we can compare the random case, where we would create trees completely random, with our experiments. In the random case we would on average need to create 174, 960 process trees for the sequential or 243 process trees for the other 2 event logs. The 99% confidence interval is +/-4507 and +/-19.75, respectively, as shown in Table 3 (note that we copied the results of Table 2 for easy comparison). The experimental results shown in Table 3 clearly show an improvement over the random case. In all cases the number of trees that needed to be generated before finding a tree with perfect fitness was far less than the random case, even when considering the 99% confidence intervals.

This shows that by first drastically reducing the search space, followed by an application of a simple genetic mining algorithm, provides perspectives for a new genetic mining algorithm. Of course, performance can be further increased by initializing the trees in a smart way. Another important future improvement is the definition of a custom fitness function directly on process trees. This could drastically reduce the time required for a fitness calculation, which currently is the main performance issue. These initial results do conform our intuition that process trees are a good candidate for genetic mining.

Conclusion

Most process mining discovery algorithms suffer from the problem that the discovered model is potentially unsound. Considering unsound process models in a search space suggests that improvements are possible by eliminating these. In this paper, we propose an alternative representation for process models, process trees. Process trees are inherently sound and can easily be translated to other process modeling languages, such as Petri nets, EPCs or BPMN.

Process mining algorithms can be seen as search algorithms. By using process trees as a representation, the search space of all possible process models is drastically reduced, compared to Petri nets. In this paper we show that genetic algorithms can be defined to search this reduced search space. One of the main benefits of genetic mining algorithms is the flexibility. The desired characteristics of the resulting process model can be defined in the fitness function. This makes the genetic algorithm a versatile discovery algorithm that can be applied in many situations. In this paper we used existing Petri net based metrics to calculate fitness. As a result, our current approach is rather slow and not very suitable for real-life processes. However, it seems possible to define quality metrics directly on trees that make use of their unique characteristics. We expect that this will dramatically speed up the discovery process.

Fig. 1 .

 1 Fig. 1. A small event log (a) and four process models (b-e).

Fig. 2 .

 2 Fig.2. Process discovery can be viewed as a search problem with possibly competing quality criteria in an enormous search space mostly populated by incorrect models.

Fig. 3 .

 3 Fig. 3. One event log (a) and three process models (b-d).

Fig. 4 .

 4 Fig. 4. Translation of Tree Operators to Petri net constructs

Fig. 5 .

 5 Fig. 5. Genetic Algorithm flow

Table 1 .

 1 Size of the search space for varying number of activities.

	number of activities number of Petri nets	number of process trees 3 operators 5 operators
	1	8	1	1
	2	512	6	10
	3	134,217,728	108	300
	4	2,41785 •10 24	3,240	15,000
	5	1,41347 •10 73	136,080	1,050,000
	6	2,82401 •10 219	7,348,320 94,500,000

Table 2 .

 2 Results for Process Trees with 6 Activities

		Sequential Exclusive Choice Parallel
	Trees considered	174,960	243	243
	Variance	306,108,266	5,881	5,881
	99% Confidence Interval	4506.66	19.75	19.75

Table 3 .

 3 Results for Process Trees with 6 Activities

		Sequential	Exclusive Choice	Parallel
		Random Genetic Random	Genetic Random Genetic
	Trees considered	174,960 459.84	243	100.96	243 100.88
	Variance	306,108,266 95,042	5,881	8,454	5,881 18,515
	Standard dev	17,495.95 308.29	76.69	91.95	76.69 136.07
	99% Confidence Interval	4506.66 79.41	19.75	23.68	19.75 35.05