Amy F Smith

Myriam Peyrounette

Anne Larue

Vincent Doyeux

Yohan Davit

Sylvie Lorthois

Structural and hemodynamic comparison of synthetic and anatomical cerebral capillary networks

à la diffusion de documents scientifiques 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.

Open Archive TOULOUSE Archive Ouverte (OATAO)

OATAO is an open access repository that collects the work of Toulouse researchers and makes it freely available over the web where possible. This is an author-deposited version published in : http://oatao.univ-toulouse.

Abstract

A computational method is presented for generating 3D synthetic, random capillary networks which match the topological, geometrical and functional properties of the cerebral microcirculation. This enables production of larger capillary networks than can currently be extracted using high-resolution imaging modalities. These networks can then be coupled to lower-resolution data sets of whole-brain vasculature (capillaries unresolved) to model blood ow and mass transport, and to validate equivalent continuum/hybrid models. Another motivation is to reveal the dominant structural features of cerebral capillary networks, enabling us to tune these features to model di erent brain regions or pathological states such as Alzheimer's disease. Previous works (Linninger et al, Ann Biomed Eng, 2013; Su et al, Microcirc, 2012) lacked physiological basis, and although resulting networks conformed to expected global morphometric properties, they were not subjected to thorough topological or functional analysis. In contrast, our approach is based on the physiological assumption that the maximum separation of tissue cells from the nearest capillary is limited by the di usion distance of oxygen (Lorthois & Cassot, J Theor Biol, 2010). Previously, synthetic, space-lling 2D networks were constructed by placing one point randomly in each cell of an n × n grid; from this set of points, Voronoi diagrams were extracted with the edges producing a 2D capillary network with mainly three capillaries per vertex, a characteristic feature of cerebral capillary networks. Here, we present a 3D extension of this approach and compare the resulting structural and hemodynamic properties to those of anatomical cerebral capillary networks. In 3D, Voronoi diagrams produce polyhedrons with many capillaries at each vertex. To derive a network with only bifurcations, clusters of vertices were systematically merged and capillaries were then randomly removed. The resulting network structures were compared to capillary regions extracted from human and mouse anatomical data sets (Cassot et al, Microcirc, 2006;Tsai et al, J NeuroSci, 2009;Blinder et al, Nat Neurosci, 2013), showing excellent agreement. Geometrical metrics included the mean/S.D. of capillary lengths and edge/length/vertex densities. To measure the interconnected network topology, capillary loops were identi ed and the mean number of edges per loop, loop length, and number of loops per edge were compared. The spatial arrangement of capillaries was compared by studying the distribution of extravascular distances. Finally, the permeability was computed as a hemodynamic measure of blood ow conductivity.

  fr/ Eprints ID : 19264 To cite this version : Smith, Amy and Peyrounette, Myriam and Larue, Anne and Doyeux, Vincent and Davit, Yohan and Lorthois, Sylvie Structural and hemodynamic comparison of synthetic and anatomical cerebral capillary networks. (2017) In: Neuroscience 2017, 11 November 2017 -15 November 2017 (Washington D.C., United States). (Unpublished) Any correspondence concerning this service should be sent to the repository administrator: staff-oatao@listes-diff.inp-toulouse.fr Structural and hemodynamic comparison of synthetic and anatomical cerebral capillary networks Authors *A. SMITH, M. PEYROUNETTE, A. LARUE, V. DOYEUX, Y. DAVIT, S. LORTHOIS; Inst. De Mecanique Des Fluides De Toulouse, Toulouse, France Disclosures A. Smith: None. M. Peyrounette: None. A. Larue: None. V. Doyeux: None. Y. Davit: None. S. Lorthois: None.


Laure David

Frédéric Taieb

Marie Pénary

Pierre-Jean Bordignon

Rémi Planès

Salimata Bagayoko

Valérie Duplan-Eche

Etienne Meunier

Eric Oswald
email: eric.oswald@inserm.fr.

Outer membrane vesicles produced by pathogenic strains of Escherichia coli block autophagic flux and exacerbate inflammasome activation

Keywords: Outer Membrane Vesicle, Escherichia coli, HlyF, pathogenesis, autophagy, inflammasome AIEC: adherent-invasive E. coli BDI: Bright Detail Intensity BMDM: bone marrow-derived macrophages Casp: Caspase E. coli: Escherichia coli EHEC: enterohemorrhagic E. coli

Outer membrane vesicles produced by pathogenic strains of Escherichia coli block autophagic flux and exacerbate inflammasome activation

Escherichia coli strains are responsible for a majority of human extra-intestinal infections, resulting in huge direct medical and social costs. We had previously shown that HlyF encoded by a large virulence plasmid harbored by pathogenic E. coli is not a hemolysin but a cytoplasmic enzyme leading to the overproduction of outer membrane vesicles (OMVs). Here, we show that these specific OMVs inhibit the autophagic flux by impairing the autophagosome -lysosome fusion, thus preventing the formation of acidic autophagolysosome and autophagosome clearance. Furthermore, HlyFassociated OMVs are more prone to activate the non-canonical inflammasome pathway.

Since autophagy and inflammation are crucial in the host's response to infection especially during sepsis, our findings reveal an unsuspected role of OMVs in the crosstalk between bacteria and their host, highlighting the fact that these extracellular vesicles have exacerbated pathogenic properties.

Introduction

Although the majority of E. coli strains are commensal bacteria colonizing the digestive tract, some are pathogenic because they have acquired an arsenal of virulence factors that allow them to overcome innate or acquired defense mechanisms of their host [START_REF] Sarowska | Virulence factors, prevalence and potential transmission of extraintestinal pathogenic Escherichia coli isolated from different sources: recent reports[END_REF]. HlyF is a bacterial protein encoded by a gene present on a virulence plasmid found in strains of E. coli responsible for extraintestinal infection in both humans and animals [START_REF] Peigne | The Plasmid of Escherichia coli Strain S88 (O45:K1:H7) That Causes Neonatal Meningitis Is Closely Related to Avian Pathogenic E. coli Plasmids and Is Associated with High-Level Bacteremia in a Neonatal Rat Meningitis Model[END_REF]. More specifically, it is found in strains responsible for neonatal meningitis, avian colibacillosis [START_REF] Johnson | Identification of minimal predictors of avian pathogenic Escherichia coli virulence for use as a rapid diagnostic tool[END_REF][START_REF] Kim | Molecular characterization of avian pathogenic Escherichia coli from broiler chickens with colibacillosis[END_REF][START_REF] De Oliveira | Prevalence of ColV Plasmid-Linked Genes and In Vivo Pathogenicity of Avian Strains of Escherichia coli[END_REF] and more recently in an emerging serovar of enterohemorrhagic E. coli (EHEC) responsible for hemolytic and uremic syndrome in human [START_REF] Soysal | Enterohemorrhagic Escherichia coli Hybrid Pathotype O80:H2 as a New Therapeutic Challenge[END_REF]. The hlyF gene does not code for hemolysin as its name would suggest, but for a bacterial cytoplasmic protein that contributes to the bacterial virulence [START_REF] Murase | HlyF Produced by Extraintestinal Pathogenic Escherichia coli Is a Virulence Factor That Regulates Outer Membrane Vesicle Biogenesis[END_REF]. The HlyF protein displays a predicted catalytic domain of the short-chain dehydrogenase/reductase superfamily. This conserved domain is involved the ability of HlyF to promote the production of bacterial OMVs [START_REF] Murase | HlyF Produced by Extraintestinal Pathogenic Escherichia coli Is a Virulence Factor That Regulates Outer Membrane Vesicle Biogenesis[END_REF]. Noteworthy, HlyF protein is not detected in OMVs. OMVs are nanoparticles consisting of a lipid bilayer envelope including membranous proteins and LPS originating from the parental strain and containing luminal cargos [START_REF] Jan | Outer Membrane Vesicles (OMVs) of Gram-negative Bacteria: A Perspective Update[END_REF][START_REF] Schwechheimer | Outer-membrane vesicles from Gram-negative bacteria: biogenesis and functions[END_REF]. Similarly to eukaryotic exosomes and microvesicles, OMVs are a means of communication between bacteria and eukaryotic host cells [START_REF] Kuehn | Bacterial outer membrane vesicles and the host-pathogen interaction[END_REF][START_REF] Kulp | Biological Functions and Biogenesis of Secreted Bacterial Outer Membrane Vesicles[END_REF]. Interestingly, we have observed that eukaryotic cell treatment with culture supernatants of E. coli strains expressing HlyF induced LC3positive vesicles accumulation in host cells. At that time, we thought we were observing an exacerbation of autophagy and we interpreted this phenotype as related to the greater quantity of OMVs present in the supernatant [START_REF] Murase | HlyF Produced by Extraintestinal Pathogenic Escherichia coli Is a Virulence Factor That Regulates Outer Membrane Vesicle Biogenesis[END_REF].

Here, we show that extracellular vesicles from E. coli strains producing HlyF have exacerbated pathogenic properties compared to OMVs produced by isogenic strains unable to produce a functional HlyF. Our results revealed that these OMVs inhibit the autophagic flux and thus are more prone to promote the activation of the non-canonical inflammasome pathway, the main host defense mechanism against infections that must be tightly regulated to ensure a correct antimicrobial response [START_REF] Biasizzo | Interplay Between NLRP3 Inflammasome and Autophagy[END_REF][START_REF] Feng | The protective role of autophagy in sepsis[END_REF][START_REF] Ho | Autophagy in sepsis: Degradation into exhaustion?[END_REF][START_REF] Qiu | Review: the Role and Mechanisms of Macrophage Autophagy in Sepsis[END_REF]. Thus, these OMVs, produced by bacteria responsible of extraintestinal infections, could destabilize the host response to the infection, thus facilitating bacterial pathogenesis.

Results

OMVs from HlyF-expressing E. coli specifically induce an increase of LC3-positive vesicles numbers

In agreement with our previous results [START_REF] Murase | HlyF Produced by Extraintestinal Pathogenic Escherichia coli Is a Virulence Factor That Regulates Outer Membrane Vesicle Biogenesis[END_REF], bacterial expression of wild type (WT) HlyF is associated with an overproduction of OMVs (Fig. 1A). Moreover, HeLa cells treatment with culture supernatant of these HlyF WT strains induces an increase of LC3-positive structures number in host cells, as denoted by vesicles-associated LC3 foci (Fig. 1B). To take into account a dose effect due to overexpression of OMVs in bacteria producing HlyF, eukaryotic cells were then treated with the same number of purified OMVs from isogenic E. coli strains expressing or not HlyF. To do so, we analyzed OMVs by transmission electron microscopy (TEM) and checked that the concentration of OMVs is correlated to protein concentration (data not shown). At the same concentration, only OMVs from the wild type strain expressing HlyF specifically induce an increase of LC3-positive structures number in host cells (Fig. 1C). We repeated these experiments using the same amount of OMVs purified from the laboratory E. coli strain BL21(DE3) devoid of virulence factors and flagellin, expressing wild-type or inactivated HlyF (Suppl. Fig 1A). OMVs were analyzed by TEM (Fig. 1D), but also by dynamic light scattering (Suppl. Fig. 1B) and we performed protein and LPS dosages (Suppl. Fig. 1C) to refine their characterization. These results showed that OMVs produced from both strains expressing active and inactive HlyF have a similar diameter (25.95nm +/-4.91 and 24.5nm +/-4.86 respectively) and comparable concentration of protein and LPS per vesicle. The increase of LC3-GFP-associated LC3positive foci (Fig. 1E) as well as the significant increase of LC3-II level (Fig. 1F-G) confirmed the specific HlyF-dependent increase of LC3-positive structures number following cell treatment with OMVs from BL21-producing wild type HlyF.

