Verifying Inverse Model Neural Networks

Chelsea Sidrane
Sydney Katz
Anthony Corso
Mykel J. Kochenderfer

C. Sidrane et al.

Stanford University, Stanford CA 94305, USA

{csidrane, smkatz, acorso<EMAIL_ADDRESS>
Inverse problems exist in a wide variety of physical domains from aerospace engineering to medical imaging.
The goal is to infer the underlying state from a set of observations.
When the forward model that produced the observations is nonlinear and stochastic, solving the inverse problem is very challenging.
Neural networks are an appealing solution for solving inverse problems as they can be trained from noisy data and once trained are computationally efficient to run.
However, inverse model neural networks do not have guarantees of correctness built-in, which makes them unreliable for use in safety and accuracy-critical contexts.
In this work we introduce a method for verifying the correctness of inverse model neural networks.
Our approach is to overapproximate a nonlinear, stochastic forward model with piecewise linear constraints and encode both the overapproximate forward model and the neural network inverse model as a mixed-integer program.
We demonstrate this verification procedure on a real-world airplane fuel gauge case study.
The ability to verify and consequently trust inverse model neural networks allows their use in a wide variety of contexts, from aerospace to medicine.

§.§.§ Acknowledgements

This work was supported by AFRL and DARPA under contract FA8750-18-C-0099.
The NASA University Leadership initiative (grant 80NSSC20M0163) provided funds to assist the authors with their research, but this article solely reflects the opinions and conclusions of its authors and not any NASA entity.
This research was also supported by the National Science Foundation Graduate Research Fellowship under Grant No. DGE–1656518.

[Akintunde et al., 2018]
Akintunde, M., Lomuscio, A., Maganti, L., Pirovano, E.: Reachability analysis
for neural agent-environment systems. In: International Conference on
Principles of Knowledge Representation and Reasoning (2018)

[Bak et al., 2021]
Bak, S., Liu, C., Johnson, T.: The second international verification of neural
networks competition (vnn-comp 2021): Summary and results. arXiv preprint
arXiv:2109.00498  (2021)

[Bixby et al., 2004]
Bixby, R.E., Fenelon, M., Gu, Z., Rothberg, E., Wunderling, R.: Mixed-Integer
Programming: A Progress Report, pp. 309–325 (2004),

[Brooks et al., 2011]
Brooks, S., Gelman, A., Jones, G., Meng, X.L.: Handbook of Markov Chain
Monte Carlo. CRC Press (2011)

[Cheng et al., 2017]
Cheng, C.H., Nührenberg, G., Ruess, H.: Maximum resilience of artificial
neural networks. In: International Symposium on Automated Technology for
Verification and Analysis, pp. 251–268, Springer (2017)

[Corso et al., 2021]
Corso, A., Moss, R.J., Koren, M., Lee, R., Kochenderfer, M.J.: A survey of
algorithms for black-box safety validation of cyber-physical systems. Journal
of Artificial Intelligence Research 72(2005.02979), 377–428 (2021),

[Dutta et al., 2018]
Dutta, S., Jha, S., Sankaranarayanan, S., Tiwari, A.: Output range analysis for
deep feedforward neural networks. In: NASA Formal Methods Symposium, pp.
121–138, Springer (2018)

[Fischetti and Jo, 2017]
Fischetti, M., Jo, J.: Deep neural networks as 0-1 mixed integer linear
programs: A feasibility study. arXiv preprint arXiv:1712.06174  (2017)

[Ge et al., 2018]
Ge, H., Xu, K., Ghahramani, Z.: Turing: a language for flexible probabilistic
inference. In: International Conference on Artificial Intelligence and
Statistics, pp. 1682–1690 (2018),

[Goodfellow et al., 2016]
Goodfellow, I., Bengio, Y., Courville, A.: Deep Learning. MIT Press (2016),

[Gurobi Optimization, LLC, 2022]
Gurobi Optimization, LLC: Gurobi Optimizer Reference Manual (2022),

[Hamilton and Hauptmann, 2018]
Hamilton, S.J., Hauptmann, A.: Deep d-bar: Real-time electrical impedance
tomography imaging with deep neural networks. IEEE Transactions on Medical
Imaging 37(10), 2367–2377 (2018)

[Hoffman et al., 2014]
Hoffman, M.D., Gelman, A., et al.: The No-U-Turn sampler: adaptively
setting path lengths in Hamiltonian Monte Carlo. Journal of Machine
Learning Research 15(1), 1593–1623 (2014)

[Huang et al., 2018]
Huang, Z., Guo, Y., Arief, M., Lam, H., Zhao, D.: A versatile approach to
evaluating and testing automated vehicles based on kernel methods. In:
American Control Conference, pp. 4796–4802, IEEE (2018)

[Hussain et al., 2001]
Hussain, M.A., Kittisupakorn, P., Daosu, W.: Implementation of
neural-network-based inverse-model control strategies on an exothermic
reactor. Science Asia 27, 41–50 (2001)

[Kim and Nakata, 2018]
Kim, Y., Nakata, N.: Geophysical inversion versus machine learning in inverse
problems. The Leading Edge 37(12), 894–901 (2018)

[Koopman and Wagner, 2016]
Koopman, P., Wagner, M.: Challenges in autonomous vehicle testing and
validation. SAE International Journal of Transportation Safety 4(1),
15–24 (2016)

[Liu et al., 2021]
Liu, C., Arnon, T., Lazarus, C., Strong, C., Barrett, C., Kochenderfer, M.J.:
Algorithms for verifying deep neural networks. Foundations and Trends in
Optimization 4(3–4), 244–404 (2021), 10.1561/2400000035,

[Lomuscio and Maganti, 2017]
Lomuscio, A., Maganti, L.: An approach to reachability analysis for
feed-forward relu neural networks. arXiv preprint arXiv:1706.07351  (2017)

[Melzi and Sabbioni, 2011]
Melzi, S., Sabbioni, E.: On the vehicle sideslip angle estimation through
neural networks: Numerical and experimental results. Mechanical Systems and
Signal Processing 25(6), 2005–2019 (2011)

[Mosek ApS, 2018]
Mosek ApS: MOSEK Modeling Cookbook (2018)

[RTCA, 1992]
RTCA: RTCA/DO-178B, EUROCAE/ED-12B: Software Considerations in Airborne Systems
and Equipment Certification (1992)

[Sidrane et al., 2022]
Sidrane, C., Maleki, A., Irfan, A., Kochenderfer, M.J.: OVERT: An algorithm
for safety verification of neural network control policies for nonlinear
systems. Journal of Machine Learning Research 23(117), 1–45 (2022)

[Tamaddon-Jahromi et al., 2020]
Tamaddon-Jahromi, H.R., Chakshu, N.K., Sazonov, I., Evans, L.M., Thomas, H.,
Nithiarasu, P.: Data-driven inverse modelling through neural network (deep
learning) and computational heat transfer. Computer Methods in Applied
Mechanics and Engineering 369, 113217 (2020)

[Tjeng et al., 2019]
Tjeng, V., Xiao, K., Tedrake, R.: Evaluating robustness of neural networks with
mixed integer programming. In: International Conference on Learning
Representations (2019)

[Zakrzewski, 2001]
Zakrzewski, R.R.: Fuel volume measurement in aircraft using neural networks.
In: International Joint Conference on Neural Networks, vol. 1, pp. 687–692,
IEEE (2001)

[Zakrzewski, 2002]
Zakrzewski, R.R.: Verification of performance of a neural network estimator.
In: International Joint Conference on Neural Networks, vol. 3, pp.
2632–2637, IEEE (2002)

[Zakrzewski, 2004]
Zakrzewski, R.R.: Randomized approach to verification of neural networks. In:
International Joint Conference on Neural Networks, vol. 4, pp. 2819–2824,
IEEE (2004)

§ AIRPLANE FUEL GAUGE MODEL DETAILS

The forward measurement model mapping fuel mass to noisy pressure measurements and noisy acceleration measurements was described in brief in the body of the paper, and is described in more detail here.


[pages=-, offset=72 -72]Couverture.pdf

Declaration of Authorshipfalse

I, the undersigned student ZEKENG NDADJI Milliam Maxime, registration number CM04-10SCI1755, declare that this thesis submitted in fulfilment of the requirements for obtaining the degree of Doctor/PhD in Computer Science, option Software Engineering, speciality Business Process Management, is the result of my own work unless otherwise referenced or acknowledged.

The Student

ZEKENG NDADJI Milliam Maxime

Date: ...................................

The Co-Directors

TCHOUPÉ TCHENDJI Maurice

Senior Lecturer, University of Dschang, Cameroon

Date: ...................................

TAYOU DJAMEGNI Clémentin

Full Professor, University of Dschang, Cameroon

Date: ...................................

I dedicate this work to all those who one day, saw the efforts they had put into a project (especially an intense love relationship) being wiped out without a logical explanation and who took it upon themselves, to ride the waves unleashed by these storms, came out ten times stronger and developed an incredible desire to live rather than die. Like your daily efforts, this work is in large part the result of the knowledge that suffering has brought to me and thus, it contributes to prove Friedrich Nietzsche's aphorism: "what doesn't kill you, makes you stronger".

Along the paths I followed during this thesis, I have gained a unique experience and, I hope, the necessary maturity to aspire to the title of Doctor/PhD. Throughout these years of work, I have come to realise that producing a thesis is far from being a solitary labour. In order to go through this tunnel, one must be under the benevolent escort of the Almighty Lord and of souls of good faith. I have benefited from a multiform accompaniment of many persons, both physical and moral. I would like them to find in this section, the expression of my deep gratitude. I therefore thank very warmly:

- The LORD our God, creator of heaven and earth: in addition to my days, he offers me every day, the necessary grace and strength to continue to glorify him. Glory be to you, Holy Father!

- Dr TCHOUPÉ TCHENDJI Maurice, Senior Lecturer at the Department of Mathematics and Computer Science of the Faculty of Science of the University of Dschang: he took the time to mentor me throughout this work, inculcating in me his sense of commitment and organisation. Sir, I reiterate that you are my model.

- Pr TAYOU DJAMEGNI Clémentin, Head of the Computer Engineering Department of the Institute of Technology - Fotso Victor of Bandjoun: it was under difficult conditions that he agreed to supervise this work and to reward us with his legendary positivism. I'm more than honoured to be one of your students, Sir.

- All the imminent members of my pre-hearing and defence juries: they agreed to objectively evaluate this work. Thank you for the chance you are giving me, gentlemen.

- Dr PARIGOT Didier, Senior Researcher on Programming Languages at INRIA: he accompanied me during this thesis by his reviews, his points of view, his recommendations and his know-how in terms of software programming. I learned a lot from your multiple contributions, Sir.

- The INRIA/LIRIMA FUCHSIA Associate Research Team: they welcomed me when I needed it most and gave me a chance to express myself. Working with you guys is a lifelong dream.

- The lecturers at the University of Dschang: they contributed enormously to my education. As education is priceless, I can only express my gratitude.

- My parents, NDADJI Emmanuel and MAFFOZEMTSOP Marie: they gave me everything. I love you infinitely.

- My brothers, sisters, friends and colleagues (Nani, Chance, Alex, Arnold, Brice, Ariège, Brel, Doris, Audrey, Fabrice, Rodrigue, Virginie, Emeric, Nestor, Preston, Yann, Max, Ange, Lionel, etc.): I live only by you and for you (uh, for me too ;-)).