Increased LC3-positive vesicles numbers induced by OMVs from HlyF-expressing E. coli is dosedependent

To quantify the number of LC3-positive foci per cell, we counted the fluorescently labelled GFP-LC3 puncta per cell using the imaging flow cytometry technology (ImageStreamX system -ISX) [START_REF] Pugsley | Quantifying autophagy: Measuring LC3 puncta and autolysosome formation in cells using multispectral imaging flow cytometry[END_REF]. The quantification of dots of GFP-LC3 per cell shows that OMVs HlyF WT treatment induces a 5fold increase of LC3-positive structures in eukaryotic cells compared to non-treated cells (Fig. 2A -B). We also showed that the accumulation of LC3-positive structures increases substantially with the concentration of OMVs HlyF WT until it reaches a plateau from a concentration of 4µg/mL of OMVs (Fig. 2C-D). A dose effect showed that no matter how much OMVs of the non-HlyF producing strain are put on the HeLa cells, no LC3-positive structures accumulation is ever observed (Fig. 2C-D). Finally, measurement of the level of LC3-II at different time points in HeLa cells showed that autophagosome increase in HeLa cells lasted at least 72 hours after the beginning of OMV HlyF WT treatment (Suppl. Fig. 2).

OMVs from HlyF-expressing E. coli triggers the specific accumulation of autophagosomes in host cells

Accumulation of LC3-positive structures in eukaryotic cells following OMVs treatment could result from an accumulation of autophagosomes or from LC3-associated phagocytosis vesicles (LAP). To distinguish between these two types of vesicles, we first observed that OMVs were not sequestered inside the LC3-positive vesicles, as there is no co-localization between GFP-LC3 structures and OMV stained with DiI (Fig. 3A), suggesting that the accumulation of LC3-positive structures does not result from LAP and the phagocytosis of OMVs prior to their degradation but from autophagosomes. We confirmed this result by transmission electron microscopy analysis of Hela cells treated by OMVs, in which we observed the accumulation of double-membrane vesicles, indicative of autophagosome, rather than single-membrane vesicle of LAP (Fig. 3B).

OMVs from HlyF-expressing E. coli induce an autophagic blockade

Autophagy is a dynamic process in which the number of autophagosomes depends on their formation and further degradation. This is referred as autophagic flux. Thus, OMV-dependent accumulation of autophagosomes could result either from an increased synthesis of autophagosomes or from a decreased degradation following their fusion with lysosomes (Fig. 4A) [START_REF] Mizushima | Methods in mammalian autophagy research[END_REF][START_REF] Muñoz-Braceras | Analysis of Relevant Parameters for Autophagic Flux Using HeLa Cells Expressing EGFP-LC3[END_REF]. To decipher the cellular basis of increase of autophagosomes number after OMV treatment, we monitored the level of autophagosomes-associated LC3-II in HeLa cells. As expected, LC3-II level increased when lysosomal-dependent LC3-II degradation is blocked by the lysosomal inhibitor chloroquine. However, these levels were comparable in cells treated with OMVs in presence of chloroquine (Fig. 4B, lines 2 and 4, quantified in Fig. 4C). Absence of cumulative effect of OMVs and chloroquine on LC3-II level suggests that OMVs HlyF WT induce an autophagy blockade in HeLa cells similarly to chloroquine treatment. These results were confirmed by quantification of GFP-LC3 cells treated by OMVs HlyF WT in presence or absence of chloroquine by imaging flow cytometry.

We observed that the number of GFP-LC3 fluorescent dots in OMV-treated cells is not further increased by chloroquine which would have been the case if the autophagic flux had been stimulated (Fig. 4D-E). Altogether, these results showed that OMVs HlyF WT treatment induces an autophagic blockade in eukaryotic cells rather than an induction of the flux.

OMVs from HlyF-expressing E. coli prevents the autophago-lysosome fusion and autophagosomes clearance.

To characterize which step of the autophagy pathway was inhibited, we used the HeLa-Difluo hLC3 cell line. These cells express a fusion protein RFP::GFP::LC3, in which the N-terminus of LC3 is fused to two fluorescent reporter proteins: an RFP (acid-stable) and a GFP (acid-sensitive). Autophagosomes that contain intact RFP::GFP::LC3 proteins emit both RFP and GFP signals resulting in a co-localization of GFP-and RFP-positive puncta. After fusion of the autophagosomes with the lysosomes, the GFP fluorescence diminishes due to the acidification of the autophagolysosome, while the red fluorescence corresponding to the remaining acidic -resistant RFP-LC3 signal is maintained [START_REF] Kimura | Dissection of the autophagosome maturation process by a novel reporter protein, tandem fluorescent-tagged LC3[END_REF][START_REF] Loos | Defining and measuring autophagosome fluxconcept and reality[END_REF]. We performed confocal imaging of HeLa-Difluo hLC3 cells. As expected, in the control condition treated with lysosomal inhibitor chloroquine, we observed an accumulation of colocalization of GFP-and RFP-positive puncta corresponding to autophagosomes harboring GFP and RFP LC3. When cells were starved with HBSS, known to induce the autophagic flux, a proportion of GFP fluorescence was decreased by the acidic pH environment while acid-resistant red fluorescence persisted, denoting that fusion of autophagosome with lysosome occurred in these cells. In contrast, in cells treated with OMVs HlyF WT, we observed an increased number of co-localization of GFP-and RFP-positive puncta and absence of red-fluorescent-associated autophagolysosome, indicating that the autophagic blockade occurs before the acidification of the autophagosomal compartments (Fig. 5A).

To confirm this result, we quantified the level of fluorescently labeled RFP and GFP LC3 in HeLa-Difluo hLC3 by imaging flow cytometry. In contrast to starvation but similarly to chloroquine treatment, we observed that in cells treated by OMVs the ratio RFP/GFP was low, indicating that the GFP is preserved from autophagosome acidification (Fig 5B-C).

Finally, we stained acidic organelles in GFP-LC3 cells with LysoTracker Red labeling. We checked that upon starvation, GFP-LC3 Hela cells harbored co-localization of GFP-and RFP-positive puncta (highlighted by white arrows) resulting from the co-localization of autophagosomes and lysosomes merged signals. In contrast, absence of co-localization of GFP-and RFP-positive puncta indicated that OMVs HlyF WT treatment of GFP-LC3 HeLa cells prevented lysosomal acidification of autophagosomes (Fig. 5D). These results showed that autophagy flux is blocked by OMV at lysosomal fusion step. Moreover, persistance of signal corresponding LC3-II up to 72hr after OMV addition (suppl. Fig. 2) supports that autophagosomal clearance is inhibited.

OMVs from HlyF-expressing E. coli induce a stronger activation of the non-canonical inflammasome pathway compared to OMVs from E. coli expressing a non-functional HlyF protein.

Numerous studies showed that autophagy is a negative regulator that prevents excessive activation of inflammasomes [START_REF] Biasizzo | Interplay Between NLRP3 Inflammasome and Autophagy[END_REF][START_REF] Deretic | Autophagy in infection, inflammation and immunity[END_REF][START_REF] Harris | Autophagy and inflammasomes[END_REF][START_REF] Krakauer | Inflammasomes, Autophagy, and Cell Death: The Trinity of Innate Host Defense against Intracellular Bacteria[END_REF][START_REF] Netea-Maier | Modulation of inflammation by autophagy: Consequences for human disease[END_REF][START_REF] Qian | Inflammasome and Autophagy Regulation: A Twoway Street[END_REF][START_REF] Saitoh | Loss of the autophagy protein Atg16L1 enhances endotoxin-induced IL-1beta production[END_REF][START_REF] Shi | Activation of autophagy by inflammatory signals limits IL-1β production by targeting ubiquitinated inflammasomes for destruction[END_REF]. We checked that OMVs HlyF WT cause a substantial autophagosomes accumulation in bone marrow-derived macrophages (BMDM) cells (Suppl. Fig. 3A-B) and in the THP1 cell line (Suppl. Fig. 3C-D). We therefore speculated that OMV-dependent inhibition of autophagic flux could exacerbate inflammasome activation. OMV-treatment of unprimed BMDM from wild type mice led to cell death (measured by lactase dehydrogenase (LDH) release) and to the excretion of mature IL-1β in the supernatant of cell culture. Importantly, these phenotypes were significantly exacerbated when BMDM were treated with OMVs HlyF WT compared to OMVs produced in bacteria expressing inactive HlyF. These phenotypes were dependent of the activation of the non-canonical inflammasome pathway since they are abolished in inflammasome-deficient BMDM invalidated for caspase 11, caspase 1/11 or gasdermin D (Fig. 6A). Furthermore, we deciphered the impact of autophagic blockage on the inflammasome activation following OMV treatment, using 2 different autophagic inhibitors (wortmannin and bafilomycin). As expected, autophagic inhibition alone does not activate the inflammasome machinery. Interestingly, we observed that autophagic inhibition by bafilomycin and wortmannin abolished the autophagic negative feedback loop and thus, restored the overactivation of the inflammasome in OMV HlyF Mut treated cells to the level of OMV HlyF WT treated BMDM (Fig. 6B-C).

In accordance with the literature, these results suggest that the specific exacerbation of the noncanonical inflammasome pathway activation induced by OMVs HlyF WT treatment was due to their ability to block the autophagic flux [START_REF] Biasizzo | Interplay Between NLRP3 Inflammasome and Autophagy[END_REF][START_REF] Deretic | Autophagy in infection, inflammation and immunity[END_REF][START_REF] Harris | Autophagy and inflammasomes[END_REF][START_REF] Krakauer | Inflammasomes, Autophagy, and Cell Death: The Trinity of Innate Host Defense against Intracellular Bacteria[END_REF][START_REF] Netea-Maier | Modulation of inflammation by autophagy: Consequences for human disease[END_REF][START_REF] Qian | Inflammasome and Autophagy Regulation: A Twoway Street[END_REF][START_REF] Saitoh | Loss of the autophagy protein Atg16L1 enhances endotoxin-induced IL-1beta production[END_REF][START_REF] Shi | Activation of autophagy by inflammatory signals limits IL-1β production by targeting ubiquitinated inflammasomes for destruction[END_REF]. Finally, since activation of the non-canonical inflammasome pathway is related to the sensing of LPS through host guanylate-binding proteins in the cytosol [START_REF] Santos | LPS targets host guanylate-binding proteins to the bacterial outer membrane for non-canonical inflammasome activation[END_REF], we transfected purified LPS from OMVs HlyF WT and from OMVs HlyF Mut directly into the cytosol of BMDM. We observed that the activation of the non-canonical inflammasome pathway, measured by cell death and IL-1β release, was similar regardless of the LPS transfected (Fig. 6D). This result suggests that the overactivation of the non-canonical inflammasome pathway does not depend on LPS difference but rather results from OMV HlyF WT ability to block the autophagy.