- My dear BANGUKET T. Nina: she proofread and corrected the typos in all my English documents. Now I can write a correct sentence in English, thanks to you.

Table of Contents

=In this thesis, we focus on the proposal of distributed workflow systems dedicated to the automation of administrative business processes. We propose an approach to build such systems by relying on the concepts of multiagent systems, Peer to Peer (P2P) architecture, Service-Oriented Architecture (SOA) and structured documents (artifacts) cooperative edition.
Indeed, we develop mathematical tools that allow any workflow systems designer, to express each administrative process in the form of an attributed grammar whose symbols represent tasks to be executed, productions specify a scheduling of these tasks, and instances (the derivation trees that conform to it) represent the different execution scenarios leading to business goal states. The obtained grammatical model is then introduced into a proposed P2P system which is in charge of carrying out the completely decentralised execution of the underlying process's instances.
The said system orchestrates a process's instance execution as a choreography during which, various software agents driven by human agents (actors), coordinate themselves through artifacts that they collectively edit. The exchanged artifacts represent the system's memory: they provide information on already executed tasks, on those ready to be executed and on their executors. The software agents are autonomous and identical: they execute the same unique protocol each time they receive an artifact. This protocol allows them to identify the tasks they must immediately execute, to execute them, to update the artifact and to disseminate it if necessary, for the continuation of the execution.
Moreover, actors potentially have only a partial perception of processes in which they are involved. In practice, this means that certain tasks can be carried out confidentially: this property makes it possible to offer automatic management of administrative processes that is a little closer to their non-computerised management.

Keywords: Administrative Workflows, Artifacts, Peer to Peer, Partial Replication, Business Process Management.

Une Approche Grammaticale d'Edition Coopérative entre pairs sur une Architecture Orientée Service

height 4.5pt

height 1.5pt

=Dans cette thèse, nous nous intéressons à la conception et à l'implémentation des systèmes workflows distribués, dédiés à l'automatisation des processus opérationnels dits administratifs. Nous proposons une approche de mise en oeuvre de tels systèmes en nous appuyant sur les concepts de systèmes multi-agents, d'architecture Pair à Pair (P2P, égal à égal), d'architecture orientée service et d'édition coopérative de documents structurés (artefacts).
En effet, nous développons des outils mathématiques permettant à tout concepteur de systèmes workflows, d'exprimer chaque processus administratif qu'il désire automatiser, sous forme d'une grammaire attribuée dont les symboles représentent les tâches à exécuter, les productions spécifient un ordonnancement de celles-ci, et les instances (les arbres de dérivation qui lui sont conformes) représentent les différents scénarii d'exécution menant aux différents états qui matérialisent l'accomplissement des objectifs de l'entreprise. Le modèle grammatical obtenu est ensuite introduit dans un système P2P que nous proposons, et qui est chargé d'assurer l'exécution complètement décentralisée d'instances du processus sous-jacent.
Ledit système orchestre l'exécution d'une instance de processus sous forme d'une chorégraphie durant laquelle, divers agents logiciels pilotés par des agents humains (acteurs), se coordonnent à l'aide d'artefacts qu'ils éditent collégialement. Les artefacts échangés représentent la mémoire du système: ils donnent des informations sur les tâches déjà exécutées, sur celles prêtes à l'être et sur leurs exécutants. Les agents logiciels sont autonomes et identiques: ils exécutent le même et unique protocole à chaque fois qu'ils reçoivent un artefact. Ce protocole leur permet d'identifier les tâches qu'ils doivent exécuter dans l'immédiat, de les exécuter, de mettre à jour l'artefact et de le diffuser si nécessaire, pour la continuation du processus d'exécution.
En outre, les acteurs n'ont potentiellement qu'une perception partielle des processus dans lesquels ils sont impliqués. Ce qui autorise donc une possible exécution confidentielle de certaines tâches en pratique: cette propriété permet d'offrir une gestion automatique des processus administratifs se rapprochant un peu plus, de leur gestion non informatisée.

Mots clés: Workflows Administratifs, Artefacts, Pair à Pair, Réplique Partielle, Gestion des Processus Opérationnels.

General Introductiontrue

The Emergence of Business Process Managementtrue

Business Process Management (BPM) has received considerable attention in recent years due to its potential for significantly increasing productivity and saving costs. It is defined by Wil M. P. Van Der Aalst  as "the discipline that combines knowledge from information technology and knowledge from management sciences and applies this to operational business processes". BPM aims to improve business processes by focusing on their automation, their analysis, their involvement in decision-making operations (management) and the organisation of work. Hence, BPM is often accompanied by software to manage, control and support business processes: these software systems are called Workflow Management Systems (WfMS) <cit.>.

The BPM discipline emerged in the 1980s in a more restrictive form known as Workflow Management (WfM). Before WfM was developed, information systems were built from scratch; it means that, all components of such systems had to be programmed, including data storage and retrieval <cit.>. Software vendors soon realised that many information systems had similar data management requirements. This generic functionality was therefore outsourced to a data management system. Subsequently, the generic functionality related to user interaction (forms, buttons, graphics, etc.) was outsourced to user interfaces generators. The trend to outsource recurring functionalities to generic tools has continued in different areas. It is in this context that WfM has been introduced. Precisely, a WfMS automatically manages the process-related aspects <cit.> of information systems. The aim of WfM in the design of information systems is to simplify as much as possible, the modelling and management of the business processes they automate: traditionally, this modelling and management are reduced to the specification of processes using simple graphical languages called workflow languages.