Discussion

In this study, we confirmed that pathogenic E. coli strains harboring a virulence plasmid coding for hlyF overproduce OMVs that modulate autophagy [START_REF] Murase | HlyF Produced by Extraintestinal Pathogenic Escherichia coli Is a Virulence Factor That Regulates Outer Membrane Vesicle Biogenesis[END_REF]. However, we showed that this modulation was due to an autophagic blockage instead of an induction of the flux as initially thought [START_REF] Murase | HlyF Produced by Extraintestinal Pathogenic Escherichia coli Is a Virulence Factor That Regulates Outer Membrane Vesicle Biogenesis[END_REF]. Moreover, we demonstrated that OMVs HlyF WT block autophagosome maturation and fusion with lysosomes and inhibit their clearance from host cytosol. Autophagy is recognized as an innate antibacterial mechanism by direct lysosomal degradation of intracellular pathogen. After engulfment of the cytosolic pathogen, autophagosomes fuse with lysosomes, leading to degradation of the sequestered content [START_REF] Netea-Maier | Modulation of inflammation by autophagy: Consequences for human disease[END_REF]. Thus, autophagy that is crucial to maintain cellular homeostasis, acts also as the first line of host defense against bacterial pathogen as it fights against the intruder very early during infection [START_REF] Losier | AMPK Promotes Xenophagy through Priming of Autophagic Kinases upon Detection of Bacterial Outer Membrane Vesicles[END_REF]. It has been shown recently that some ExPEC strains hijack the host autophagy machinery to promote their intracellular survival and replication in macrophages [START_REF] Zhuge | A Novel PhoP/PhoQ Regulation Pathway Modulates the Survival of Extraintestinal Pathogenic Escherichia coli in Macrophages[END_REF]. This ability is due to the inhibition of the fusion of ExPEC-containing phagosomes with lysosomes and their subsequent degradation [START_REF] Zhuge | A Novel PhoP/PhoQ Regulation Pathway Modulates the Survival of Extraintestinal Pathogenic Escherichia coli in Macrophages[END_REF]. This observation is consistent with the properties we demonstrated here, i.e. OMVs preventing the phagolysosomal fusion and acidification in macrophages. In line with this idea, the fact that the adherent-invasive E. coli (AIEC) reference strain NRG 857Cc harbors the hlyF gene suggests that OMVs actively participate in the virulence of these pathogenic bacteria by favoring their survival and their replication into eukaryotic cells [START_REF] Mcphee | Host Defense Peptide Resistance Contributes to Colonization and Maximal Intestinal Pathology by Crohn's Disease-Associated Adherent-Invasive Escherichia coli[END_REF]. Pathogenic bacteria could exploit HlyF OMV property to block their autophagosomal clearance into epithelial cells and macrophages.

Thus, the contribution of OMVs produced by HlyF-expressing E. coli to bacterial virulence includes autophagic blockage but also the dissemination and delivery of their virulence factors potentially far from the source of infection, directly into the cytoplasm of target cells. In line with this idea, OMVs play a very important role in mediating the cytosolic localization of lipopolysaccharide (LPS), an endotoxin that is present at their surface. Once in the host cytosol, LPS is recognized by the noncanonical inflammasome machinery and thereby activates an inflammatory immune response [START_REF] Kaparakis-Liaskos | Immune modulation by bacterial outer membrane vesicles[END_REF][START_REF] Santos | LPS targets host guanylate-binding proteins to the bacterial outer membrane for non-canonical inflammasome activation[END_REF][START_REF] Vanaja | Bacterial Outer Membrane Vesicles Mediate Cytosolic Localization of LPS and Caspase-11 Activation[END_REF]. However, excessive inflammation activation by LPS can be deleterious for the host. The inflammatory burst they cause can also lead to organ dysfunction which can worsen up to sepsis in severe cases [START_REF] Chen | Noncanonical inflammasome signaling elicits gasdermin D-dependent neutrophil extracellular traps[END_REF][START_REF] Schroder | Mechanisms and Consequences of Inflammasome Activation[END_REF]. At the early stage of sepsis, macrophages release large amounts of proinflammatory molecules that exacerbate inflammatory response. It is then followed by an immunosuppression due to the massive apoptosis of macrophages, which makes host susceptible to recurrent infections [START_REF] Cecconi | Sepsis and septic shock[END_REF][START_REF] Van Der Poll | The immunopathology of sepsis and potential therapeutic targets[END_REF]. The role of OMVs in sepsis is highlighted by the fact that injection of OMVs alone in mice recapitulates sepsis-associated exacerbated inflammation and mortality [START_REF] Eren | Irgm2 and Gate-16 cooperatively dampen targeting of caspase-11 to Gram-negative bacterial products[END_REF]. Thus, this inflammation machinery initiated by OMV recognition must be tightly regulated. Here, we show that OMV HlyF WT provoke an exacerbated activation of the non-canonical inflammasome activation and IL-1β release, one of the main mechanisms through which innate and adaptive immune responses are induced by an infection [START_REF] Eren | Irgm2 and Gate-16 cooperatively dampen targeting of caspase-11 to Gram-negative bacterial products[END_REF][START_REF] Gomes | Autophagy in antimicrobial immunity[END_REF][START_REF] Schroder | Mechanisms and Consequences of Inflammasome Activation[END_REF]. We showed that not only OMVs HlyF WT induces inflammation actions, they also block autophagy, a major negative regular of excessive inflammation activation and IL-1β release (Crişan et al., 2011;[START_REF] Saitoh | Loss of the autophagy protein Atg16L1 enhances endotoxin-induced IL-1beta production[END_REF]. In particular, autophagy induction prevents the onset of sepsis [START_REF] Biasizzo | Interplay Between NLRP3 Inflammasome and Autophagy[END_REF]. This negative regulation mainly relies through effects on the secretion of immune mediators and on the removal of endogenous inflammasome agonists such as PAMPs [START_REF] Deretic | Autophagy in infection, inflammation and immunity[END_REF][START_REF] Harris | Autophagy and inflammasomes[END_REF][START_REF] Krakauer | Inflammasomes, Autophagy, and Cell Death: The Trinity of Innate Host Defense against Intracellular Bacteria[END_REF][START_REF] Netea-Maier | Modulation of inflammation by autophagy: Consequences for human disease[END_REF][START_REF] Qian | Inflammasome and Autophagy Regulation: A Twoway Street[END_REF]. Therefore, not only OMVs favor intracellular delivery of LPS and PAMPs into cells but inhibition of autosomal clearance of these inflammasome activators by OMV HlyF WT impairs inflammasome negative feedback control, leading to an excessive and uncontrolled inflammatory condition detrimental for the host.

Our study unravels the mechanisms by which HlyF expression by E. coli confers hyper-virulent properties to OMVs, as they gain the property to manipulate the host cell autophagic and inflammatory responses to bacterial benefit both at the site and at great distance from the site of infection. An additional contribution of OMVs HlyF to bacterial virulence could be associated to the dissemination of toxins [START_REF] Bielaszewska | Host cell interactions of outer membrane vesicle-associated virulence factors of enterohemorrhagic Escherichia coli O157: Intracellular delivery, trafficking and mechanisms of cell injury[END_REF][START_REF] Murase | HlyF Produced by Extraintestinal Pathogenic Escherichia coli Is a Virulence Factor That Regulates Outer Membrane Vesicle Biogenesis[END_REF]. Overall, OMVs HlyF contribute significantly to the virulence of pathogenic bacteria.

Materials and methods

Bacterial strains and growth conditions

SP15 is an extra-intestinal pathogenic E. coli (ExPEC) strain isolated from a neonatal meningitis case [START_REF] Johnson | Phylogenetic distribution of virulence-associated genes among Escherichia coli isolates associated with neonatal bacterial meningitis in the Netherlands[END_REF]. SP15, SP15∆hlyf and SP15∆hlyfGST-hlyF were previously described in [START_REF] Murase | HlyF Produced by Extraintestinal Pathogenic Escherichia coli Is a Virulence Factor That Regulates Outer Membrane Vesicle Biogenesis[END_REF]. pGEX6P-1 plasmids expressing GST-HlyF protein wild type or inactivated by a mutation on its putative catalytic site (Suppl. Fig. 1A) were transformed in E. coli BL21(DE3) strain. SP15 and BL21(DE3) strains and derivatives were inoculated and grown in Terrific Broth with appropriate antibiotics for 8hr at 37°C with agitation.

Purification of bacterial OMVs

After 8hr of culture the bacterial suspension was centrifuged at 6500g for 10min at 4°C. The supernatant was filtered (pore size 0.45μm) to obtain bacterial-free supernatant. The filtered supernatant was ultrafiltered and concentrated using tangential concentrator and PES membrane cassette (pore size, 100kDa, Sartorius) and ultracentrifuged at 150,000g for 1.5hr at 4°C. After removing the supernatant, pelleted OMV were resuspended in sterile PBS with Ca 2+ and Mg 2+ and stored at 4°C. To visualize the concentration of OMVs and the purity of the preparation, negative staining transmission electron microscopy (TEM) was performed according to standard procedures. The concentration of OMVs in the suspension correlates with protein concentration evaluated by BCA protein assay (DC TM protein assay Biorad) (Suppl. Fig. 1C). LPS concentration in OMV was evaluated by Purpald assay as described in [START_REF] Lee | Quantification of bacterial lipopolysaccharides by the purpald assay: measuring formaldehyde generated from 2-keto-3-deoxyoctonate and heptose at the inner core by periodate oxidation[END_REF]. Values were normalized to glycerol concentration. OMV diameter was calculated by dynamic light scattering using Zetasizer Nano instrument (Malvern) (Suppl. Fig. 1B).

OMVs in PBS were fluorescently labeled using 1% (v/v) DiI (Thermofisher) for 30 min at 37°C.

Purification and transfection of LPS from OMVs

LPS was extracted from purified OMV using LPS extraction kit (iNtRON Biotechnology) according to manufacturer's instruction. LPS concentration was determined by Purpald assay as described in [START_REF] Lee | Quantification of bacterial lipopolysaccharides by the purpald assay: measuring formaldehyde generated from 2-keto-3-deoxyoctonate and heptose at the inner core by periodate oxidation[END_REF]. Transfection of cells with purified LPS was done at a concentration of 500ng/50,000 cells, using FuGeneHD (Promega) transfection reagent in Opti-MEM, as previously described [START_REF] Santos | LPS targets host guanylate-binding proteins to the bacterial outer membrane for non-canonical inflammasome activation[END_REF].

Eukaryotic cell culture and treatments

HeLa cells, HeLa-LC3-GFP cells and HeLa-Difluo hLC3 cells (Invivogen) were cultured in DMEM with Glutamax (Sigma) supplemented with 10% fetal bovine serum (FBS). HeLa-Difluo hLC3 cells were maintained in growth medium supplemented with the selection antibiotic Zeocin 200µg/mL (Invivogen). One day before the experiment, HeLa cells were seeded at a density of 5 × 10 4 cells per mL in DMEM supplemented with 10% FBS. OMV treatment were done by adding directly in the medium of cell culture the volume of OMV corresponding to the amount of proteins indicated. The cells were collected 3h after OMV addition. THP1 cells were cultured in RPMI with Glutamax (Sigma) supplemented with 10% FBS. One day before the experiment, THP1 cells were seeded at a density of 3 x 10 5 cells per mL. OMV treatment were done by adding directly in the medium of cell culture the volume of OMV corresponding to the amount of proteins indicated. The cells were collected 3h after OMV addition.

Bone marrow-derived macrophages (BMDM) were prepared from fresh bone marrow isolated from WT, Caspase 11 -/-, Caspases 1 -/-/11 -/-or Gasdermin D -/-deficient mice. Bone marrow cells were allowed to differentiate in macrophages by incubation for 7 days in DMEM supplemented with 10% fetal calf serum (Bioconcept), 25ng/ml M-CSF (Immunotools), 10mM HEPES, and nonessential amino acids (Life Technology). One day before treatment, BMDM were seeded into 24 well plates at a density of 2.5 × 10 5 cells per well. OMV treatment, were done by adding the volume of OMV corresponding to the amount of proteins indicated in Opti-MEM medium. The cells and supernatant were collected 24hr after OMV addition.

Immunoblotting

Cells were treated with the OMV or left untreated for the indicated times. Then cells were washed twice with cold PBS, lysed in NuPAGE LDS sample buffer with reducing agent (Invitrogen) and sonicated. Cell extracts were boiled for 5min at 95°C, separated by SDS-PAGE and transferred to PVDF membranes (Invitrogen). The membranes were blocked in 5% BSA in 0.1% Tween-20 in TBS and probed with primary antibodies. The primary antibodies used were Rabbit anti-LC3 (Cell Signaling S 3868), Mouse anti-actin (Abcam Ab 3280). After incubation with Goat anti-Rabbit and Goat anti-Mouse HRPconjugated secondary antibodies (Promega), proteins were visualized using chemiluminescent peroxidase substrat detection reagents (Sigma), and acquired by the ChemiDoc XRS+ System (BioRad). Densitometric analyses of immunoblots were performed using the ImageJ software.

Fluorescence microscopy

GFP-LC3 HeLa cells or HeLa-Difluo hLC3 cells were seeded onto Nunc Lab-Tek Chamber Slide system 8 wells (Sigma). The day of the experiment, cells were incubated with the indicated treatment or left untreated for the indicated times. LysoTracker Red (Invitrogen) staining was achieved by adding the Lysotracker probe at a final concentration of 50nM directly in the medium of cell culture for 1hr. Then the cells were washed and fixed with 4% paraformaldehyde for 15min on ice. DNA was visualized using Fluoroshield with 4,6-diamidino-2-phenylindole (DAPI, Sigma). Images were acquired using a Zeiss LSM 710 confocal microscope and subsequently processed using the ImageJ software package.

Transmission electron microscopy

Negative staining TEM for OMV was performed according to standard procedures. Briefly, 5µL of OMV samples were added to carbon coated copper mesh grid and stained with 1% uranyl acetate for 1 minute and imaged with Jeol JEM-1400 transmission electon microscope. For Hela cells ultrastructure visualization, cells were cultured on 6-well plates at a density of 1,5 × 10 6 cells/well one day prior to the experiment. After OMV treatment, cells were fixed with final concentrations of 2.5% glutaraldehyde / 2% paraformaldehyde in 0.1M Sorensen buffer (pH 7.2) volume/volume in the culture medium for 15 minutes at room temperature. After this primary fixation, the cells were secondarily fixed with 2.5% glutaraldehyde / 2% paraformaldehyde in 0.1M Sorensen buffer (pH 7.2) for 1.15 hr at room temperature. Then cells were rinsed three times in Sorensen buffer for 10 min each time and let in Sorensen buffer with 1% paraformaldehyde at 4°C until they were then scraped off, pelleted, concentrated in agarose, and treated for 1 h with 2% aqueous uranyl acetate. The samples were then dehydrated in a graded ethanol series and embedded in Epon. After 48 h of polymerization at 60 °C, ultrathin sections (80 nm thick) were mounted on 200 mesh Formvar-carbon-coated copper grids. Finally, sections were stained with Uranyless and lead citrate. Grids were examined with a TEM (Jeol JEM-1400, JEOL Inc, Peabody, MA, USA) at 80 kV. Images were acquired using a digital camera (Gatan Orius, Gatan Inc, Pleasanton, CA, USA) and subsequently processed using the ImageJ software package.

Measurement of LDH release

Cell death was quantified by measuring LDH release, using the CyQUANT TM LDH Cytotoxicity Assay (Invitrogen). To normalize for spontaneous cell lysis, the percentage of cell death was calculated as follows: [(LDH sample) -(LDH non-treated control)] / [(LDH positive control) -(LDH non-treated control)] X 100.

Measurement of IL-1β release

Quantification of IL-1β secretion in cell supernatant was measured by ELISA (Invitrogen, IL-1 beta Mouse Uncoated ELISA Kit, # 88-7013-88), according to the manufacturer's instructions.

Imaging Flow Cytometry

GFP-LC3 HeLa cells or HeLa Difluo hLC3 cells were incubated with the indicated treatment or left untreated for the indicated times. Then the cells were washed, trypsinized, fixed with 4% paraformaldehyde for 15min on ice. Image of each cell was acquired while they were run on the ImageStreamX Mark II (Amnis-EMD Millipore) at 5 × 10 7 cells per mL in PBS. In each experiment 5,000 (GFP+) events per sample were acquired (ensuring a sufficient number of events remaining for statistically robust analysis) at 60X magnification. Single stain samples were also collected using the same settings and used as compensation controls to generate compensation matrix.

Image analysis was completed using image-based algorithms in the ImageStream Data Exploration and Analysis Software (IDEAS_6.2.64.0, EMD Millipore). The number of GFP-LC3 puncta per cell was assessed with the feature "Spot Counting". A mask based on GFP-LC3 staining was employed (SpotCount (M02, LC3, Bright, 16, 2, 1)) to visualize the GFP-LC3 puncta. A feature in the IDEAS software called Bright Detail Intensity R7 (BDI) was used to assess the intensity of bright spots in the cell image that have radii smaller than a threshold size (7 pixels in this study), while neglecting background staining. The ratio of BDI RFP/ BDI GFP brightness was thus assessed. The same mask and feature were automatically applied for each condition.

Figure 1 .

 1 Figure 1. Increased LC3-positive structures numbers in epithelial cells treated by OMVs from E. coli producing HlyF. (A) Images of purified OMVs with equivalent volumes from wild type SP15 (SP15 WT) and from SP15ΔhlyF visualized by negative staining transmission electron microscopy (TEM). Scale bar = 100nm. Images representative of 3 independent experiments. (B-C) Images of confocal microscopy of LC3-GFP (green) and DAPI (blue) in LC3-GFP-Hela cells treated 3hr with supernatant from wild type SP15 (SP15 WT) and SP15ΔhlyF 250µL/mL after ultrafiltration (B) or with purified OMV with equivalent protein dosage from wild type SP15 (SP15 WT) 10µg/mL, SP15ΔhlyF 10µg/mL and SP15ΔhlyFGST-HlyF 1µg/mL (C). Scale bar = 10µm. Images representative of 3 independent experiments. (D) Images of purified OMVs with equivalent protein dosage from BL21 expressing HlyF WT or inactivated (Mut) visualized by negative staining TEM. Scale bar = 100nm. Images representative of 3 independent experiments. (E) Images of confocal microscopy of LC3-GFP (green) and DAPI (blue) in LC3-GFP-Hela cells treated 3hr with OMV BL21 HlyF WT or OMV BL21 HlyF Mut 5µg/mL. Scale bar = 10µm. Images representative of 3 independent experiments. (F) Western blot analysis of LC3 and actin in cell extracts of Hela cells treated 3hr with OMV from BL21 HlyF WT and OMV BL21 HlyF Mut 5µg/mL. Experiment reproduced 3 times independently. (G) Quantification of the LC3B-II/actin ratios of the Fig. 1F obtained by densitometric analysis of 3 independent experiments. The graph shows the mean and the standard deviation for each condition. ** p<0,01 and *p<0,05 t test.

Figure 2 .

 2 Figure 2. OMVs-induced increase of LC3-positive structures numbers is dose-dependent. (A) Images acquired by ISX of GFP-LC3 HeLa cells treated 3hr with OMV from BL21 HlyF WT 5µg/mL. On the left panel, brightfield channel (BF) images the cells according to their size and morphology; on the right panel, LC3 channel images cells according to their fluorescence in GFP-LC3 in green. Number of LC3 green dots of LC3-GFP per cell is indicated in blue in the dial at the top right of the BF channel. The mask is shown in red on the BF. Scale bars = 7µm. Images representatives of 4 independent experiments. (B) Quantification of (A). Number of LC3 green dots of LC3-GFP per cell counted with the Spot count function is indicated on the vertical axis on a minimum of 3000 cells per condition. Each square represents a cell image acquired by ISX. The graphs show the mean for each condition. ****p<0.0001 t test. Graph representative of 4 independent experiments. (C) Hela cells were treated with increasing concentrations of OMVs from BL21 HlyF WT for 3hr then LC3 and actin were analyzed by western blot. Experiment reproduced 3 times independently. (D) Quantification of the LC3B-II/actin ratios of the Fig. 2C obtained by densitometric analysis of 3 independent experiments. The graph shows the mean and the standard deviation for each condition.

Figure 3 .

 3 Figure 3. OMVs HlyF WT triggers the specific accumulation of autophagosomes in host cells. (A) Confocal images of LC3-GFP (green) and fluorescently labelled OMVs with DiI (Red) fluorescence in LC3-GFP Hela cells. The cells were incubated with OMVs from BL21 HlyF WT 5µg/mL for 3hr. 100 cells were analyzed per condition. Scale bar = 10µm. Images representative of 3 independent experiments. (B) Ultrastructure of Hela cells visualized by TEM. The cells were incubated with OMVs from BL21 HlyF WT or from BL21 HlyF Mut 5µg/mL for 3hr. 15 cells were analyzed per condition. Scale bar = 1µm (upper panel) and scale bar = 500nm (bottom panel). Arrows indicate double-membrane autophagosomes. The bottom images are a magnification of the part of the top images within the rectangles.

Figure 4 .

 4 Figure 4. Autophagy flux is blocked by OMVs HlyF WT. (A) Schema of the autophagic flux and of the accumulation of different autophagic structures depending on the autophagic dynamic regulation (adapted from Mizushima et al., 2010). (B) Hela cells were treated with OMVs from BL21 HlyF WT 5µg/mL and/or 50μM chloroquine for 3hr before LC3 and actin western-blot analysis. Experiment reproduced 3 times independently. (C) Quantification of the LC3B-II/actin ratios of the Fig. 4B obtained by densitometric analysis of 3 independent experiments. The graph shows the mean and the standard deviation for each condition. **p = 0.0097 t test, n.s. = non-significant. (D) LC3-GFP Hela cells were treated with OMVs from BL21 HlyF WT 5µg/mL and/or 50μM chloroquine for 3hr before ISX analysis. On the left panel, brightfield channel (BF) images; on the right panel, LC3 channel image cells according to their fluorescence in GFP-LC3 in green. Scale bars = 7µm. Images representatives of 3 independent experiments. (E) Quantification of (C). Number of LC3 green dots of LC3-GFP per cell counted with the Spot count function is indicated on the vertical axis, on a minimum of 3000 cells per condition. Each square represents a cell image acquired by ISX. The graphs show the mean for each condition. Experiment reproduced 3 times independently, ****p<0.0001 t test.

Figure 5 .

 5 Figure 5. Autophagy flux blocked by OMVs HlyF WT at lysosomal fusion step. (A) Confocal images of DiFluo Hela cells deprived with HBSS or treated for 3hr with 50μM chloroquine or with OMVs from BL21 HlyF WT 5µg/mL. Images of LC3-GFP fluorescence (green), LC3-RFP fluorescence (red), and the overlay with DAPI (blue) which shows co-localization of GFP-and RFP-positive puncta. Scale bar = 10µm. 50 cells were analyzed per condition. Images representative of 3 independent experiments. (B) Images acquired by ISX of DiFluo Hela cells deprived with HBSS or treated for 3hr with 50μM chloroquine or with OMVs from BL21 HlyF WT 5µg/mL. On the left panel, brightfield channel (BF), on the medium panel, LC3-GFP channel images cells according to their fluorescence in GFP in green and on the right panel LC3-RFP channel images cells according to their fluorescence in RFP in red. Scale

Figure 6 .

 6 Figure 6. OMVs HlyF WT induce a stronger activation of the non-canonical inflammasome pathway compared to OMVs HlyF Mut. (A) Release of LDH and IL-1β from unprimed WT, Casp11 -/-, Casp1 -/-/Casp11 -/-and Gasdermin D -/-mice BMDMs treated for 24 hr with OMV HlyF WT or OMV HlyF Mut 5µg/mL. The graphs show the mean and the standard deviation of at least 3 independent experiments for each condition. Each dot represents the value obtained in one experiment. *p<0.05 t test. (B) Release of LDH and IL-1β from unprimed WT mice BMDM treated for 24 h with OMV HlyF WT or OMV HlyF Mut 5µg/mL with 10µM wortmaninn. The graphs show the mean and the standard deviation of 3 independent experiments for each condition. Each dot represents the value obtained in one experiment. (C) Release of LDH and IL-1β from unprimed WT mice BMDM treated for 24 h with OMV HlyF WT or OMV HlyF Mut 5µg/mL with 10 nM bafilomycin. The graphs show the mean and the standard deviation of 3 independent experiments for each condition. Each dot represents the value obtained in one experiment. (D) Release of LDH and IL-1β from unprimed WT mice BMDM transfected with LPS purified from OMVs BL21 HlyF Mut or from OMVs BL21 HlyF WT (1µg/mL using FuGENE HD, Promega) for 24hr. The graphs show the mean and the standard deviation of 3 independent experiments for each condition. Each dot represents the value obtained in one experiment.

I

  Figure 1

Acknowledgments:

We gratefully acknowledge the imaging platform of INFINITy institute. This work also benefited from the assistance of Stephanie Balor and Vanessa Soldan from the Multiscale Electron Imaging platform (METi) of the Centre de Biologie Intégrative (CBI). We also thank Emmanuel Ravet (Invivogen, Toulouse) for providing us HeLa-Difluo hLC3 cells, Marie-Charline Blatche (LAAS institute, Toulouse) for assistance in DLS analysis and Miriam Pinilla (IPBS institute, Toulouse) for her valuable help in the preparation of BMDM cells and the LPS transfection experiments. Finally, we are indebted to Dr MS, Dr J-PM and Dr J-PN for their insightful comments on the manuscript.

Fundings: This project was funded by ERC StG grant (INFLAME 804249) to EM and RP.

Disclosure of interest:

The authors declare that they have no conflict of interest.

Supplementary materials

Suppl. figure S1 Suppl. figure S2 Suppl. Figure S3


Davide Grossi

Andreas Herzig

Wiebe Van Der Hoek

Christos Moyzes
email: cmoyzes@liverpool.ac.uk

Non-Determinism and the Dynamics of Knowledge

In this paper we attempt to shed light on the concept of an agent's knowledge after a non-deterministic action is executed. We start by making a comparison between notions of non-deterministic choice, and between notions of sequential composition, of settings with dynamic and/or epistemic character; namely Propositional Dynamic Logic (PDL), Dynamic Epistemic Logic (DEL), and the more recent logic of Semi-Public Environments (SPE). These logics represent two different approaches for defining the aforementioned actions, and in order to provide unified frameworks that encompass both, we define the logics DELVO (DEL+Vision+Ontic change) and PDLVE (PDL+Vision+Epistemic operators). DELVO is given a sound and complete axiomatisation.

Introduction

The paper focuses on the dynamics of knowledge in environments where agents are aware of (possibly non-deterministic) actions that are executed, but data is distributed privately: Semi-Public Environments as they are called, more recently in [START_REF] Grossi | [END_REF] and earlier in [van der Hoek et al., 2011]. By data being distributed privately we mean that the agents may or may not have constant, real-time knowledge, of the value of the variables involved. The paper sets out to investigate how non-deterministic choice in this type of environments affects the knowledge of an agent after an action is executed.

Non-deterministic choice is a central action composition operator for most logics of action. In this paper our starting points will be Propositional Dynamic Logic (PDL, [Harel et al., 2000]), Dynamic Epistemic Logic with Action Models (DEL, [van Ditmarsch et al., 2007], [START_REF] Baltag | [END_REF]Baltag et al., 1998]) and the aforementioned logic for Semi-Public Environments (SPE, [START_REF] Grossi | [END_REF]). For the presentation to follow, the reader is assumed to be familiar with DEL. In DEL and PDL, for any actions a and b of the respective language, we have the validity

([a]ϕ ∧ [b]ϕ) ↔ [a ∪ b]ϕ.
(1) If ϕ expresses knowledge, e.g. is K i ψ, the scheme expresses a strong relation between knowledge and non-determinism: an agent knows ψ after non-deterministically executing a or b, if and only if he knows ψ after executing just a and after executing just b. In DEL, an instance of ( 1) is

[x!](K i x ∨ K i y) ∧ [y!](K i x ∨ K i y) ↔ [x! ∪ y!](K i x ∨ K i y).
This property makes perfect sense; after being announced that x, or being announced that y, the agent at least knows one of the two to be true. Another interesting instance of (1), however, should arguably fail. That is what happens in SPE, where the following formula is not valid (let Kw i x be shorthand for K i x∨K i ¬x, and x:=⊥ (respectively, ⊤) stands for the action of setting variable x to false (respectively, true):

[x:=⊥]Kw i x ∧ [x:=⊤]Kw i x ↔ [x:=⊤ ∪ x:=⊥]Kw i x.
The failure of (1) in SPE also has an intuitive appeal: some part of a non-deterministic action is executed, but which part is actually performed is not necessarily revealed to the agent.

So, in contrast to what happens in DEL (or PDL extended with epistemic operators), it is not the case that if the agent knows ψ after executing a and after executing b, that he necessarily knows ψ after the execution of the non-deterministic choice between them.

A similar analysis applies to sequential composition. In the same fashion as before, we have the validity that essentially defines sequential composition in PDL:

[a; b]ϕ ↔ [a][b]ϕ.

(2) And in DEL, we have that formula [x!; y!]K i (x ∧ y) ↔ [x!][y!]K i (x ∧ y) is a validity, for x, y being atoms. This is again intuitive: announcing x ∧ y ought to be the same as announcing x and then announcing y. But also this schema is not valid in SPE; we very briefly refer to an example from [START_REF] Grossi | [END_REF] below. In its perspective the failure of (2) should not come as a surprise.

Example 1 The agent can see only variable x, and we execute the action where we non-deterministically toggle the values of x and y, or just y. After this action, we also nondeterministically toggle the value of x, or of y.

In both steps the agent can distinguish between the two possible actions; one changes x, the other does not. Consider that the agent has the opportunity to observe the impact of the first action, before the second starts, and then the impact of the second. As a result, he can distinguish between any of the four total alternatives (where both x and y, or just x, or just y, or nothing, was changed; for later use let us denote the four individual actions with v 1 , v 2 , v 3 , v 4 respectively). But what if the agent has no opportunity to observe what happened in-between? Then he can only observe what happened at the very end, and in our example, he will not be able to distinguish between all possibilities, particularly those with same truth value for x, but different for y.

The paper introduces and studies a logic that integrates both the above approaches to choice and composition, defining two novel action operators which we call opaque choice and composition. The proposed logic is a generalisation of both SPE and DEL and is called DELVO: DEL plus vision plus ontic change, which are features of SPE. Logic DELVO is then compared with an extension of PDL with vision and epistemic modalities we also introduce (called PDLVE). This logic can be considered the natural 'abstraction' of DELVO in PDL style, in the sense that the actions involved will be arbitrary connections between possible worlds (as opposed to the other dynamic logic, DL-PA [Balbiani et al., 2013], that uses assignments). The relationship between DELVO and PDLVE is studied in detail. The drawing below recapitulates the relations among the investigated logics.

Static Models

EM EMV EMV DM DEM Dynamic Models º º --A model M from any of the above classes, has a set of worlds/points W . We then have single-pointed models to be pairs of the form (M, w), for w ∈ W , and multi-pointed models to be pairs of the form (M, S), for S ⊆ W . We will use the prefix σ or µ, and the name of a class in brackets, to denote the corresponding classes of single-pointed and multi-pointed models (e.g., µ(º ) stands for multi-pointed action models). To justify the abbreviations: EM stands for Epistemic Models, EMV for the Epistemic Models with Vision, DM for Dynamic Models and DEM for Dynamic Epistemic Models, º for Action Models, º for Action Models with Toggle sets, for Program Models. We recapitulate the basic notions of DEL, we refer the reader to [van Ditmarsch et al., 2007, Ch. 6] for a comprehensive exposition. Let L be a logical language for given parameters Ag and Var. An action model M is a tuple W, R, pre such that W is a finite set, R : Ag → 2 (W×W) assigns an equivalence relation to each agent i ∈ Ag, and pre : W → L. We will denote the class of action models for L DEL with º . Language L DEL is given by syntax ϕ ::

= x | ¬ϕ | ϕ ∧ ϕ | K i ϕ | [a]ϕ
, where x ∈ Var, i ∈ Ag and a ::= (M, w) | (a ∪ a) where w ∈ W. An epistemic model for L DEL is M = W, R, f , where W is a (possibly empty) set, the set of states; f : W → Θ assigns a valuation θ to each state in W ; R : Ag → 2 (W ×W ) assigns an equivalence relation to each agent i ∈ Ag. EM denotes the class of epistemic models. The model resulting from the application of an action model M to an epistemic model M , referred to here as model product, is the model

M ⊗M = W ′ , R ′ , f ′ such that W ′ = {(w, w) ∈ W × W | M, w |= pre(w)},
(w, w)R ′ (u, u) iff wRu and wRu. and f (w, w) = f (w). Actions of DEL are defined by syntax a ::= (M, w) | a ∪ a. Finally, for each action a, we have the induced relation

[|a|]: for M, w ∈ σ(º ) we have (M, w)[|M, w|](M ′ , w ′ ) iff M, w |= pre(w) and (M ′ , w ′ ) = (M ⊗ M, (w, w)), while [|a ∪ b|] = [|a|] ∪ [|b|]. We have M, w |= [a]ϕ iff for all M ′ , w ′ ∈ [|a|](M, w) we have M ′ , w ′ |= ϕ.
The rest of the truth definitions are as usual.

Let us denote the actions of DEL with L Act 1 . In the remainder of the section we define an equivalent presentation of DEL based on multi-pointed action models. This allows us to have a unified model structure to handle all actions of L Act 1 , which facilitates later comparison with SPE. So let us consider the language L Act 2 where actions are only multi-pointed action models, that is, a ::= M, S where M, S ∈ µ(º ); and the language of DEL using L Act 2 denoted by L ′ DEL . Now the induced relation is defined as

[|M, S|](M, w) = {M ⊗ M, (w, w) | w ∈ S}.
In what follows, "⊔" denotes the disjoint union of two action models, whose sets of worlds are, for simplicity, already assumed to be disjoint. Definition 1 (Translation to µ(º )) We define function t :

L Act 1 → L Act 2 = µ(º ) as follows: If M, w ∈ σ(º ), then t(M, w) = M, {w}. If a, b ∈ L Act 1 and t(a) = M a , S a , t(b) = M b , S b , then t(a ∪ b) = M a ⊔ M b , S a ⊔ S b .
The fact that this translation is truth-preserving is formally stated in the following Theorem. Theorem 1 For all ϕ ∈ L DEL let t(ϕ) denote the formula that is ϕ but for each action a all its occurrences in ϕ are replaced by t(a). For all M, w ∈ σ(EM) and ϕ ∈ L DEL , we have M, w |= ϕ iff M, w |= t(ϕ).

The Logic DELVO

The first traditional setting on which we would like to expand and incorporate both alternative versions of choice and composition mentioned in the introductory section is DEL. The difference in behaviour we have observed relies on visionthat is, what agents can observe-and ontic change-that is, the 'factual' differences among points of evaluation in the model. It thus seems reasonable to introduce a DEL-style logic, with epistemic models enriched with vision, and action models that allow for ontic change. Definition 2 (Toggling values) Let θ ∈ Θ and S ⊆ Var. The toggling of values for the variables in S in θ, notation ˜(S)(θ), is the atomic valuation (member of Θ) defined as

˜(S)(θ)(x) = not θ(x) if x ∈ S, otherwise ˜(S)(θ)(x) = θ(x)
. Given two sets of variables S 1 and S 2 , we denote their symmetric difference by W×W) assigns an equivalence relation to each agent i ∈ Ag, pre : W → L, tgl : W → P(Var) and each tgl(w) is finite. A pair (M, S), where M is an action model and ∅ ⊂ S ⊆ W, is called a (Multi-)Pointed Action Model. When clear from context, instead of M, {w} we may also write M, w.

S 1 △S 2 , i.e., S 1 △S 2 = (S 1 ∪ S 2 ) \ (S 1 ∩ S 2 ).

Definition 3 (DELVO Action Models) A (DELVO) action model is a tuple

M = W, R, pre, tgl , where W = ∅ is finite, R : Ag → 2 (
The class of all action models is denoted by º .

In comparison with the standard manifestation of postcondition effects in DEL, which uses assignments (see for example [van Benthem et al., 2006]), our action models use toggle sets, as in [START_REF] Grossi | [END_REF]. The reason is that it allows for a more elegant handling of the notion of vision, since the agent successfully resolves uncertainty based on the difference in ontic changes caused by the actions. The two formulations are technically equivalent: one can simulate 'assignments' to variables using toggle sets [START_REF] Grossi | [END_REF]. Pairs (M, S) now are essentially the multi-pointed action models of DEL, but with each point w carrying additional information about a finite toggle set tgl(w). Finally the syntax of formulas ϕ ∈ L DELVO is:

ϕ ::= ⊤ | x | V i x | ¬ϕ | ϕ ∧ ϕ | [M, S]ϕ | K i ϕ where x ∈ Var, i ∈ Ag, (M, S) ∈ µ(º ).
Definition 4 (DELVO models) An epistemic model

(with vi- sion) M for L DELVO is a tuple M = W, R, V, f where W, R, f ∈ EM, V : Ag → 2 Var , and • wR i u implies (f (w)△f (u)) ∩ V (i) = ∅.
EMV denotes the class of epistemic models with vision. The set of all vision functions V is denoted by Vis.

So the models of DELVO are standard epistemic models enhanced with a vision function recording information about which propositional variables each agent observes. If an agent considers two worlds indistinguishable, then it must be the case that he cannot observe a difference in their valuation.

There exists the possibility that the indistinguishability relation of an action model is not compatible with the vision function of an epistemic model. The way we address these cases when trying to calculate a model product, is by 'rewiring' the action models to be 'in sync' with the agents' vision, but without them hiding any information at all, or giving information not acquired by vision.

Definition 5 Let V ∈ Vis and M ∈ º . We define the action model

M V = W V , R V , pre V , tgl V as follows: • W V = W; pre V = pre; tgl V = tgl; • wR V i u iff wR i u and tgl(w)△tgl(u) ∩ V (i) = ∅
. Now that we have everything else in place, we proceed to define the semantics of formulas and actions in DELVO.

Definition 6 Let M = W, R, V, f ∈ EMV. The truth conditions are as for DEL, plus (M, w)

|= V i x iff x ∈ V (i). Relation [|M, S|] ⊆ σ(EMV) × σ(EMV) is defined again as in DEL: [|M, S|](M, w) = {M ⊗ M, (w, w) | w ∈ S}, while (M ⊗ M) is now the epistemic model M ′ = W ′ , R ′ , V ′ , f ′ defined as: • W ′ = {(w, w) | w ∈ W, w ∈ W & (M, w) |= pre(w)}; • (w, w)R ′ i (u, u) iff wR i u and wR V i u; • V ′ = V , f ′ ((w, w)) = ˜ tgl(w) f (w) .
We conclude the section thus far by introducing a notion of bisimulation between DELVO models [START_REF] Blackburn | [END_REF].

Definition 7 Let M, M ′ ∈ EMV. A non-empty relation Z ⊆ W × W ′ is a bisimulation iff for all (w, w ′ ) ∈ Z and i ∈ Ag: Atoms For all x ∈ V ar, x ∈ f (w) iff x ∈ f ′ (w ′ ), and x ∈ V (i) iff x ∈ V ′ (i); Forth For all v ∈ W , if wR i v then there is a v ′ ∈ W ′ such that w ′ R ′ i v ′ and (v, v ′ ) ∈ Z; Back For all v ′ ∈ W ′ , if w ′ R ′ i v ′ then there is a v ∈ W such that wR i v and (v, v ′ ) ∈ Z.
Two multi-pointed action models (M, S) and (M ′ , S ′ ) are bisimilar (written (M, S) ↔ (M ′ , S ′ )) iff there is a bisimulation Z between M and M ′ , such that for any w ∈ S, there is a w ′ ∈ S ′ with (w, w ′ ) ∈ Z, and vice versa.

Axiomatisation The axiomatisation for DELVO is comprised of the axioms and rules for logic S5, axioms for vision

V i x → (K i x ∨ K i ¬x) and V i x → K j V i x,
and reduction axioms that allow any formula that includes dynamic modalities to be reduced to one that does not. These reduction axioms are identical to those of SPE [START_REF] Grossi | [END_REF], except the slightly changed reduction action for knowledge:

[M, w]K i ϕ ↔ pre(w) → V ∈Vis M (χ V → wR V i u K i [M V , u]ϕ) , with χ V
being a characteristic formula of vision function V over the variables that appear in M. Soundness is derived easily from the definitions, and completeness is proven along the lines of DEL and SPE via the standard reduction technique; completeness is then further reduced to that of logic S5+V, that is, the multi-agent epistemic logic S5n [START_REF] Fagin | [END_REF], with the two additional axioms for vision.

Opaque Choice and Composition

The logic DELVO provides us with a setting in which to properly capture not only the traditional forms of choice and composition (cf. Theorem 1) but also their opaque variants-opaque choice and composition-we motivated in the introductory section.

Let the set of actions Act be defined inductively as:

Act ∋ a ::= ϕ! | ϕ? | ˜x | a ∪ a | a ⊎ T a | a; a | a; ; a, where ϕ ∈ L, x ∈ Var and T ⊆ Ag.
The constructs ⊎ T and ; ; denote the opaque variants of the standard ∪ and ;. For T = Ag we write ⊎ omitting the subscript. Each of the above actions we recursively define in terms of suitable DELVO action models. By writing action "a" in a formula we will mean the multi-pointed action model that corresponds to a. In order to define test as a multi-pointed action model, we have based ourselves on the archetype that the test relation

w x ⊗ t ⊤ {x} s ⊤ {} 1, 2 = w, t ¬x w, s x 2 w x ⊗ t ⊤ {x} s ⊤ {} = w, t ¬x w, s
x The action model for standard non-deterministic choice is a disjoint union of action models, as in DEL (Def. 1).

Definition 9 (Opaque Non-det. Choice) Let a, b ∈ Act. The action model for a ⊎ T b is M a⊎T b , S a⊎T b = W ′ , R ′ , pre ′ , tgl ′ , S ′ where, if M a∪b , S a∪b = W, R, pre, tgl , S : • W ′ = W; pre ′ = pre; tgl ′ = tgl; S ′ = S • For i ∈ T , R ′ i = ( R i ∪ (S ′ × S ′ ) ) ∼ . For i / ∈ T , R ′ i = R i .
The intuition behind opaque choice compared to standard choice, is that, for agents in T , it 'overrides' any information gained by the distinction between points in S. It can be read as "non-deterministically execute one of the action points in S, but, after execution you will only be able to tell between them if your vision allows it". To do this, we simply take the action model of the standard non-deterministic choice, and then connect, for the agents in T , the worlds in S. As mentioned earlier, an agent's uncertainty is bound by the information it acquires by vision (recall M ⊗ M in Def. 6).

Example 2 Consider the epistemic model M with a single world w with x ∈ V (1), x / ∈ V (2). In Figure 1 we compare the action models ˜x ∪ ⊤! and ˜x ⊎ ⊤!, along with the resulting model products. Note that for opaque choice, M, w |= [˜x ⊎ ⊤!]¬Kw 2 x while for standard choice M, w |= [˜x ∪ ⊤!]Kw 2 x. And for agent 1 that 'sees'

x we have M, w |= [˜x ⊎ ⊤!]Kw 1 x ∧ [˜x ∪ ⊤!]Kw 1 x.
This example demonstrates that both directions of validity (1) fail for opaque choice. Indeed, we have M, w |=

[˜x]Kw 2 x ∧ [⊤!]Kw 2 x but M, w |= ¬[˜x ⊎ ⊤!]Kw 2 x, and similarly M, w |= [˜x ⊎ ⊤!]¬Kw 2 x but M, w |= ¬[˜x]¬Kw 2 x.
The uncertainty of the agent described by the intuition above and portrayed by this example can be described more generally by the following formula: let (M, w), (M ′ , w ′ ) ∈ µ(º ) and V be the vision function for which agent i can see none of the variables in tgl(w)△tgl(w ′ ). Then we have:

χ V ∧ [M, w]x ∧ [M ′ , w ′ ]¬x ∧(pre(w) ↔ pre(w ′ )) → [M, w ⊎ M ′ , w ′ ]¬Kw i x
We now move on to the subject of sequential composition, which poses some more difficulties. It becomes evident that it is not possible to define regular composition only as a function of the models M a , M b , without vision as a parameter; this is in contrast with the action models and the other constructs defined so far. As proof recall the actions of Example 1: if V (i) = ∅ then v j R i v k for 1 ≤ j, k ≤ 4 in the action model, and for the resulting worlds also (w, v j )R i (w, v k ). If we set V (i) = {x} then the action model would be the same but it should not be the case e.g. that (w, v 2 )R i (w, v 3 ). We are therefore led to the following definition.

Definition 10 (Composition) Let V ∈ Vis, M a = W a , R a , pre a , tgl a , S a and M b = W b , R b , pre b , tgl b , , S b . Their composition w.r.t. V is the pointed action model M V a;b , S V a;b = W, R, pre, tgl , S where: W = W a × W b , S = S a × S b , • (w, w ′ )R i (v, v ′ ) iff wR V ai v & w ′ R V bi v ′ ; • pre(w, v) = M a , w pre b (v), tgl(w, v) = tgl a (w)△tgl b (v)
We need not advocate the correctness of the definition regarding W, pre, tgl, and S, as they are what is expected for the composition of two action models in DEL as well as SPE. Vision influences only the accessibility relation R, and regarding that we need only note that it is again the one normally expected, with the exception that the agent has the opportunity to apply his vision after execution of actions a and b. Hence R V ai is used (Def. 5) and not R ai . Finally, let us point out that with this definition a vision function V is linked to an action model directly, and an epistemic model M may have a vision function V ′ = V . In that case, a formula using such an action model cannot be interpreted in M .

We do not run into the same kind of problem with opaque composition as it uses the same idea behind opaque choice: it disregards previous connections (or more precisely, the lack thereof) in the model. Intuitively speaking, the agent is absent while actions a and then b are executed, 'missing' any announcements made and also the opportunity to apply his vision as changes occur to the variables. We can now see how to falsify property (2) from the introduction. Consider again the epistemic model of Example 2. Action model for (˜x ∪ ⊤!); ; ⊤! is the action model of (˜x ⊎ ⊤!), found in the first row of Figure 1, while in the second row we have the action model of (˜x ∪ ⊤!) and the resulting epistemic model. Applying action ⊤! does not change anything, and so

M, w |= ¬[(˜x ∪ ⊤!); ; ⊤!]Kw 2 x, while M, w |= [˜x ∪ ⊤!][⊤!]Kw 2 x.
Relation to DEL and SPE Not coincidentally, the class of DELVO (static) models-i.e. epistemic models with vision-is exactly the class of models of SPE, and subsumes the class of standard epistemic models (without vision, that is, where vision is empty), which are the models of DEL. In this section we define the relevant translations among these classes of models and state, without proof, and state the two truth-preserving embeddings.

Definition 12 We define function h : EM → EMV as follows: Let

M = W, R, f ∈ EM. Then h(M ) = W, R, V, f , where V is such that for all i ∈ AG, V (i) = ∅.
Definition 13 Let M, S = W, R, pre , S. We define g : µ(º ) → µ(º ) as g(M, S) = W, R, pre, tgl , S, where tgl is the function such that for all w ∈ W, tgl(w) = ∅.

Theorem 2 For all ϕ ∈ L ′ DEL let g(ϕ) denote the formula that is ϕ but for each action a all its occurrences in ϕ are replaced by g(a). Let M, w ∈ σ(EM) and ϕ ∈ L ′ DEL . We have M, w |= ϕ iff h(M ), w |= g(ϕ).

We work similarly for SPE; its models are exactly those of DELVO, and its action models can be seen as a special case of DELVO action models. Definition 14 We define function g : σ(

) → µ(º ) as follows: Let M = {w 1 = (ϕ 1 , X 1 ), . . . , w n = (ϕ n , X n )} ∈ and w ∈ M. Then g(M, w) = W, R, pre, tgl , {w} where W = {w 1 , . . . , w n }, pre(w i ) = ϕ i , tgl(w i ) = X i and R j = W × W.
Theorem 3 For all ϕ ∈ L SPE let g(ϕ) denote the formula that is ϕ but for each action M, w all its occurrences in ϕ are replaced by g(M, w). Let M, w ∈ σ(EMV) and ϕ ∈ L SPE . We have M, w |= ϕ iff M, w |= g(ϕ).

The Logic PDLVE

We now attempt a generalisation of opaque choice and composition to a more abstract PDL-like setting. For DELVO, a large part of the intuitions and formal techniques stem from the use of action models. The latter do not exist in PDL and it is interesting to examine how it would be possible to circumvent their use. Furthermore, actions of PDL are strictly more general; to see this consider that an atomic PDL action can connect a finite component of worlds to an infinite one -this cannot be achieved by any [|M, w|] as action models are finite. Therefore with PDLVE we attempt not only to represent the opaque constructs in the PDL paradigm, but also extent their use to a richer class of actions.

In addition to sets Ag and Var, let also a countable set of atomic actions Atom = {a 1 , a 2 , . . . } be given.

The language of PDLVE is defined by the following syntax:

ϕ ::= ⊤ | x | V i x | ¬ϕ | ϕ ∧ ϕ | [a]ϕ | K i ϕ where a ::= π ∈ Atom | a ∪ a | a ⊎ a | a; a | a;
; a and x ∈ Var, i ∈ Ag. We avoid the generalisation for T ⊆ Ag consciously, so as to not further encumber notation.

To capture opaque choice in PDLVE we rely on the basic intuition behind it. Given actions a, b, and world w, "either a or b is executed at w, but the agent does not know which, unless his vision allows him to do that". Based on the above, we first give an auxiliary definition: given M ∈ EMV and relations for a, b ∈ Act, this definition describes a representation of the epistemic model that should be the image of a ⊎ b.

So let M = W, R, V, f ∈ EMV. For S ⊆ W let N (S) denote the epistemic submodel generated by S, and N w (S) the worlds of that model. We remind that for

E ⊆ W × W , E(S) = {w ∈ W | ∃v ∈ S s.t. vEw}. Definition 15 Let M = W, R, V, f ∈ EMV, and E ⊆ W ×W . Let M ′ = N (E(W )) = W ′ , R ′ , V ′ , f ′ . Finally let E be injective and E(W ) = W ′ . We then define g(M, E) = W ′′ , R ′′ , V ′′ , f ′′ such that: W ′′ = W ′ , V ′′ = V ′ , f ′′ = f ′ , • for u ∈ E(w), z ∈ E(v), we have uR ′′ z iff wRv and (f (w)△f ′′ (u))△(f (v)△f ′′ (z)) ∩ V (i) = ∅
In words, given a model M and an injective relation E (that is later to play the role of choice or composition between two actions), we first get the epistemic submodel generated by worlds that are an image through E, namely M ′ . Note also that E is such that its co-domain is exactly the set of worlds of M ′ . Then we 'tinker' M ′ to get the model g(M, E), that is the same as M ′ but the agents cannot distinguish between worlds that are images through E (uR ′′ z), if and only if the origin worlds were indistinguishable to begin with (wRv) and their vision does not help them notice a difference in the changes caused among the possible executions; that is,

(f (w)△f ′′ (u))△(f (v)△f ′′ (z)) ∩ V (i) = ∅}.
We can now define the class of PDLVE models (denoted by DEM). For brevity, let * denote either regular choice or composition, and ⊛ their opaque variant. Also let (g(M, E), E(w)) = g(M, w, E).

Definition 16 (PDLVE Models) Let M = W, R, E, V, f where W, R, V, f ∈ EMV (Def. 4) and E is a family of relations E a ⊆ W × W , where a is either atomic or of the form "b ⊎ c" or "b; ; c". Furthermore, E is such that:

• for a = b ⊛ c, if E b * c is an injection and E b * c (W ) = N w (E b * c (W )), then N (E a (w)), E a (w) ↔ g(M, w, E b * c ), otherwise E a = ∅;
We interpret formulas at pointed dynamic models as usual.

And regarding standard choice and composition we define

E a∪b = E a ∪ E b and E a;b = E b • E a , again as normal.
In contrast to what happens with relations E a∪b and E a;b , relations E a⊎b and E a;;b are not necessarily expressed only in terms of the source world w, E a (w), or E b (w). Different worlds whose names we cannot dictate beforehand may be involved. What we do is therefore require that these worlds are 'correct', in the sense that they are bisimilar to the corresponding set of worlds in the model that would be the representation (Def. 15) of opaque choice or opaque composition.

Is this representation we have chosen a correct one? The next theorem shows that at least as far as a special subset of DELVO actions is concerned, this is indeed the case. Let, for M ∈ EMV,

P M = {M, w | w ∈ M }. Theorem 4 Let M, w ∈ σ(EMV) and (M a , S a ), (M b , S b ) ∈ µ(º ) such that M a , M b are disjoint, [|M a * b , S a * b |](P M ) = P M ⊗M a * b . Let M ′ = M ∪ (M ⊗ M a * b ). Define wE a v iff (M, w)[|M a , S a |](M ⊗ M a * b , v
) and similarly for b. Also let M ′′ = M ′ ⊔ g(M ′ , E a⋆b ). Assume that for the disjoint union, every w ∈ g(M ′ , E a⋆b ) was renamed to w ′ . Finally, for

w ∈ M ′′ let E a⊛b (w) = {v ′ | v ∈ E a * b (w)}. Then [|M a⊛b , S a⊛b |](M, w) ↔ M ′′ , E a⊛b (w).
Relation to DELVO We now have two logics for describing knowledge, and epistemic & ontic change. A natural question is whether the actions of PDLVE are more general than those of DELVO. We find that, under mild restrictions, they are not.

As one would expect, the transition from DELVO to PDLVE can be done simply enough. After all DELVO can be reduced to S5+V, and epistemic models with vision are part of PDLVE models. To evaluate a given DELVO formula ϕ in a model M, w ∈ σ(EMV), one would have to potentially evaluate subformulas of ϕ in M and in the respective model products.

The idea for the transition from DELVO to PDLVE, is to define a single PDLVE model by putting together all such models.

Definition 17 Let M ∈ σ(EMV) and ϕ ∈ L DELVO (M may be omitted when clear from context) by induction on the complexity of ϕ as follows:

T 1 (⊤) = T 1 (x) = T 1 (V i x) = {M }, T 1 (¬ϕ) = T 1 (K i ϕ) = T 1 (ϕ), T 1 (ϕ ∧ ψ) = T 1 (ϕ) ∪ T 1 (ψ), T 1 ([M, S]ϕ) = {N ⊗ M | N ∈ T 1 (ϕ)}.
We then define

T M 2 (ϕ) = {M ′ ∈ EMV | ∃n ≥ 0 and M 1 , . . . , M n ∈ µ(º ) s.t. M ′ ⊗ M 1 • • • ⊗ M n ∈ T 1 (ϕ)}
T M 2 (ϕ) therefore contains a tree with all the models involved in the process of evaluating ϕ in some w ∈ M . This idea is not new, see e.g. [START_REF] Van Benthem | The tree of knowledge in action: Towards a common perspective[END_REF].

Theorem 5 Let ϕ ∈ L DELVO and M, w ∈ σ(EMV). Let T M 3 (ϕ) = W, R, E, V, f such that W, R, V, f = T M 2 (ϕ)
and regarding E, for all multi-pointed action models M i , S i that appear in ϕ it holds that, for w ∈ M and w

′ ∈ M ′ , wE ai v ′ iff (M, w)[|M i , S i |](M ′ , w ′ ). Finally let T M
4 (ϕ) be a model that has T M 3 (ϕ) as a submodel but contains appropriate definitions for opaque choice and composition, so that T M 4 (ϕ) ∈ DEM. Let t : L DELVO → L PDLVE be a function such that t(ϕ) is ϕ, but for all action models M i , S i that appear in ϕ, all its occurrences are replaced with a i . Then it holds that M, w |= ϕ iff T M 4 (ϕ), w |= t(ϕ). For the direction "PDLVE to DELVO", the problem we will be trying to solve is, given M, w ∈ σ(DEM) and ϕ ∈ L PDLVE , is there a translation t for ϕ, where actions of PDL have been translated into multi-pointed action models, such that N (w), w |= t(ϕ)? Such a translation is impossible to define homogeneously for all models of PDLVE, as action a changes depending on its relation, in each PDLVE model M . So let M ∈ DEM, and a ∈ Act. Action a is perhaps executable in a number of worlds, and for each such world, the action may have a number of different possible executions. When focusing on the case where a single world w is connected through a with a world v, then the question is: is there a multi-pointed action model to transform N (w), w into N (v), v?

This question relates to epistemic planning, which is undecidable for the multi-agent case [START_REF] Aucher | Undecidability in epistemic planning[END_REF], and it has been answered in [START_REF] Van Ditmarsch | [END_REF] for finite S5 models (and other models under certain restrictions) and using action models with assignment to achieve ontic change. Our construct will follow the same idea, but we will be focusing on PDLVE models that (i) have finite W , (ii) are an epistemic bisimulation contraction (cf. [START_REF] Blackburn | [END_REF]), and (iii) for which wE a v implies that for all

v ′ ∈ N w (v), f (w)△f (v ′ ) is finite.
Note that for any M, w ∈ σ(DEM) satisfying (i)-(ii), there exists a characteristic formula ϕ w ∈ L DELVO [START_REF] Barwise | Vicious circles : on the mathematics of non-wellfounded phenomena[END_REF]

, i.e., for v ∈ M we have M, v |= ϕ w iff v = w.
Definition 18 Let M, w ∈ σ(DEM), satisfying (i)-(iii) and wE a v. We define h(M, w, v) = W, R, pre, tgl ∈ º as:

• W = N w (v), R = R| Nw(v) ; • for all w ∈ W, pre(w) = ϕ w , tgl(w) = f (w)△f (w).
Back to the more general problem; action a can lead a world w to a multitude of worlds v i , finite in number. A way to get an equivalent result by using action models, is to put 'side by side', via disjoint union, models h(M, w, v i ). Furthermore, we can have the case where action a is executable in a multitude of worlds w j , again finite in number. Again, this can be solved by taking the disjoint union of h(M, w j , v). Definition 19 Let M, w ∈ σ(DEM), ϕ ∈ L PDLVE and a an action that appears in ϕ. Let M satisfy (i)- (iii). Define:

M a , S a = w∈M v∈Ea(w) h(M, w, v), v.

Theorem 6 Let M, w ∈ σ(DEM) as above and ϕ ∈ L PDLVE . Let t : L PDLVE → L DELVO be a function such that t(ϕ) is ϕ, but for all actions "a" that appear in ϕ, all its occurrences are replaced with M a , S a . Then it holds that M, w |= ϕ iff N (w), w |= t(ϕ).

Conclusion

We pointed to two different ways to understand the interaction between knowledge dynamics and non-determinism, starting from logics DEL, PDL, and SPE. We presented a multi-pointed action model formulation of DEL to express non-deterministic choice. We defined the logic DELVO, which is capable of handling epistemic and ontic change (for DEL-based work that also combines epistemic and ontic change see [van Eijck, 2004a;2004b], [van Benthem et al., 2006], and[van Ditmarsch andKooi, 2008]), along with the notion of vision, and allows for a richer set of actions than those of DEL and SPE. Within DELVO, we defined both standard and opaque forms of choice and composition. We also provided a sound and complete axiomatisation for it, and a number of embedding results situating it among its related formalisms.

We also explored a more abstract logic, capable of epistemic and ontic change, with an even richer class of actions: PDLVE. Its semantics are based on PDL models with epistemic relations and vision atoms. Here, our contribution is the definition of opaque non-deterministic choice and composition in this PDLlike setting. Finally, we provided theorems that compare DELVO and PDLVE, thus also investigating the relation between action models, and atomic actions defined arbitrarily.

Several opportunities for future work exist; we briefly mention that for DELVO we would like vision atoms to exist for other formulas as well, not only variables. For PDLVE there is the obvious need for a proof system. Furthermore, two papers that in our opinion are especially relevant are [van Eijck, 2012] and [START_REF] Charrier | [END_REF]. The former distinguishes between actual use of vision and the capability to use it. In the latter, vision is necessarily common knowledge and the notions of higher order and joint vision are introduced. One may also consider the agents not being aware of the actions being executed or some of the variables [START_REF] Van Ditmarsch | Action models for knowledge and awareness[END_REF]. Another worthwhile endeavour would be a systematic comparison between our framework and the Situation Calculus (cf. [START_REF] Scherl | [END_REF][START_REF] Van Ditmarsch | [END_REF]) and the standard and opaque variants. The difference between the variants is demonstrated by the difference between MDP and POMDP (see for example [START_REF] Boutilier | [END_REF][START_REF] Delgrande | [END_REF] and [START_REF] Bacchus | [END_REF]).

  Announcement) Let M ϕ! = W, R, pre, tgl , where W = {e}, R i = {(e, e)}, pre(e) = ϕ and tgl(e) = {}. The multi-pointed action model for ϕ! is M ϕ! , {e}. 2. (Toggle) Let M ˜x = W, R, pre, tgl , where W = {t}, R i = {(t, t)}, pre(t) = ⊤ and tgl(t) = {x}. The multipointed action model for ˜x is M ˜x, {t}. 3. (Test) Let M ϕ? = W, R, pre, tgl , where W = {w, v}, R i = W × W, pre(w) = ϕ, pre(v) = ¬ϕ and tgl(w) = tgl(v) = {}. The multi-pointed action model for ϕ? is M ϕ? , {w}.