Across the years, WfM has evolved into BPM. While WfM focused primarily on the automation of business processes, i.e. it was not fundamentally interested in other issues such as the analysis, verification and maintenance of their specifications, BPM made it its foundation <cit.>. With this evolution, many tools and techniques have been developed and have allowed the BPM field to mature. Today, its relevance is recognised by practitioners (users, managers, analysts, consultants and software developers) and academics. The availability of many BPM systems (WfMS) and a series of BPM-related conferences is proof of this <cit.>.

With the evolution of WfM and the development of new concepts related to the implementation of collaborative software systems, namely Peer-to-Peer (P2P) computing, multiagent paradigm and Service-Oriented Architecture (SOA), the way of designing and implementing WfMS has also evolved. There has been a shift from centralised systems implemented according to a reference architectural model <cit.>, to fully distributed systems offering decentralised workflow execution <cit.>. New paradigms of specification and management of business processes have been developed too. Among these, we find the document-centric <cit.>, the email-based <cit.>, the database-based <cit.>, the artifact-centric <cit.>, the data-centric <cit.> paradigms, etc. The artifact-centric paradigm has been the subject of several studies over the last two decades <cit.>; it has been very successful because it has enabled the development of much more flexible workflow languages, that treat process data as first-class citizens, as opposed to the existing languages (BPMN - Business Process Model and Notation <cit.> -, YAWL - Yet Another Workflow Language <cit.> -, etc.), that were only concerned with process tasks scheduling and assignment to actors. All these concepts' evolution and this involvement of many technologies in workflow systems' engineering, has made the BPM field, one of the most attractive for software vendors and software engineering researchers.

The Mitigated Use of Business Process Managementtrue

The BPM discipline has quickly established itself as an indispensable solution to the process automation needs of large firms, which often involve production lines <cit.>. Indeed, the workflows encountered in this context are generally highly structured and their tasks are almost entirely automated (executed by machines); this greatly "simplifies" their management by BPM. Another field of application in which BPM tends to naturally impose itself, is that of science. Indeed, the management (storage, distribution, computation, analysis, etc.) of generally very voluminous scientific data, involves several human and material resources that are often distributed across organisations <cit.>. With the help of cloud computing, BPM in this context, serves to organise these resources for a more efficient management of scientific data <cit.>. In these two application contexts, the systems' complexity due to the large amount of data to be managed and to the time-consuming and intensive computations requiring computer support, as well as the multiplicity and the distributivity of the involved resources, have somehow "imposed" the use of BPM.