Figure 1 :

 1 Figure 1: Epistemic model M (left) for which x ∈ V (1), x / ∈ V (2), action models (˜x ⊎ ⊤!) (top) and (˜x ∪ ⊤!) (bottom), and the resulting model products (right). represents, in PDL models. Specifically, given a PDL model M , then [|ϕ?|] = {(w, w) ∈ M × M | M, w |= ϕ}. The relation induced by action models (in our case Def. 6) is not between worlds of the same model, but between the original epistemic model, and the model product. The reader can check that with the action model for test in Definition 8, we have, given M, w ∈ σ(EMV), if M, w |= ϕ then [|ϕ?|](M, w) = ∅, and if M, w |= ϕ then [|ϕ?|](M, w) = M ⊗ M ϕ? , (w, w), and M, w is isomorphic to M ⊗ M ϕ? , (w, w).The action model for standard non-deterministic choice is a disjoint union of action models, as in DEL (Def. 1).

Definition 11 (

 11 Opaque Composition) Let a, b ∈ A. The pointed action model for a; ; b is M a;;b , S a;;b = W, R, pre, tgl , S defined as in Definition 10 but R i = W × W.

  Let us next give a summary of the notation for the different classes of models we will be using, given that several logics are involved in this study.

	DEL	SPE		PDL
	Th. 2	Th. 3
			Th. 5
	DELVO			PDLVE
			Th. 6
	2 Preliminaries
	DEL	SPE	DELVO	PDL	PDLVE

Throughout the paper, we will be dealing with a finite set Ag = {1, . . . , m} of agents, and a countable set of propositional variables Var = {x 1 , x 2 , . . . }. A valuation θ : Var → {true, f alse} assigns a truth value to each variable x ∈ Var. The set of all valuations is denoted by Θ. Given a relation R ⊆ A × A, R ∼ is its reflexive, symmetric, and transitive closure. For S ⊆ A, R(S) = {w ∈ A | ∃v ∈ S s.t. vRw}.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence

Acknowledgements

We wish to thank the anonymous reviewers for many helpful and constructive comments.