Although in its current state BPM could be applied very successfully in the context of organisations with so-called administrative business processes (i.e. processes whose tasks are often semi-automated and therefore require the expertise of human agents - they are then more complex to automate using generic frameworks) <cit.>, there is less enthusiasm for it <cit.>; information systems using classical database management concepts and tailored to the use cases involved, are often preferred. In some cases, such information systems are inspired by some BPM concepts or they embed workflow engines to make limited use of them: this is the case of Enterprise Resource Planning (ERP) systems such as SAP S/4HANA[Official website of SAP: <https://www.sap.com/>, visited the 19/03/2020.] and Oracle Fusion Applications (OFA)[Official website of Oracle ERP: <https://www.oracle.com/applications/erp/>, visited the 19/03/2020.] <cit.>. Therefore, the application of "pure" BPM is still limited to specific industries such as banking and insurance. This mitigated use of BPM for the automation of quite common administrative processes can be explained by the following factors:

* Building process management systems is considerably more "tricky" than building information systems using classical database management. In database-based information systems, a specific number of processes whose behaviours are known in advance are designed and automated, whereas in process management, systems are designed and implemented to offer a generic management of an arbitrary set of processes with behavioural similarities. To quote Wil M. P. Van Der Aalst , "BPM is multifaceted, complex, and difficult to demarcate"; it is therefore not accessible to everyone and requires from its practitionners : great capacities of reasoning, logical abstraction, generalisation and architectural design <cit.>.

* Existing BPM solutions are too abstract and generic. As a result, compared to traditional information systems, they are less suitable for certain applications such as the exclusive management of administrative processes, that have a variety of specifications depending on organisations <cit.>.

* There is no real consensus on BPM implementation techniques and tools. BPM is composed by a multitude of paradigms and tools. Even if an effort of standardisation has been made in recent years, WfMS vendors seem to prefer the development of multiple proprietary solutions <cit.>; in our opinion, this has the effect of reducing BPM credibility.

Because they offer enormous benefits in terms of time saving, implementation cost and system complexity management, we believe that there is a need to better adapt workflow solutions for administrative processes' management, which seem to be the most frequently encountered <cit.>. Naturally, we are not the first to take an interest in this issue; the authors of <cit.> and <cit.> have established that the potential obstacle to the popularisation of workflow solutions, is the imbalance of research work on the different BPM aspects. Indeed, they believe that research has focused too much on BPM specific artifacts (such as process models) rather than on improving organisations' business processes: this does not meet the real use and needs of BPM practitioners. They therefore propose to address now the issue of business process improvement, in order to give even more reasons to organisations regarding the choice of BPM for their processes management. This perspective is shared by a plurality of researchers; hence their growing interest in the new field of process mining[Process mining is one of the leading techniques conducting workflows' event data automatic analysis, for possible improvement of its corresponding workflow model <cit.>.] <cit.>.

Although the idea of improving business processes by analysing the data produced during their execution is interesting, we believe that it does not answer the question that we are struggling with: how can we get information system users (organisations and software vendors) to systematically opt for BPM technology to automate their processes ? Indeed, data analysis is posterior to the users' choice of a technology to produce these data. Moreover, the question of improving business processes seems really interesting for use cases where these processes are very complex; it is not always the case for administrative processes.

Our Global Visiontrue

Because the benefits of BPM are now widely recognised and unanimously accepted, we believe that it would be more interesting to tackle the problem of its popularisation for administrative business processes automation, by improving its technology as it stands at present. Therefore, it would be a matter of:

* Making more accessible, the automation of administrative business processes using BPM. We believe that if the implementation of workflow systems for administrative business processes is simplified, then more and more software vendors will choose it to produce organisations' information systems.

* Adapt BPM technology so that it is less abstract and evasive, so that it is closer to that of classical information systems, and so that it can respond to specific problems of organisations.

We believe that one way to achieve these goals, is to apply the domain-specific software engineering <cit.> to BPM and thus, to focus on a kind of Domain-Specific BPM: that is the application of BPM techniques in specific domains of activity, thus respecting the constraints imposed by them, and offering a framework which best fits the needs of practitioners in these domains. In this thesis therefore, we must use BPM exclusively for the automation of administrative business processes: it is not a matter of reinventing the wheel (even if some new concepts are added) but rather of reproducing and adapting in the more constrained context of administrative business processes management, what is already being done in BPM, while introducing new concepts and making judicious choices to achieve the desired goals.

As far as we know, there are no other scientific studies that have focused exclusively on the automation of administrative processes. On the other hand, there is a growing effort among workflow solution providers to popularise administrative BPM. Precisely, they increasingly offer to organisations, cloud-based and flexible process management solutions such as Metatask[Official website of Metatask: <https://metatask.io/>, visited the 29/03/2020.], Samepage[Official website of Samepage: <https://www.samepage.io/>, visited the 29/03/2020.], Digital Business Transformation Suite[Official website of Digital Business Transformation Suite: <https://www.interfacing.com/>, visited the 29/03/2020.], Favro[Official website of Favro: <https://learn.favro.com/>, visited the 29/03/2020.], etc. Let us mention that there are studies focused on adapting BPM technologies to scientific data management exclusively (Domain-specific BPM): these gave birth to the field of scientific workflows <cit.>.

The Challenge Addressed in this Thesistrue

In this thesis, we are interested in the automation of administrative business processes (exclusively) using BPM technology. The idea is to use the most up-to-date paradigms already developed in the implementation of workflow systems, to produce a new approach for the specification and execution of administrative business processes. Nowadays, the most common paradigms and concepts used in the implementation of workflow management approaches include:

* Artifact-centric paradigm: it is the most successful BPM paradigm of the last two decades; it simplifies the specification of a business process, to the instantiation of a data structure called artifact, whose state evolves into a business goal state when executing process instances.

* Cooperative edition of documents: in the artifact-centric paradigm, an artifact can be seen as a structured document containing the execution state of a process instance at a given time. Because the evolution of the state contained in it is the consequence of actions carried out by the different actors involved in the considered instance's execution, this execution can be assimilated to the cooperative edition of structured documents.

* Peer to Peer computing: workflow systems increasingly rely on P2P architectures; as opposed to centralised systems, they facilitate scalability and fault tolerance <cit.>.

* Multiagent paradigm: the multiagent paradigm was developed to facilitate the creation of distributed systems, especially those based on P2P architectures. It is also increasingly used in workflow systems, where process tasks are now executed by agents that communicate through messages; these agents have a high degree of autonomy to allow better decentralisation of process management.

* Service-Oriented Architecture: in decentralised workflow management systems based on P2P architectures, the concept of SOA is generally used to define communication protocols between agents and to increase their autonomy by implementing a loose coupling between them.

We combine these concepts to produce a workflow solution that best suits the automation of administrative business processes. Because this project is much too voluminous to be addressed in the context of a single PhD thesis, we will focus herein, only on the fundamental aspects: administrative process modelling and their distributed execution. One could summarise the main objective of this thesis by saying that it focuses on:

The proposal of a new artifact-centric framework, facilitating the modelling of administrative business processes and the completely decentralised execution of the resulting workflows; this completely decentralised execution being provided by a P2P system conceived as a set of agents communicating asynchronously by service invocation so that, the execution of a given workflow instance is technically assimilated to the cooperative edition of (mobile) structured documents called artifacts.

This justifies the title of this thesis. We should however admit that, a title like "yet another approach to facilitate administrative workflows design and distributed execution using structured and cooperatively edited mobile artifacts" would certainly have better reflected the work done[Although this is the title that best suits our work, academic constraints have "forced" us to keep the one currently in use (A Grammatical Approach to Peer-to-Peer Cooperative Editing on a Service-Oriented Architecture). Indeed, it is with this last one that we applied for a thesis in our doctoral school; at the time when we were certain of the judicious title for our work, the legal texts governing the PhD thesis in our institution, no longer allowed us to make changes to the title of our thesis.].

A Synoptic View of our Methodology and Engineeringtrue

A synoptic view of our methodology.

Figure <ref> summarises the methodology and chronology we used to complete this thesis work. We started by studying a plethora of concepts including, the key concepts presented in chapter <ref>. Then, we reinforced our knowledge on some other concepts, especially those related to the implementation of distributed systems (see fig. <ref>(1)). Having a better knowledge on BPM, especially on the artifact-centric paradigm, we undertook the design of a new artifacts' model; the search for such a model led us to an extensive study of structured cooperative editing workflows. In particular, we studied the structured documents asynchronous cooperative editing model proposed by Badouel and Tchoupé  so well that, we extended it with three new contributions (see chapter <ref>). Based on the document model manipulated by Badouel and Tchoupé, we derived an artifact model (an attributed grammar) that can be used to specify administrative business processes. We then designed a P2P system based on communicating agents using a service-oriented model, capable of executing in a completely decentralised manner, administrative processes specified using the proposed artifact model. To demonstrate the concreteness of our artifact-centric model, we finally implemented a fully functional prototype system allowing to experiment the proposed models on various administrative processes (see chapter <ref>). As a result, we count at least six major contributions in this thesis:

* An extension of the merge algorithm proposed by Badouel and Tchoupé for the cooperative edition of a structured document, so that it can be applied in the more general case where edition conflicts might appear. It should be noted that this contribution was initiated in our Master's work before being fully matured during our first year of thesis. Some of the elements presented here are therefore part of our Master's dissertation;

* A generic system architecture that can be used to produce workflow systems for the cooperative editing of structured documents based on the Badouel and Tchoupé extended model;

* A workflow system prototype referred to as TinyCE v2 (a Tiny Cooperative Editor version 2), coded in Java and Haskell following the proposed system architecture and a novel cross-fertilisation protocol. It allowed us to test all the proposed algorithms related to the merge of documents' replicas;

* Another tree-based model of "business artifact" for administrative processes modelling, which makes it possible to better assimilate them to structured documents edited cooperatively;

* A choreography-oriented artifact-centric workflow execution model in which geographically dispersed agents execute the same and unique update (editing of artifact upon receipt) and diffusion (dissemination of updates) protocol;

* A prototype of a distributed system referred to as P2PTinyWfMS (a Peer-to-Peer Tiny Workflow Management System), allowing to fully experiment the artifact-centric approach investigated in this thesis.

More concretely, in the asynchronous cooperative editing workflow as perceived by Badouel and Tchoupé, each of the co-authors receives in the different phases of the editing process, a copy of the edited document to insert his contribution.
Since the collectively edited document is structured, it may in some cases, be preferable for reasons of confidentiality for example, that a co-author has access only to certain information; meaning that, he only has access to certain parts of the document, belonging to certain given types (sorts[A sort is a datum used to define the structuring rules (syntax) in a document model. Example: a non-terminal symbol in a context free grammar, an ELEMENT in a Document Type Definition (DTD).]) of the document model. Thus, the replica $t_{\mathcal{V}_i}$ edited by co-author $c_i$ from the site $i$ may be only a partial replica of the (global[We designate by global document or simply document when there is no ambiguity, the document including all parts.]) document $t$, obtained via a projection operation, which conveniently eliminates from the global document $t$, parts which are not accessible to the co-author in question. Badouel and Tchoupé call view of a co-author, the set of sorts that he can access.

When asynchronous local editions are done on partial replicas, it can be assumed that each co-author has on his site a local document model guiding him in his edition. This local model can help to ensure that for any update $t_{\mathcal{V}_i}^{maj}$ of a partial replica $t_{\mathcal{V}_i}$ (conform to the considered model), there is at least one document $t_c$ conform to the global model so that $t_{\mathcal{V}_i}^{maj}$ is a partial replica of $t_c$: for this purpose, the local model should be coherent towards the global one[Intuitively, a local model of document is coherent towards a global model if any partial document $t_{\mathcal{V}_i}$ that is conform to it, is the partial replica of at least one (global) document $t_c$ conform to the global model.]. Thus, because of the edition's asynchronism, the only inconsistencies that we can have when the synchronisation time arrives are those from the concurrent edition of the same node[Manipulated documents are structured, they can be intentionally represented by a tree. Intuitively, a node is an identifiable part in the document (a section, a subsection, an image, a table, …): it is the instance of a sort.]  (in the point of view of the global document) by several co-authors: the partial replicas concerned are said to be in conflict.
In its first contribution, this thesis proposes an approach of detection and resolution of such conflicts by consensus,
using a tree automaton said of consensus, to represent all the documents that are the consensus of competing editions realised on different partial replicas.

A structured document $t$ is intentionally represented by a tree that possibly contains buds[A bud is a leaf node of a tree indicating that an edition must be done at that level in the tree. Edit a bud consists to replace it by a subtree using the productions of the grammar of the document.]. Intuitively, synchronise or merge consensually the updates $t_{\mathcal{V}_1}^{maj}, \ldots, t_{\mathcal{V}_n}^{maj}$ of $n$ partial replicas of a document $t$, consists in finding a document $t_{c}$ conform to the global model, integrating all the nodes of $t_{\mathcal{V}_i}^{maj}$ not in conflict and in which, all the conflicting nodes are replaced by buds. Consensus documents are therefore the largest prefixes without conflicts in merged documents.
Technically, the process for obtaining the documents forming part of the consensus is:
(1) For each update $t_{\mathcal{V}_i}^{maj}$ of a partial replica $t_{\mathcal{V}_i}$, we associate a tree automaton with exit states $\mathcal{A}^{(i)}$ recognising the trees (conform to the global model) for which $t_{\mathcal{V}_i}^{maj}$ is a  projection.
(2) The consensual automaton $\mathcal{A}_{(sc)}$ generating the consensus documents is obtained by performing a synchronous product of the automata $\mathcal{A}^{(i)}$ with a commutative and associative operator noted $\otimes$  that we define. It is such that: $\mathcal{A}_{(sc)}=\otimes\mathcal{A}^{(i)}$.
(3) It only remains to generate the set of trees (or those most representative) accepted by the automaton $\mathcal{A}_{(sc)}$, to obtain the consensus documents.

The concept of structured document as perceived by Badouel and Tchoupé can be adapted to correspond to that of artifact in the sense of artifact-centric workflow systems. In this sense, a structured document can be seen as an artifact (annotated tree) that can be exchanged between the different agents (actors) involved in the execution of a given particular business process case; during its life, it is edited appropriately to make the system converge towards the achievement of one of the considered process's business goals. Its buds materialise the tasks to be executed or which are being executed and, an attributed grammar called the Grammatical Model of Workflow (GMWf) is used as artifact type. The sorts of a given GMWf represent the process tasks and each of its productions represents a scheduling of a subset of these tasks.
When a task is executed on a given site, the corresponding bud in the artifact is closed accordingly; then, one of the GMWf's production having the considered task as left hand side is choosen by the local stakeholder to expand the bud into a subtree highlighting in the form of new buds, the new tasks to be executed. To enrich the notion of access to different parts of artifacts, we add to GMWf, organisational information called accreditations (similar to views) that offer a simple mechanism for modelling the generally different perceptions that actors have on processes and their data. The couple (GMWf, accreditations) is then the proposed model of "business artifact".

The execution of an administrative process's instance modelled using the couple (GMWf, accreditations), is a choreography in which the agents are reactive autonomous software components, communicating in peer-to-peer mode and driven by human agents (actors) in charge of executing tasks. An agent's reaction to the reception of a message (an artifact) consists in the execution of a five-step protocol clearly described in this thesis.
This protocol allows it to: (1) merge the received artifact with the one it hosts locally in order to consider all updates, (2) project the artifact resulting from the merger in order to hide the parts to which the local actor may not have access and highlight the tasks to be locally executed, (3) make the local actor execute the revealed tasks and thus edit the potentially partial replica of the artifact obtained after the projection, (4) integrate the new updates into the artifact through an operation called expansion-pruning and finally, (5) diffuse the updated artifact to other sites for further execution of the process if necessary.
The agents' operational capabilities allow that, for the execution of a given process, an artifact created by one of them (initially reduced to an open node), moves from site to site to indicate tasks that are ready to be executed at the appropriate time and to provide necessary data (created by other agents) for that execution; the mobile artifact, cooperatively edited by agents, thus "grows" as it transits through the distributed system so formed.

The Organisation of this Manuscripttrue

The rest of this thesis manuscript consists of four chapters and two appendices organised as follows:

Chapter <ref> - A State of the Art in Business Process Management: the Artifact-Centric Modelling: we present some basic concepts related to the field of BPM, P2P, SOA, as well as the multiagent and artifact-centric paradigms. We also do a survey of some P2P and artifact-centric workflow management systems.

Chapter <ref> - A Workflow for Structured Documents' Cooperative Editing : Key Principles and Algorithms: after a brief presentation of Badouel and Tchoupé's asynchronous cooperative edition model, we present our algorithm for reconciling partial replicas of a structured document as well as a generic architecture of administrative workflow management systems.

Chapter <ref> - A Choreography-like Workflow Design and Distributed Execution Framework Based on Structured Mobile Artifacts Cooperative Editing: we propose a new choreography-like approach to address administrative workflow design and their distributed execution. We also present a fully functional prototype system built according to the proposed approach.

General Conclusion: we summarise our work and present some possible venues for its further development.

Appendix <ref> - Implementations of Some Important Algorithms Presented in this Thesis: we present an implementation of all this thesis' key algorithms in the Haskell language.

Appendix <ref> - List of Scientific Communications Issued from the Work Presented in this Thesis: we list the various scientific papers we produced during this thesis.

A State of the Art in Business Process Management: the Artifact-Centric Modelling

A Workflow for Structured Documents' Cooperative Editing : Key Principles and Algorithms

A Choreography-like Workflow Design and Distributed Execution Framework Based on Structured Mobile Artifacts' Cooperative Editing

General Conclusiontrue

We hereby summarise the work reported and presented in this document. To this, we associate a critical analysis of our models and methodological choices. Finally, we present some research avenues that can be explored following the work in this thesis manuscript.

Recall of this Thesis' Challenge and of our Methodological Choicestrue
In this thesis, we focused on the automation of business processes using the technological framework offered by the BPM domain.
We have contributed to the ambition of making more accessible, administrative business processes automation through this technology. We were guided by the aim of increasing its success in business sectors using administrative processes as it has been in other sectors such as science, banking and insurance, which are governed by much more programmable processes.
We thought that a first step towards achieving this great ambition was to rely on the current (most up-to-date) BPM paradigms and tools, to design and implement a new BPM framework that would be tailor-made for the management of administrative business processes.
Having identified the artifact-centric BPM, structured cooperative edition, P2P computing, multiagent system and SOA concepts as being the hot topics in the implementation of BPM, we set the following goal for this thesis:

The proposal of a new artifact-centric framework, facilitating the modelling of administrative business processes and the completely decentralised execution of the resulting workflows; this completely decentralised execution being provided by a P2P system conceived as a set of agents communicating asynchronously by service invocation so that, the execution of a given workflow instance is technically assimilated to the cooperative edition of (mobile) structured documents called artifacts.

To achieve this goal, we have chosen to base our work on the structured document cooperative editing model developed by Badouel and Tchoupé a decade earlier. They proposed an approach based on grammatical models, to manage the lifecycle of a document collegially edited by actors on geographically distant sites. In their model, each actor has a potentially partial view (obtained by projection) of the edited document. The latter is used as an interface between the different actors of the system. When an actor receives a document he must know from its content, what he can do and/or what he has to do about it. The information contained in a document can only grow over its lifetime in the system. Since the system is distributed and under the assumption that several actors can contribute concurrently, it is possible that at any given time there may be several potentially partial replicas of the document in the system. Therefore, it was necessary not only to address the problems related to the coherence of views in order to ensure the feasibility of synchronisation/merge, and to ensure the system's convergence towards a coherent end-state, but also to provide algorithms for the merging of partial replicas. Badouel and Tchoupé did this brilliantly, making their work a solid foundation for modelling workflow systems.

We adapted Badouel and Tchoupé's document model to define an artifact model. Like them, we have therefore chosen to use grammars as our basic mathematical instrument. In the same vein, we made the choice to model workflow systems in which actors have potentially only a partial perception of the processes they execute. We believe that this configuration is relevant to many administrative business processes. For example, in a peer-review process, a reviewer does not necessarily need to know if another reviewer has been contacted for the expertise of the article entrusted to him; and even if so, he should not necessarily know if the latter has already returned his report, etc.
Similarly, when organising a journey for a Head of State, not all actors (secret services, civil office, doctor, presidential guard, etc.) have access to the same information which may include for example, tasks to be executed, their dates and states of execution, etc.

A Critical Analysis of the Performed Worktrue
Chronologically, we started by better understanding Badouel and Tchoupé's model in order to extend it so that it takes into account, conflicts detection and resolution. We then embarked on the construction of a workflow system based on this model by first proposing a generic architecture of such systems and an experimental system prototype based on it. We finished by proposing an artifact-centric framework for the completely decentralised management of administrative business processes. The results we can claim are the following:

An algorithm for reconciling partial replicas of a structured document: we gave a solution to the conflicts that arose when merging partial replicas of a structured document by developing reconciliation and control techniques adapted to the modelling of Badouel and Tchoupé. To address this problem, we have expressed it as that of the consensual merging of $k$ updated partial replica $(t_{\mathcal{V}_i}^{maj})_{1 \leq i\leq k}$ (according to $k$ views $(\mathcal{V}_i)_{1 \leq i\leq k}$) whose global model is given by a grammar $\mathbb{G}=\left(\mathcal{S},\mathcal{P},A\right)$, which consists in: finding the largest documents $t^{maj}_{\mathcal{S}}$ conforming to $\mathbb{G}$ such that, for any document $t$ conforming to $\mathbb{G}$ and admitting $t_{\mathcal{V}_i}^{maj}$ as projection along the view ${\mathcal{V}_i}$, $t^{maj}_{\mathcal{S}}$ and $t$ are eventually updates each for other.
The solution we have proposed is as follows: (1) We associate a tree automaton with exit states $\mathcal{A}^{(i)}$ for each update $t_{\mathcal{V}_i}^{maj}$ of a partial replica $t_{\mathcal{V}_i}$; this automaton recognises the trees (conform to the global model) for which $t_{\mathcal{V}_i}^{maj}$ is a projection. (2) We perform a synchronous product of the automata $\mathcal{A}^{(i)}$ with a commutative and associative operator noted $\otimes$ that we define to obtain the consensual automaton $\mathcal{A}_{(sc)}$ generating the consensus documents: $\mathcal{A}_{(sc)}=\otimes\mathcal{A}^{(i)}$. (3) We obtain the consensus documents by generating the set of trees accepted by the automaton $\mathcal{A}_{(sc)}$.

A software architecture for the implementation of workflow systems: we proposed a generic architecture that could facilitate the implementation of workflow systems as modelled by Badouel and Tchoupé. The proposed architecture is composed of three tiers: clients, a central server and administration tools. These three tiers are interconnected around a middleware that facilitates service-oriented interfacing between them.

TinyCE v2: based on the proposed system architecture, we have built a workflow system prototype referred to as TinyCE v2. The latter was coded in Java and Haskell following a cross-fertilisation protocol that we presented in this manuscript, and it allowed us to test all the proposed algorithms related to the reconciliation of documents' partial replicas.

A grammar-based language for the artifact-centric modelling of administrative processes: we proposed a new tool (a language) that allows to specify any administrative business process using a triplet $\mathbb{W}_f=\left(\mathbb{G}, \mathcal{L}_{P_k}, \mathcal{L}_{\mathcal{A}_k} \right)$ composed of:
a grammatical model (GMWf) $\mathbb{G}$, a list of actors $\mathcal{L}_{P_k}$ and a list of accreditations $\mathcal{L}_{\mathcal{A}_k}$.
The GMWf is an attributed grammar used to describe all the tasks (by means of its symbols or sorts) of the studied process and the precedence of execution between them (by means of its productions); it is used as artifact type.
The list of accreditations provides information on the role played by each actor involved in the process execution; it is through accreditations that one is able to model the potentially partial perceptions that different actors have on the processes and their data.

A distributed workflow system and a fully decentralised execution model of administrative business processes: we proposed a multiagent-like distributed system in which autonomous software agents, based on a same and unique architecture presented in this manuscript, can exchange artifacts to communicate through service invocations, so as to orchestrate the fully decentralised execution of a given administrative business process instance modelled using the proposed grammar-based language. Each time a given agent receives an artifact, it executes a unique five-step protocol allowing it to identify tasks that are ready to be executed on its site, to allow their execution by the local actor and to diffuse if necessary, the updated artifact. To ensure the successful completion of this execution model on a given process case, the initial configuration of agents must be such as to guarantee the coherence of their respective accreditations (views). We have therefore proposed projection algorithms to derive agent-specific models that allow them to control their actions in order to ensure the system's convergence towards a business goal state. We have also investigated some mathematical properties of these algorithms.

P2PTinyWfMS: we have finally produced a prototype of a distributed system providing an artifact-centric management of administrative workflows according to our models. In this one, we have implemented all our algorithms in Java language and we have tested them on some process examples with convincing results.

The work we have done and presented in this manuscript is not perfect: neither in the applied methodology, nor in its presentation, and even less in its scientific contributions. The first criticisms that we can make of it are the following:

The diversity of our algorithms' presentation formats: we didn't just use pseudo code to present our algorithms. Sometimes we used code (Haskell and Java) and other times we wrote them as an arbitrary and ordered set of instructions written in natural language; in these cases we have neglected the more frequently used and more precise mathematical notations. This methodological choice of presentation can indeed be confusing for the reader. We justify it, however, by our desire to be precise, concise and as simple to understand as possible. We have written each of our algorithms in all the formats used in this manuscript before selecting for each of them, the format that seemed to us the clearest and simplest to present and understand.

Conflict management: we have chosen to use a single conflict resolution strategy: that of rejecting conflicting contributions and asking for new ones from contributors. This seems to us rather restrictive but it was a necessary (not necessarily wise) choice for a complete automation of the process of merging partial replicas of a structured document. However, in practice, it would be more appropriate to propose, following the example of Git, several conflict management strategies using a participant as an actor (coordinator) of this resolution.

Insistence on manipulating user views: although we have already justified the choice to take user views into consideration in our models by explaining their contribution to both security and accuracy, it is no less true that they do not always have a positive impact on our work. They have made it a little more complex and have led us to make slightly restrictive assumptions such as the non-recursive GWMf assumption that guarantees their projection. We could make the use of these views more flexible by restricting it to only censorship and not to the complete deletion of sensitive data; this would certainly allow us to overcome some assumptions.

The weak study of our execution model's properties: apart from the isolated study of the properties of a few of its algorithms, we did not study some properties of our decentralised workflow execution model as it is usual in similar BPM studies. We probably pay the consequences of our not completely formal and uncommon (but specific to artifact-centric models, it is one of their often mentioned limits) presentation that mixes the artifact modelling with its execution. A clear separation of these two aspects would certainly allow us to better study them in an isolated and more conventional way.

Still as theoretical as ever: obviously, we have the ambition to produce concrete systems that can be used in production environments. We are still a long way from that. For the two types of systems studied in this thesis, we have only produced prototypes that allow us to provide experimental proof of concepts. Theoretical studies on the Badouel and Tchoupé model being already quite advanced, it would be time to start implementing these concrete environments.

Some Perspectivestrue
The perspectives presented here are classified into categories according to their priority, to better guide the reader wishing to continue the work. The categories includes :

* Short-term: to indicate that the perspective is almost unavoidable and its results will be a real plus to the overall vision we have; it is therefore necessary to work on it as soon as possible;

* Mid-term: to indicate that the perspective's results will be pratical and usable but not a necessity;

* Long-term: to indicate that the perspective is optional and its theoretical results would only help give credibility to our work.

Here are now some interesting avenues for the continuation of our work that come to mind:

A Language for the Specification of Administrative Workflow based on Attributed Grammars (LSAWfP) (priority: short-term): it is obvious that process modelling is a crucial phase of BPM <cit.>. Despite the many efforts made in producing process modelling tools, existing tools (languages) are not commonly accepted. They are mainly criticised for their inability to specify both the tasks making up the processes and their scheduling (their lifecycle models), the data they manipulate (their information models) and their organisational models. Process modelling in these languages often results in a single task graph; such a graph can quickly become difficult to read and maintain. Moreover, these languages are often too general (they have a very high expressiveness); this makes their application to specific types of processes complex: especially for administrative processes.
One can generalise the artifact specification model presented in this thesis, in order to provide a new language for administrative processes modelling that allows designers to specify the lifecycle, information and organisational models of such processes using a mathematical tool based on a variant of attributed grammars. Therefore, the approach imposed by the new language will certainly require the designer to subdivide his process into scenarios, then to model each scenario individually using a simple task graph (an annotated tree) from which a grammatical model will be further derived. At each moment then, the designer will manipulate only a scenario of the studied process: this seems more intuitive and modular because it will allow to produce task graphs that will be more refined and therefore, more readable and easier to maintain.

A Scenario-Oriented Scheme for Administrative Business Processes Modelling (priority: mid-term): in the BPM community, researchers and professionals in the field have little interest in the "how" to model business processes to the benefit of the "with what" to model them. As a result, there is a plethora of workflow modelling languages but very few methods <cit.>. The question on the method to be used to successfully model a given process is however crucial when we know that BPM reduces the automation of the said process to its specification in a particular workflow language: a well carried-out specification produces a quality workflow system. Because the modelling language that can be extracted from the work of this thesis seems to be adapted to a process modelling philosophy centered on the notion of scenario, it would be interesting to propose a method that would accompany it. This one would present the steps to be followed to succeed in its scenario-oriented modelling of administrative workflow systems.

Verification of workflows specified using our models (priority: short-term): one of the BPM activities is the formal analysis/verification of the specifications produced using a given workflow language. Proposing and/or adapting a verification method for workflows designed using our models seems to be an interesting avenue of research especially since several similar works have done the same <cit.>. To this end, it will certainly be necessary to deeply study our models in order to highlight their mathematical properties. These properties will then make it possible to identify and present the criteria that must be verified by a specification in order to be qualified as correct (sound).

A tool to help in the specification of administrative processes with a scenario-oriented approach (priority: short-term): since the models we have proposed are new, it would be wise to propose a tool to assist in their use in practice. In addition to being a guide, such a tool should simplify the creation of process models and possibly validate them according to pre-established correction criteria. Moreover, it will be able to provide several DSL for saving the specifications as well as several modules for exporting them in more conventional notations (BPMN, YAWL, etc.).

A framework to generate administrative business processes' specific decentralised execution simulators (priority: mid-term): as implemented, the WfMS prototype P2PTinyWfMS can be used as a foundation for the production of a tool that generates simulators of the completely decentralised execution of administrative processes specified using our models. The new framework can be based on the models found in <cit.>; then, it will be implemented to generate a simulation environment tailored to a given administrative process. Still in a generative logic, another approach would be to use the recent concepts of model-driven engineering to produce a simulator based on integrated development environments such as Eclipse: one could for example use a GEMOC approach <cit.>.

Extension of our decentralised execution model for recursive GMWf and monitoring support (priority: short-term): we already mentioned this in the discussion section of chapter <ref>. It would be interesting to introduce into our multiagent system, new types of agents to monitor the execution of processes. In addition, we could also make the use of views more flexible by modifying their impact on projection operations. For example, we could redefine the artifact projection operation so that it no longer erases nodes but censors them; that is, it replaces them with symbols that help in the specification of control flows (restructuring symbols for instance) carrying no information on the process. This will preserve the possibility of offering only a potentially partial view of the processes and their data to actors while allowing the use of recursive symbols in GMWf.

Concrete implementation of WfMS supporting our models (priority: short-term): eventually, it will also be necessary to propose implementations of the WfMS presented here. Naturally, the implemented system will have to cover all phases and activities of the BPM lifecycle while focusing on the automation of administrative business processes. A study of recent BPM systems to ensure interoperability and an openness of the implemented system on the cloud will certainly be interesting avenues to explore.

Study of each proposed formal tool's properties in order to identify more precisely the class of workflows to which they apply (priority: long-term): another, more theoretical, line of research would be to formally analyse the proposed BPM approach to characterise the class of workflows to which it can actually be applied. We assumed that we were only interested in administrative workflows; however, the proposed models are quite general and could well be applied to other classes of workflows. The study carried out in this perspective should therefore determine these classes and the conditions under which the proposed model automates them.

Implementation of Some Important Algorithms Presented in this Thesis

We had thought to present in this appendix, a Haskell implementation of the projection algorithms proposed in chapter <ref> of this thesis. However, these are far too voluminous and their presentation here will not be very readable. We have therefore decided to present only the main data types here. We have hosted the rest of the produced Haskell code on the public Git repository accessible via this link: <https://github.com/MegaMaxim10/my-thesis-projection-algorithms>.

Haskell Type for Tagsfalse
Let's start by defining the tags for the node types (sequential or parallel). More clearly, in a given artifact, a node $A$ is tagged with |Seq| (resp. |Par|) when its sub-artifacts are executed in sequence (resp. potentially in parallel), i.e. the production used for its extension is a sequential (resp. parallel) one. A node with at most one sub-artifact is always tagged with |Seq|.
[frame=lines, fontsize=, numbers=left, numbersep=8pt]
data ProductionTag x = Seq x | Par x deriving (Eq, Show)

The |untagProduction| function below clears a given symbol of its tag (|Seq| or |Par|):
[frame=lines, fontsize=, numbers=left, numbersep=8pt]
untagProduction:: ProductionTag x -> x
untagProduction (Seq x) = x
untagProduction (Par x) = x

Definition of tags (closed, locked, unlocked or upstair) for symbolsfalse
In an artifact: a closed node is tagged |Closed|, an unlocked bud is tagged |Unlocked|, a locked bud is tagged |Locked| and an upstair bud is tagged |Upstair| (only found after expansion).
[frame=lines, fontsize=, numbers=left, numbersep=8pt]
data NodeTag x = Closed x | Locked x | Unlocked x | Upstair x deriving (Eq, Show)

The |untagNode| function below clears a given symbol of its tag (|Closed|, |Unlocked|, |Locked| or |Upstair|):
[frame=lines, fontsize=, numbers=left, numbersep=8pt]
untagNode:: NodeTag x -> x
untagNode (Closed x) = x
untagNode (Locked x) = x
untagNode (Unlocked x) = x
untagNode (Upstair x) = x

Definition of tags for symbol types (structuring or standard)false
The symbols of a given artifact $t$ are either those of the grammatical model $\mathbb{G}$ denoting $t$, or (re)structuring symbols introduced to preserve some important properties of our model (mainly, the form of productions used in GMWf): in this case, the symbols of $\mathbb{G}$ are said to be standard and are tagged with |Standard| while the (re)structuring symbols are tagged with |Structural|.
[frame=lines, fontsize=, numbers=left, numbersep=8pt]
data SymbolTag x = Structural x | Standard x deriving (Eq, Show)

As the previous "untag" functions, the |untagSymbol| function below clears a given symbol of its tag (|Structural| or |Standard|):
[frame=lines, fontsize=, numbers=left, numbersep=8pt]
untagSymbol:: SymbolTag x -> x
untagSymbol (Structural x) = x
untagSymbol (Standard x) = x

Haskell Type for Artifactsfalse
Recursively, we consider that an artifact is given by its root node (|nodeLabel|) and the list of its sub-artifacts (|sonsList|) tagged either by |Seq| (to indicate that they are executed in sequence) or by |Par| (to indicate that they are potentially executed in parallel). We do not consider empty artifacts. The corresponding Haskell type is as follows:
[frame=lines, fontsize=, numbers=left, numbersep=8pt]
data Artifact a = Node
nodeLabel:: a,
sonsList:: ProductionTag [Artifact a]
deriving Eq

Here is an example of artifact encoded in this type. It corresponds to the target artifact $art_1$ in the figure <ref>:
[frame=lines, fontsize=, numbers=left, numbersep=8pt]
art1 = Node (Closed "Ag") (
Seq [
Node (Closed "A") (
Seq [
Node (Closed "B") (Seq []),
Node (Closed "D") (Seq [])

Haskell Type for GMWffalse
Let's start by presenting a type for productions: a production is given by its left hand side (|lhs|) consisting of one symbol and by its right hand side (|rhs|) consisting of several symbols.
[frame=lines, fontsize=, numbers=left, numbersep=8pt]
data Production symb = Prod lhs:: symb, rhs:: [symb] deriving Eq

Finally, a GMWf is given by the set of symbols and the set of productions constituting it. The productions are tagged either by |Seq| or by |Par|:
[frame=lines, fontsize=, numbers=left, numbersep=8pt]
data GMWf a = GMWf
symbols:: [a],
productions:: [ProductionTag (Production a)]
deriving (Eq, Show)

These are the main data types that we have defined and which are manipulated by the different projection functions that are available in our Git repository[Our Git repository: <https://github.com/MegaMaxim10/my-thesis-projection-algorithms>]. They are included with some test cases that one will be able to immediately experiment.

List of Publications Issued from the Work Presented in this Thesis

Journal Papersfalse

* Milliam Maxime Zekeng Ndadji, Maurice Tchoupé Tchendji, Clémentin Tayou Djamegni and Didier Parigot. "A new Domain-Specific Language and Methodology based on Scenarios, Grammars and Views, for Administrative Processes Modelling." ParadigmPlus, Volume 1, Number 3, 2020, 1-22.

* Maurice Tchoupé Tchendji and Milliam Maxime Zekeng Ndadji. "Tree Automata for Extracting Consensus from Partial Replicas of a Structured Document." Journal of Software Engineering and Applications 10.05 (2017): 432-456.

Under Reviewfalse

* Maurice Tchoupé Tchendji, Milliam Maxime Zekeng Ndadji and Didier Parigot. "A Grammatical Approach for Administrative Workflow Design and their Distributed Execution using Structured and Cooperatively Edited Mobile Artifacts." Software and Systems Modeling, Springer (submitted).

* Milliam Maxime Zekeng Ndadji, Maurice Tchoupé Tchendji, Clémentin Tayou Djamegni and Didier Parigot. "A Projection-Stable Grammatical Model for the Distributed Execution of Administrative Processes with Emphasis on Actors' Views." Journal of King Saud University - Computer and Information Sciences, Elsevier (submitted).

Communications in Conferencesfalse

* Milliam Maxime Zekeng Ndadji, Maurice Tchoupé Tchendji, Clémentin Tayou Djamegni and Didier Parigot. "A Grammatical Model for the Specification of Administrative Workflow using Scenario as Modelling Unit." H. Florez and S. Misra (eds) Applied Informatics. ICAI 2020. Communications in Computer and Information Science, vol 1277, Springer, Cham, 2020. pages 131-145.

* Milliam Maxime Zekeng Ndadji, Maurice Tchoupé Tchendji, Clémentin Tayou Djamegni and Didier Parigot. "A Language for the Specification of Administrative Workflow Processes with Emphasis on Actors' Views." Gervasi O. et al. (eds) Computational Science and Its Applications - ICCSA 2020. ICCSA 2020. Lecture Notes in Computer Science, vol 12254, Springer, Cham, 2020. pages 231-245.

* Milliam Maxime Zekeng Ndadji, Maurice Tchoupé Tchendji and Didier Parigot. "A Projection-Stable Grammatical Model to Specify Workflows for their P2P and Artifact-Centric Execution." CRI'2019 - Conférence de Recherche en Informatique. Dec 2019, Yaoundé, Cameroon. (hal-02375958).

* Milliam Maxime Zekeng Ndadji and Maurice Tchoupé Tchendji. "A Software Architecture for Centralized Management of Structured Documents in a Cooperative Editing Workflow." Innovation and Interdisciplinary Solutions for Underserved Areas. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering (LNICST), Springer, Cham, 2018. pages 279-291.

* Maurice Tchoupé Tchendji and Milliam Maxime Zekeng Ndadji. "Réconciliation par consensus des mises à jour des répliques partielles d'un document structuré." CARI 2016 Proceedings, volume 1, 2016. pages 84-96.

[pages=1, offset=72 -72]Appendices/Articles/pplus-board.pdf
[pages=-, offset=72 -72]Appendices/Articles/ICAI-2020-Extended.pdf

[pages=1, offset=72 -72]Appendices/Articles/JSEA_10_01_Content_2017011916111320.pdf
[pages=-, offset=72 -72]Appendices/Articles/JSEA_2017052615402522.pdf

[pages=1,144-158, offset=72 -72]Appendices/Articles/ICAI-2020.pdf

[pages=1,269-283, offset=72 -72]Appendices/Articles/ICCSA-2020.pdf

[pages=4, offset=72 -72]Appendices/Articles/covers.pdf
[pages=-, offset=72 -72]Appendices/Articles/mainprojectionmgwfarima.pdf

[pages=1,281-293, offset=72 -72]Appendices/Articles/InterSol2017-Book.pdf

[pages=2,97-109, offset=72 -72]Appendices/Articles/CARI2016.pdf


# From Brans-Dicke theory to Newtonian gravity

Sergey Kozyrev

Scientific center gravity wave studies Dulkyn  e-mail<EMAIL_ADDRESS>
###### Abstract

We present the new interpretation of scalar field for the Brans-Dicke theory.
This interpretation is obtained by considering a fixed spacetime structure of
manifold.

Keywords : scalar-tensor theory, Newtonian physic

##  1 Comparisons with Newtonian gravity

The scalar-tensor theory first time was invented by P. Jordan [1] in the
1950’s, and then taken over by C. Brans and R.H. Dicke [2] some years later.
In this paper we restrict our discussion to the Brans-Dicke theory [1, 2]
that, among of all the alternative theories of classical Einstein’s gravity,
is the most studied and hence the best known theory.

Scalar-tensor theories of gravity describe the universe as grounded on
differentiable arbitrary manifold $M^{4}$ enveloped by a principal bundle
formed with isometric representations of a finite continuous Poincaré group.
Einstein’s principle of general relativity asserts the invariance under
general coordinate transformations of the actions integral grounded on a
$M^{4}$ manifold parameterized by variables $x^{\mu},\mu=0,1,2,3$.

As it is well known field equation and conservation low of the relativity
theory can be obtained from principle of least action. The same principle is
the basis of the Brans - Dicke theory 111Units $8\pi G=c=1$ are used
throughout the paper. Greek indices range over the coordinates of the
4-manifold and Roman indices over the coordinates of the 3-surfaces.

$S={S}_{G}+{S}_{m}$ (1) $S_{G}=\frac{1}{2}\int dx^{4}\sqrt{-g}\left\\{\Phi
R-\omega\frac{\Phi^{,\mu}\Phi_{,\mu}}{\Phi}\right\\}+{S}_{m},$ (2)

where $R$ is the scalar curvature, $\phi$ is a scalar field, $\omega$ is a
dimensionless coupling parameter, and ${S}_{m}$ is an action of ordinary
matter (not including the scalar field).

An unsatisfactory feature of relativistic theories is that the components of
Lagrangian do not have any direct physical interpretation. Note that in
abstract manifold, the Ricci scalar and tensor $g_{\mu\nu}$ lose their
geometrical meaning that they had in a spacetime and now can be viewed only as
a source for the metric.

The scalar - tensor theories appears as a theory in which the gravity is
described simultaneously by two fields the metric tensor and the scalar
fields, the latter being an essential part of the geometrical property of
spacetime manifesting its presence in all geometrical phenomena, such as
curvature, geodesic motion and so on.

On another hand, the Newtonian description of gravitating systems was
developed in the 17th century using a scalar potential field and is nowadays a
part of most classical mechanics textbooks. It seems reasonable to interpret
Newton s absolute space as an absolute Euclidean embedding-space that acts as
a container for non-Euclidean geometry. But there may be as well other reasons
to contemplate Minkowski space from considerations of scalar gravity.

In a gravity theories, a model of spacetime is usually a pair $(M,T)$ where
$M$ is $N$-dimensional manifold with suitable topological and differentiable
properties and $T$ represent a collection of matter fields on $M$. In approach
with fixed spacetime structure, like Newtonian mechanics and special
relativity, this model suggest an interpretation of manifold $M$ as
independently existing ”container” for the histories of fields and particles.
Obviously, the action (2) can be endowed with a structure of a manifold. To
obtain the physical interpretation of the scalar field, one may write the
action (2) for Minkowski metric in the following manner:
$g_{\mu\nu}=\eta_{\mu\nu},$ $R=0$. We need field equations for $\phi,$ so the
action (2) for this field must be supplied,

$S_{G}=\int dx^{4}\,\eta^{\mu\nu}\partial_{\mu}\phi\partial_{\nu}\phi,$ (3)

where $\phi=e^{\Phi}$. Without losing generality, suppose that $\omega=1$.

The overall action for the aggregate of N point particles is

$S_{m}=-\sum_{i=1}^{n}\int_{-\infty}^{\infty}\\!\\!\\!dt\,\frac{1}{2}m_{i}\dot{q}_{i}^{\mu}\dot{q}_{i}^{\nu}\eta_{\mu\nu}-\sum_{i=1}^{n}\int_{R^{4}}\\!\\!\\!dx\,m_{i}\delta(\textbf{x}-\textbf{q}_{i})\phi.$
(4)

where $q_{I}(t)=\\{q_{I}^{\mu}(t)\\},I=1,...,N$ are the trajectory of point
particles with mass $m_{I}$.

As in Newtonian mechanics, we can consider arbirtary spacelike section
$t=const$ given by Euclidean metric. The action (3) provides the following
field equations [3]:

$\frac{\delta S_{G}}{\delta\phi}=\triangle\phi=0,$ (5)

where $\triangle:=\partial_{1}^{2}+\partial_{2}^{2}+\partial_{3}^{2}$ is a
three dimensional Laplasian, the gradient of scalar field $\partial\phi$ is
taken at the point $q_{I}=\\{t,q_{I}^{\mu}\\}$, where at the time the particle
is located.

The field equations read

$\frac{\delta S}{\delta\phi}=\frac{1}{4\pi
G}\triangle\phi-\sum_{i}m_{\delta}(\textbf{x}-\textbf{q}_{i})=0,$ (6)

$\frac{\delta S}{\delta
q_{i}}=m_{i}\left(\ddot{q}_{i\mu}-\partial_{\mu}\phi\right)=0,$ (7)

Then, with this definition, the equation of gravity field have the form

$\triangle\phi=\sum_{I}m_{I}\delta(\textbf{x}-\textbf{q}_{I}).$ (8)

Thus, we see that the scalar field variables of Brans-Dicke theory play the
role of a standard Newtonian potential.

The field equation (8) yields the following solution [4]

$\phi(t,\textbf{x})=-\sum_{I}\frac{m_{I}}{|\textbf{x}-\textbf{q}_{I}(t)|},$
(9)

where

$|\textbf{x}-\textbf{q}_{I}|:=\sqrt{-\eta_{\mu\nu}(x^{\mu}-q_{I}^{\mu})(x^{\nu}-q_{I}^{\nu})}$
(10)

Now we consider the model with two particle with masses $m_{I}$ and $m_{J}$.
The force $F={F^{\mu}}$, acting on a particle $m_{I}$ by particle $m_{J}$, is

$F^{\mu}=m_{I}m_{J}\frac{q_{I}^{\mu}-q_{J}^{\mu}}{|\textbf{q}_{I}-\textbf{q}_{J}|^{3}}.$
(11)

_It is Newton’s law of gravitation._

##  2 Discussion

In order to make a physical prediction from theory a manifold must be endowed
with a structure (metric, connection, curvature …) In contrast with usual
formalism of general relativity one can perform a model of spacetime with
fixed background geometry, like Newtonian mechanics and special theory of
relativity. Then the set up of action implies the imposing the Ricci scalar
not as a scalar curvature of spacetime but as a matter source. The standard
derivation of the Newtonian gravity as a weak field limit of relativistic
theories do not expose the specific feature of Brans-Dicke theory which
include Newton s law of gravitation as an exact solution.

## References

  * [1] P. Jordan, Schwerkraft und Weltall, Vieweg (Braunschweig) 1955\.
  * [2] C.H.Brans , R. H.Dicke, Phys.Rev.124, 925 (1961).
  * [3] M.O.Katanaev, Geometrical methods in mathematical physics., arXiv:1311.0733v1 (2013).
  * [4] V.S.Vladimirov, Uravnenia matematicheskoi fiziki, Nauka, Moskow, 1988\. (Russian)