Gérard Assayag
email: gerard.assayag@ircam.fr

Creative Symbolic Interaction Keynote talk

Creative Symbolic Interaction brings together the advantages from the worlds of interactive real-time computing and intelligent, content-level analysis and processing, in order to enhance and humanize man-machine communication. Performers improvising along with Symbolic Interaction systems experiment a unique artistic situation where they interact with musical (and possibly multi-modal) agents which develop themselves in their own ways while keeping in style. Symbolic interaction aims at defining a new artificial creativity paradigm in computer music, and extends to other fields as well : The idea to bring together composition and improvisation through modeling cognitive structures and processes is a general idea that makes sense in many artistic and non-artistic domains.

INTRODUCTION

Until recently, in the field of musical interaction with machines, engineers and researchers have been concerned by fast computer computation and reaction -a logical concern considering available machine speeds and complexity of tasks. However, instantaneous response is not always the way a musician reacts in a real performance situation. Although decisions are being carried out at a precise time, the decision process relies on evaluation of past history, analysis of incoming events and anticipation strategies. Therefore, not only can it take some time to come to a decision, but part of this decision can also be to postpone action to a later time. This process involves time and memory at different scales, just as music composition does, and cannot be fully apprehended just by conventional signal and event processing. A symbolic level has to be involved as well.

In order to foster realistic and artistically interesting behaviors of digital interactive systems, and communicate with them in a humanized way, we wish to combine several means : machine listening [START_REF] Wang | Machine Audition: Principles, Algorithms and Systems, Information science reference[END_REF] -extracting high level features from the signal and turning them into significant symbolic units ; machine learning [START_REF] Dubnov | Using Machine-Learning Methods for Musical Style Modeling[END_REF] -discovering and assimilating on the fly intelligent schemes by listening to actual performers ; stylistic simulation [START_REF] Assayag | Guessing the composer's mind: applying universal prediction to musical style[END_REF] -elaborating a consistent model of style ; symbolic music representation -formalized representations connecting to organized musical thinking [START_REF] Assayag | Interaction with Machine Improvisation[END_REF], analysis and composition. These tools cooperate in effect to define a multi-level memory model underlying a discovery and learning process that contributes to the emergence of a creative musical agent.

In the Music Representation Team a t I r c a m , after OpenMusic, a standard for computer assisted composition, we have designed OMax [START_REF] Assayag | Omax Brothers : a Dynamic Topology of Agents for Improvization Learning[END_REF][START_REF] Assayag | Navigating the Oracle: a Heuristic Approach[END_REF][START_REF] Lévy | OMaxist Dialectics : Capturing, Visualizing and Expanding Improvisations[END_REF], an interactive machine improvisation environment which explores this new interaction schemes. It creates a cooperation between heterogeneous components specialized in realtime audio signal processing, high level music representations and formal knowledge structures. This environment learns and plays on the fly in live setups and is used in many artistic and musical performances. OMax exemplifies several trends of current research on interactive creative agents capable of adequacy and relevance by connecting instant contextual listening to corpus based knowledge, along with longer term investigation and decision processes allowing to refer to larger-scale structures and scenarios. We call this scheme Symbolic Interaction.

Creative Symbolic Interaction brings together the advantages one can get from the worlds of interactive realtime computing and intelligent, content-level analysis and processing, in order to enhance and humanize manmachine communication. Performers improvising along with Symbolic Interaction systems experiment a unique artistic situation where they interact with a musical (and possibly visual) agent which develops itself in its own ways while keeping in style with the user. It aims at defining a new artificial creativity paradigm in computer music, and extends to other fields as well : The idea to bring together composition and improvisation through modeling cognitive structures and processes [START_REF] Pressing | Cognitive processes in improvisation[END_REF] is a general idea that makes sense in many artistic and nonartistic domains. It is a decision-making paradigm where a strategy makes its way by weaving decisions step after step, either by relating to an overall structural determinism, or by jumping in an "improvised" way and generating a surprise. This kind of "improvisation" strategy is observed in the living world, and might be one aspect of intelligence as a way to cope effectively with the un-known, thus it may serve as a productive model for artificial music creativity.

GENERAL CONTEXT

Improvised interaction between humans and digital agents is a recent field of studies in the context of artificial creativity, which convenes several active research issues: interactive learning, which models are built at the very time of interaction, and the expression of which inflect the very conditions of this interaction ; artificial perception, based on this interaction ; modeling of social and expressive interaction between human agents and / or digital ones, in its anthropological, social, linguistic, and IT dimensions.

This type of interaction involves the perception / action loop and engages the learning process in a renewed design where an agent learns in particular from the reactions of other agents to its own creative productions.

on human and artificial creativity in sound and music raises a lot of interest worldwide and has been developing seriously these last years with many technical progresses in artificial listening, epistemic modeling, artificial intelligence, machine learning, signal and physical models and representations. Creativity in general is supported at European level by one of its Objective called "Technology and scientific foundations in the field of creativity" in its actions "Intelligent computational environments and stimulating human creativity and Enhancing Progress towards formal understanding of creativity".

IMPROVISED INTERACTION

To confront the problem of improvised interaction understood as a powerful driver for creativity and situated at the heart of all human activities constitutes one of today's c e n t r a l c h a l l enges in digital intelligence in sound and music computing. We envision it in the realm of interactions between physical, digital and human worlds, in a music information dynamics setup where we wish to integrate artificial listening, learning of musical behaviors, temporal modeling of musical structures and dynamical creative interaction in an architecture for effective experimentation in real time.

Possible applications will be available in varied flavors on-line and off-line. They are likely to change the situation in the artistic relationship between human and artificial agents. Off-line listening to and learning from large music databases will feed generative systems for composition and performance and ease the addition of creative functionalities to software for multi-media production and post-production, digital games and cinema, access to audiovisual heritage. Integrating listening and learning in the very process of artistic interaction makes it possible to program software agents with the skills to react in real-time to human performance in manmachine improvisation setups, in multimedia installations, in electro-acoustic composition, in the creation of new "variable" formats for music production and distribution.

Architectures integrating concurrent agents and logical constraints [START_REF] Assayag | Constraint Programming in Music[END_REF] capturing the idea of scenario provide opportunities for powerful generativity in situations ranging from popular music to digital games, web applications, generative cinema, by providing a control layer for the interactive generation of new temporal sequences through the progression of the game, the incarnation and the evolution of a character, the behavior of the user. In this sense, symbolic interaction will disrupt the notion of public access to recorded music, with potentially major impact on cultural heritage and industries, shifting more and more the public from passive to genuine participation.

DYNAMICS OF INTERACTION

Creative Digital Agents

Our dynamics of creative improvised interaction focuses on the creation, adaptation and implementation of effective and efficient models of artificial listening, learning, interaction and automatic creation of musical content in order to allow the formation of digital music agents that succeed in being autonomous, creative, able to display artistically credible manners in various artistic and educational human setups such as live performance and teaching. These agents mayalso help constitute the perceptual and communicative skills of embedded artificial intelligence systems.

The aim is to evolve self-creative agents by the process of interactive learning from direct exposure to human improvisers, thus creating a retro-action loop (stylistic reinjection) through the simultaneous exposure of humans to the "improvised" productions of the digital agents themselves. This involves a complex dynamics of time and space evolving human / digital communication.

Offline Learning

Even in the case of real-time performance, an offline learning process based on vast musical corpora can be anticipated so as to stylistically "color" digital individualities o r position t h e e x p e r i e n c e within a p a r t i c u l a r genre (classical, jazz, traditional, electro etc.)

In addition to applying these digital skills to live music situations where digital and human agents interplay, the game can be extended to innovative applications such as interaction of users of all sorts with audio-visual heritage archives which would be dynamically resurrected within a creative or educational framework, thus extending the improvisation paradigm to new narrative and immersive forms in a step unseen yet. We are currently building a project in this direction with EPFL University in Lausanne around the Montreux Festival Archives recently listed by Unesco as part of the World Cultural Heritage.

Collectivities of Agents

The idea is to create both an artificial expertise of musical practice ("machine musicianship") by this kind of interaction and a rich experience of instantaneous human -digital communication likely to provide an aesthetic satisfaction to the user, to broaden its sound and music production means, to "talk" with him by imitation or contradiction, and, in general, to stimulate and boost the musical experience individually and collectively. This human-agent interaction will be in effect extended to complex configuration involving potentially a great number of agents -human and artificial -learning and evolving from each other. As the experience will take form, autonomous digital music personalities, able to intervene credibly in complex situations of interaction with humans and other agents, will emerge.

An artificial entity in a creative audio-musical context subsumes itself as a collection of elementary contributory and competitive components, capable of interactive learning, implementing the artificial listening tasks, the discovery of short and long-term temporal structures, the modeling of style, the generation of symbolic sequences, the real-time audio management, and the visualization and human-machine interface functions as well.

The OMax Galaxy

A great part of these capacities are already available in the OMax environment, which has already been used in a number of public performances throughout the world and is established as a well known reference in the realm of improvised machine musicianship [START_REF] Assayag | Interaction with Machine Improvisation[END_REF][START_REF] B L A C K W E L L | Live Algorithms: Towards Autonomous Computer Improvisers[END_REF]. Several extensions of the OMax paradigm are currently under research or starting in the author's team (Music Representation) at Ircam as well as in partner labs at UCSD, EHESS, Inria, UBO, and CNMAT Berkeley. These researches include musical information dynamics [START_REF] Dubnov | Audio Oracle Analysis of Musical Information Rate[END_REF][START_REF] Surges | Feature Selection and Composition using PyOracle[END_REF], formal automata [START_REF] Donze | Control improvisation with application to music[END_REF], probabilistic approaches [START_REF] Conklin | Music Generation from Statistical Models[END_REF], cognitive modeling of memory, accompaniment systems, scenario based improvisation, multi-agent interaction dynamics, temporal adaptation of interaction, digital intelligence and artificial creativity. The OMax galaxy connects with active or starting projects in several of these labs with studies in knowledge models and decision-making strategies for synchronous and asynchronous agents caught in collective creative action, elicitation of augmented listening by the use of prior knowledge, co-adaptation of perception and action in an interactive learning environment, integration of multi-dimensional and multi-scale aspects of musical structures.

SYMBOLIC INTERACTION

From there on, we wish to move in the direction of a more powerful and versatile instantiation of symbolic interaction. A series of projects involving several PhD and post-doc works and several national and international collaboration have been initiated, in order to stimulate theoretical advances and development of experimental environments in a number of directions.

Perceptual Skills

It is thus necessary to be able to empower digital agents with the ability to analyze complex auditory scenes in real time and to extract musical structure from them by discovering time and space regularities [START_REF] Cont | On the Information Geometry of Audio Streams with Applications to Similarity Computing[END_REF] and exploiting available prior knowledge possibly through an "informed musical decomposition" paradigm [START_REF] Marchand | DReaM: a novel system for joint source separation and multi-track coding[END_REF], taking advantage of scores, annotations, or inferring partial information from learning beforehand stylistically compatible corpora.

Learning Skills

Interactive learning of musical structures stems from data provided by the sequential process of listening, learning symbolic models that capture high-level multidimensional and multi-scale musical structures emerging in a context of musical performance and improvisation. Many formal models may compete and even cooperate for that purpose. The Factor Oracle model [START_REF] Assayag | Using Factor Oracles for machine Improvisation[END_REF][START_REF] Crochemore | The Structure of Factor Oracles[END_REF] coming from the automata and formal languages research field has been massively used in OMax and its derivative with great achievements. Hidden Markov Models, Temporal Grammar Rules Induction, Deep Be-lief Networks, Concurrent Constraint Calculus, Spatial and Epistemic CCP, Multi-objective Time Series modeling among others can be explored as well for that purpose. Researches at Inria have shown the power of Bayesian modeling [START_REF] Raczyński | Dynamic Bayesian networks for symbolic polyphonic pitch modeling[END_REF] in the case of data sparsity and a new collaboration project will allow the evaluation of integrating sequential formal modeling with probabilistic methods in the case of complex musical discourses when one lacks training data, trying to combine this way computational efficiency and robustness of learning.

Interaction Logic

In this perceptual and knowledge framework, improvised interaction logic allows a rich and creative exchange between human and artificial agents and asks questions on the temporal and spatial collective adaptation of interaction at multiple scales. This adaptation takes advantage of the artificial perceptual and cognitive environment in order to articulate a proactive control of collective improvised interaction, addressing such issues as internal structure of the agents, memory models, knowledge and control capabilities. There is a need to go beyond the conventional static and predetermined approaches and be able to adapt in real-time the models, representations and learning methods of interaction, taking into account different temporal scales and collective dynamics [START_REF] Canonne | A Model for Collective Free Improvisation[END_REF], engaging attention, comprehension and decision skills. It will be possible in this way to construct intelligent multi-agent systems well equipped for dealing credibly with more complex musical situations involving a variety of styles.

Scenario Models

An artificial improvising musical agent may have in certain cases a planned strategy or a scenario. It has to improvise in an explicit harmonic and rhythmic context by exploiting a priori information that is structuring on one hand the training corpus and on the other the current context of improvisation providing they are labeled by a common symbolic vocabulary, e.g. harmonic, textural, or timbral descriptors [START_REF] Nika | ImproteK, integrating harmonic controls into improvisation in the filiation of OMax[END_REF]. The improvisation process guided by a control sequence can be described as the relationship between an external plan and a structured and annotated memory from which it dynamically reconstitutes musical sequences to create new improvisations, compatible in their temporal organization and their different dimensions (harmonic, rhythmic) with the plan. As an example, the plan can be a harmonic grid, and the memory a formal model learned from realizations of this grid and/or others one as well. The Improvisation will follow the grid while deploying and combining musical material coming from a number of sources. The ImproTek [START_REF] Nika | ImproteK, integrating harmonic controls into improvisation in the filiation of OMax[END_REF] flavor of OMax developed in collaboration between EHESS and the Music Representation Team at Ircam can already, to a certain extent, simulate such a planned improvisation situation.

Flow Models

However, an improvising agent may act freely with no information on the future as in the previous case. When there is no known scenario, the generative process can nevertheless be oriented causally by an input stream, typically produced by a human musician or by an other digital i n t e l l i g e n c e , t h e m s e l v e s i m p r o v i s i n g f r e e l y o r with a defined strategy. The process maintains in that case a "floating synchronization" between the data acquired in real-time by listening to the input stream and a structured and annotated memory from which it dynamically reconstructs musical sequences coherent and locally compatible with the input stream for certain musical dimensions. A simple example of such an interaction is the automatic accompaniment of a melodic improvisation, another one is the generation of solos on an improvised series of chord ; in the general case, an arbitrary number of agents trained on different corpus will be able to co-improvise by listening to each other and adapting flexibly to each other with regards to pitch, rhythm, harmony, or texture and timbre, as would human experts do. The SoMax flavor of OMax developed in the Music Representation Team at Ircam can already, to a certain extent, simulate such an adaptive behavior linked to an input flow.

Scenario models and flow models can be combined to simultaneously take advantage of the ability of the first to manage improvisation plans and of the second to flexibly adapt to the contingencies of listening and interaction, taking into account the formal organization of music as it is learned and modeled into a structured annotated memory.

Temporal Adaptation

An adaptive and proactive system of improvised interaction takes into account different temporal scales and collective dynamics. This means recognizing and adapting short-term phenomena (reaction, synchronization) as well as long-term phenomena (the emergence of vocabulary and higher level forms) and involves updating multi-scale hierarchical representations of interaction (engaging cognitive representations, or mental states). The formalization of a consistent and versatile scheme of interaction to address these areas is challenging and requires the development of a global approach in order to reach "expressiveness" and "style".

Memory, Knowledge, Control

A creative artificial agent capable of listening, learning and performing improvised musical interaction with humans and other artificial agents must have a minimal "cognitive" structure allowing him to succeed in a complex environment which incorporates its own productions, thus involving reflexivity on its own behavior and state. One has to identify the representations and processes best suited to model this internal structure and its activation by external stimuli.

It may consist in a memory and a knowledge network operated at different time scales (echoic memory, long term memory) and at different activation and control levels, whether they be implicit (procedural or reflex) or explicit (episodic or semantic memory). Coupled structures of memory and control currently implemented as a Factor Oracle, should be extended to sophisticated topological devices, possibly using SOM (self organizing maps). These would contribute to the formation of a semantic memory through the automatic organization of a topology of musical objects. It would contribute as well to the constitution of reflexive processes simulating awareness (curiosity triggered by a stimulus), attention (listening or not other agents), motivation (wanting to learn or not) and initiative (decision to play or not) in relation to computational models of self and intentionality (self-model theory).

CONCLUSIONS

Creative Symbolic Interaction has emerged as an extremely productive combination of machine listening, machine Learning and Music structure modeling, in the framework of adaptive interaction dynamics. It is rich of promises for Improvised Machine Musicianship ( t o quote Robert Rowe's famous book Machine Musicianship) and in general for digital intelligence and creativity.

Figure 1 .

 1 Figure 1. Stylistic Reinjection Paradigm

Figure 2 .

 2 Figure 2. OMax Galaxy

Acknowledgments

Thanks to the other OMax Brothers: M. Chemillier, S. Dubnov, G. Bloch, B. Lévy, L. Bonnasse-Gahot, J. Nika.

Improvised Machine Musicianship projects described in this document partly funded by Agence nationale de la recherche (ANR) projects ImproTech, SOR2 (finished) and DYCI2 (starting).


Andreas Herzig

Pilar Pozos-Parra

Franc ¸ois Schwarzentruber

Belief Merging in Dynamic Logic of Propositional Assignments

Keywords: belief merging, belief change, dynamic logic

We study syntactical merging operations that are defined semantically by means of the Hamming distance between valuations; more precisely, we investigate the Σ-semantics, Gmax-semantics and max-semantics. We work with a logical language containing merging operators as connectives, as opposed to the metalanguage operations of the literature. We capture these merging operators as programs of Dynamic Logic of Propositional Assignments DL-PA. This provides a syntactical characterisation of the three semantically defined merging operators, and a proof system for DL-PA therefore also provides a proof system for these merging operators. We explain how PSPACE membership of the model checking and satisfiability problem of star-free DL-PA can be extended to the variant of DL-PA where symbolic disjunctions that are parametrised by sets (that are not defined as abbreviations, but are proper connectives) are built into the language. As our merging operators can be polynomially embedded into this variant of DL-PA, we obtain that both the model checking and the satisfiability problem of a formula containing possibly nested merging operators is in PSPACE.

Introduction

To merge a vector of belief bases E = B 1 , • • • , B n means to build a new belief base ∆(E). In the literature, E is called a profile, and ∆(E) is sometimes called the fusion of E. Much efforts were spent on the characterisation of 'good' merging operations ∆ by means of rationality postulates [START_REF] Konieczny | Logic based merging[END_REF][START_REF] Konieczny | On the logic of merging[END_REF][START_REF] Konieczny | Merging with integrity constraints[END_REF]. Beyond such families of abstract belief merging operations satisfying the postulates, several concrete operations were also introduced and studied in the literature. Some are syntax-based and others are semantic. The former are also called 'formula-based', and the latter are called 'model-based' or 'distancebased'. An example of the former is the MCS operation [START_REF] Baral | Combining knowledge bases consisting of first-order theories[END_REF], where each element B i of E is viewed as a set of formulas that is not closed under logical consequence and where the construction of ∆(E) is based on the extraction of maximal consistent subsets of each B i of E. Such operations are syntax dependent: they do not guarantee that the merging of logically equivalent profiles leads to merged bases that are logically equivalent. 1 In contrast, syntax independence is guaranteed by the semantic merging operations, whose most prominent are ∆ Σ , ∆ max , and ∆ Gmax [START_REF] Lin | Knowledge base merging by majority[END_REF][START_REF] Revesz | On the semantics of theory change: arbitration between old and new information[END_REF]. These operations work on valuations of classical propositional logic. Indeed, even when the elements of the input profile are presented as formulas or sets thereof, the merging procedure starts by computing their models. The output set of valuations is sometimes transformed into a formula characterising the set, which can always be done because these operations are presented in terms of a finite set of propositional variables.

Contrasting with the existing literature, the present paper studies concrete semantic merging operations from a syntactic perspective: given a vector of formulas E, our aim is to obtain a syntactical representation of the merged belief base ∆(E), for ∆ being ∆ Σ , ∆ max , or ∆ Gmax . As we have already said above, when the language is finite then it is easy to construct a formula representing ∆(E): it suffices to take the disjunction of the formulas describing the models of ∆(E), where each of these model descriptions is a conjunction of literals. Is there a better, more direct way of building a syntactic representation? In this paper we propose a powerful yet simple logical framework: Dynamic Logic of Propositional Assignments, abbreviated DL-PA [START_REF] Balbiani | Dynamic logic of propositional assignments: A wellbehaved variant of PDL[END_REF]. DL-PA is a simple instantiation of Propositional Dynamic Logic PDL [START_REF] Harel | Dynamic logic[END_REF][START_REF] Harel | Dynamic Logic[END_REF]. Just as PDL, its language is built with two ingredients: atomic formulas and atomic programs. In both logics, atomic formulas are propositional variables. While PDL has abstract atomic programs, the atomic programs of DL-PA are assignments of propositional variables to either true or false, respectively noted p←⊤ and p←⊥. The assignment p←⊤ corresponds to an update by p, while the assignment p←⊥ corresponds to an update by ¬p. Complex programs π are built from atomic programs by the standard PDL program operators of sequential composition, nondeterministic composition, finite iteration (the so-called Kleene star), and test. Just as PDL, DL-PA has formulas of the form π ϕ and [π]ϕ, where π is a program and ϕ is a formula. The former expresses that ϕ is true after some possible execution of π, and the latter expresses that ϕ is true after every possible execution of π. For example, the DL-PA formula p←⊤ ∪ p←⊥ ϕ captures the propositional quantification ∃p.ϕ, illustrating that DL-PA naturally captures Quantified Boolean Formulas (QBF). It is shown in [START_REF] Balbiani | Dynamic logic of propositional assignments: A wellbehaved variant of PDL[END_REF] that DL-PA formulas can be reduced to equivalent Boolean formulas. Just as for QBFs, the original formula is more compact than the equivalent Boolean formula. Star-free DL-PA has the same mathematical properties as the QBF reasoning problems; in particular, model checking, satisfiability and validity are all PSPACE complete. We believe DL-PA to be a more natural and flexible tool than QBF to reason about domains involving dynamics due to its more elaborate account in terms of programs.

Our main contributions are polynomial embeddings of semantic belief merging operators into DL-PA: to every profile E and merging operation ∆ we associate a DL-PA formula ϕ(∆, E), and we prove that the merged profile ∆(E) has the same models as ϕ(∆, E). Then ϕ(∆, E) may then be reduced to a Boolean formula, thus providing a syntactical representation of ∆(E) in propositional logic. A further contribution of our paper is a presentation of merging in terms of a recursive language with several merging operators ∆ σ in the object language, one operator per semantics σ. This contrasts with the usual presentations in terms of metalanguage operations (where we systematically use the term operator for connectives in the object language, while we reserve the term operation for functions from the metalanguage).

The paper is organized as follows. In Section 2 we give the basic notation for propositional logic and recall the semantic definitions of the concrete merging operations ∆ Σ , ∆ Gmax , and ∆ max . In Section 3 we take a more syntactical stance: instead of viewing ∆ as an operation in the metalanguage, we introduce a recursive language with families of n-ary merging operators in the object language and reformulate the above concrete merging operations in that language. In Section 4 we recall DL-PA. In Section 5 we embed the three merging operations into DL-PA. Section 6 concludes.

Background

We recall some standard notations and conventions for propositional logic, in particular distances between its valuations, as well as the definitions of the three concrete Boolean merging operators we are interested in.

Propositional Logic

Boolean formulas are built by means of the standard connectives ¬, ∨, etc. from a countable set of propositional variables P = {p, q, . . .}. We will in particular use the exclusive disjunction ⊕. We denote them by letters such as A, B, C; in particular, we use B, B 1 , B 2 , etc. for Boolean belief bases, which we identify with Boolean formulas.

Contrasting with that, modal formulas-to be defined in the next section-will be denoted by ϕ, ψ, etc. For a given Boolean formula A, the set of variables occurring in A is noted P A . For example, P p∨¬q = {p, q}.

A valuation associates a truth value to each propositional variable. We identify valuations with subsets of P and use v, v 1 , v 2 , etc. to denote them. The set of all valuations is V = 2 P . Sometimes it will be convenient to view v as a function from Boolean formulas into the set of truth values {0, 1} and to write v(p) = 1 when p ∈ v and v(p) = 0 when p v.

Given a valuation v and a Boolean formula A, the truth value v(A) ∈ {0, 1} is determined in the usual way. When v(A) = 1 then we say that v is an A-valuation. For example, {p, q} is a ¬p∨¬r valuation. The set of all A-valuations is denoted ||A||. For example, ||p|| = {v ∈ V : p ∈ v} and ||p ∨ q|| = {v ∈ V : p ∈ v or q ∈ v} = ||p|| ∪ ||q||.

Distances

The Hamming distance between two valuations v 1 and v 2 is the cardinality of the symmetric difference between v 1 and v 2 :

d H (v 1 , v 2 ) = card (v 1 \ v 2 ) ∪ (v 2 \ v 1 ) = card {p ∈ P : v 1 (p) v 2 (p)} . So d H (v 1 , v 2 )
is the number of all those p such that v 1 (p) v 2 (p). For example, the Hamming distance between ∅ and {p, q} is card ∅ ∪ {p, q} = 2, and the Hamming distance between {p, q} and {q, r, s} is card {r, s} ∪ {p} = card {p, r, s} = 3. Note that the Hamming distance might be infinite; for instance, d H (∅, P) = ∞.

The definition of Hamming distance can be extended to a distance between a valuation v and a set of valuations V ⊆ V as follows:

d H (v, V) =        0 if V = ∅ min({d H (v, v ′ ) : v ′ ∈ V}) otherwise
This leads to the definition of the Hamming distance between a valuation and a Boolean formula as d H (v, B) = d H (v, ||B||). For example:

d H ({p, q}, p∧¬p) = 0 d H ({p, q}, p∧q) = 0 d H ({p, q}, ¬p∨q) = 0 d H ({p}, ¬p∨q) = 0 d H ({p, q}, ¬p∨¬q) = 1 d H ({p, q}, ¬p∧¬q) = 2 d H ({p, q}, ¬p∨¬r) = 0 d H ({p, q}, (¬p∨¬r)∧¬q) = 1 Lemma 1. For every valuation v, d H (v, B) ≤ card(P B ). Proof. Let v be a valuation. If ||B|| = ∅ then d H (v, B) = d H (v, ||B||) = d H (v, ∅) = 0 and the lemma is correct. Otherwise, let v ′ ∈ ||B||. Without loss of generality, we can assume that for all p P B , v(p) = v(p ′ ). Thus, d H (v, v ′ ) ≤ card(P B ). By definition of d H (v, B) we have d H (v, B) = d H (v, ||B||) ≤ d H (v, v ′ ) ≤ card(P B ).
Finally, the Hamming distance between a valuation v and a vector of Boolean belief bases B 1 , . . . , B n is defined to be the vector of the distances:

d H (v, B 1 , . . . , B n ) = d H (v, B 1 ), • • • , d H (v, B n )
For example:

d H ({p}, ¬p∨¬q ) = 1 d H ({p, q}, ¬p∨¬r, (¬p∨¬r)∧¬q ) = 0, 1 d H ({p, q}, ¬p∨q, ¬p∨¬q, ¬p∧¬q ) = 0, 1, 2

Various Merging Operations

A profile, typically noted E, is a vector of belief bases:

E = B 1 , • • • , B n .
The traditional definition of a belief merging operation is as a mapping ∆ associating to every profile E a new belief base ∆(E). Such operations have been defined in several different ways and that is why we indicate a particular definition σ by a superscript and write ∆ σ (E). Throughout the present paper we suppose that there is no preference between the belief bases of a profile: we assume that

∆ σ (ϕ 1 , • • • , ϕ n ) is equivalent to ∆ σ (ϕ k 1 , • • • , ϕ k n ), for every permutation ϕ k 1 , • • • , ϕ k n of ϕ 1 , • • • , ϕ n .
The reader may therefore view the vector as a set. We stick to the vector notation for two reasons: first, it is common in the merging literature, and second, it better fits the object language operators to be introduced in the next section.

Perhaps the best starting point is the merging operation that is based on minimisation of the sum of the Hamming distances to each belief base B i of E, abbreviated ∆ Σ . It associates to every profile E the set of valuations such that the sum of the distances to the elements of E is minimal. Formally:

∆ Σ (E) = v ∈ V : there is no v ′ ∈ V such that d H (v ′ , E) < d H (v, E) .
For example:

∆ Σ (p, ¬p∨q) = {v : p, q ∈ v} = ||p ∧ q|| ∆ Σ (p∧q, ¬p∧¬q) = 2 P = ||⊤||
Beyond ∆ Σ we consider other concrete merging operations: the Gmax merging operation ∆ Gmax and the max merging operator ∆ max . Their definitions are based on other minimisations. We do not give them here; instead, they will be presented in the next section in terms of object language operators.

Merging can also be done under integrity constraints. This leads to more general operations ∆ σ ψ (E) where the formula ψ is an integrity constraint that the merged belief base should satisfy. The unconstrained ∆ σ (E) can then be identified with ∆ σ ⊤ (E). Then the ∆ Σ operation becomes:

∆ Σ ψ (E) = v ∈ ||ψ|| : there is no v ′ ∈ ||ψ|| such that d H (v ′ , E) < d H (v, E) .
For example, ∆ Σ ¬r (p, ¬p∨q) = ||p ∧ q ∧ ¬r|| and ∆ Σ p (p∧q, ¬p∧¬q) = ||p||. Observe that in the above definitions ∆ C (E) is a set of valuations. In contrast, the merging postulates to be given below are defined in terms of formulas: as already mentioned, papers on merging operations typically identify the set ∆ C (E) with the Boolean formula characterising it.

The Postulates for Merging with Integrity Constraints

We briefly recall the principles for merging operations that were introduced by Konieczny and Pino Pérez. We here present the version of [START_REF] Konieczny | Logic based merging[END_REF], in a slightly adapted version because there, belief bases are considered to be finite sets of formulas (which are however often identified with their conjunction).

Let ∆ be an mapping assigning to each belief profile E and integrity constraint C a belief base ∆ C (E). ∆ is a merging operation if and only if it satisfies the following postulates.

(IC0) ∆ C (E) → C is valid. (IC1) If C is satisfiable then ∆ C (E) is satisfiable. (IC2) If C ∧ ( E) is satisfiable then ∆ C (E) ↔ E is valid. (IC3) For E = B 1 , • • • , B n and E ′ = B ′ 1 , • • • , B ′ n , if C ↔ C ′ and B i ↔ B ′ i are valid for 1≤i≤n then ∆ C (E) ↔ ∆ C ′ (E ′ ) is valid. (IC4) If ∆ C B, B ′ ∧ B is satisfiable then ∆ C B, B ′ ∧ B ′ is satisfiable. (IC5) ∆ C (E) ∧ C ′ → ∆ C∧C ′ (E) is valid. (IC6) If ∆ C (E) ∧ C ′ is satisfiable then ∆ C∧C ′ (E) → ∆ C (E) is valid.
In the above postulates, 'satisfiable' means 'propositionally satisfiable' and 'valid' means 'propositionally valid'.

The operations ∆ Σ and ∆ Gmax satisfy all the postulates, while the max merging operator ∆ max does not. Nonetheless, many authors in the literature consider that the latter is an interesting merging operator.

A Modal Framework for Merging Operators

The ∆ σ are not logical connectives of the object language: they are part of the metalanguage. We highlight that by saying that they are operations. The merging operators to be introduced now are connectives of the object language, just as the Boolean operators ¬ and ∨ are. 2 For that reason we also write them differently as σ : for each semantics σ we have an object language operator σ . 3 It is an advantage of such a move that many things can then be proved in a formal, rigorous way inside a logical system, as opposed to lines of argument in natural language texts. Moreover, it also allows to take advantage of mathematical results such as complexity upper bounds and theorem proving methods for the logic.

If merging operators are in the object language, we have enough flexibility to nest merging operators and even talk about different semantics in the same formula, as illustrated by the well-formed formula σ 1 σ 2 (p,q) (p, p∨q). To motivate this, consider a company whose productivity is declining and whose shareholders desire to implement a motivation policy in order to change the workers' conditions. They then have to merge the desires of every worker, while preserving several kinds of integrity constraints: job security, working environment, salary costs, job satisfaction. These different criteria have to be merged in their turn.

Formulas involving one or more kinds of merging operators may be given as an input to a reasoner. Observe that when we define the length of the input for the reasoner then one occurrence of a merging operator counts for 1 and certainly not for the length of the disjunction describing the corresponding set of valuations (as would be the case in the metalinguistic presentation).

Language

Our logical language L is defined by the following grammar:

ϕ p | ¬ϕ | ϕ∨ϕ | σ ϕ (ϕ, • • • , ϕ)
where p ranges over the set of propositional variables P and where σ ranges over the set of symbols {Σ, Gmax, max}. The informal reading of the formula σ ψ (E) is "the profile E has been merged (with merging semantics σ) under the constraint ψ".

Abusing language a bit, when the profile is E = ϕ 1 , . . . , ϕ n then instead of σ ψ (E) we write σ ψ (ϕ 1 , • • • , ϕ n ). The function P . associating to a formula the set of its propositional variables naturally extends to our language; in particular we have

P σ ψ (ϕ 1 ,••• ,ϕ n ) = P ψ ∪ 1≤i≤n P ϕ i .
In the rest of the present section we introduce the truth conditions for the three merging operators Σ , Gmax , and max . Clearly, when the profile E = B 1 , . . . , B n and the constraint C are Boolean then we expect the interpretation of the merging operator σ under semantics σ to coincide with the merging operation ∆ σ defined in Section 2.3. In formulas, we expect the equality

∆ σ C (E) = || σ C (E)
|| to hold for Boolean C and E.

The Σ-Semantics

The interpretation of Σ is the set of valuations such that the sum of the distances to the elements of E is minimal. Formally:

|| Σ ψ (E)|| = v ∈ ||ψ|| : there is no v ′ ∈ ||ψ|| such that d H (v ′ , E) < d H (v, E) .
The definition of the Hamming distance d H is as in Section 2.

The Gmax-Semantics

The interpretation of Gmax is as follows:

|| Gmax ψ (E)|| = v ∈ ||ψ|| : there is no v ′ ∈ ||ψ|| such that d sort H (v ′ , E) < lex d sort H (v, E)
where

d sort H (v, E) = sort(d(v, ϕ 1 ), . . . , d(v, ϕ n ))
is the list that is obtained from the vector d(v, ϕ 1 ), . . . , d(v, ϕ n ) by sorting it in descending order and where < lex is the lexicographical order between sequences of integers of the same length.

For example,

|| Gmax ⊤ (p∧q, ¬p∧¬q)|| = {v : v(p) v(q)} = ||p⊕q|| because d sort H (v, p∧q, ¬p∧¬q ) =        2, 0 if v(p) = v(q) 1, 1
otherwise.

The max-Semantics

The interpretation of max is as follows:

|| max ψ (E)|| max = v ∈ ||ψ|| : there is no v ′ ∈ ||ψ|| such that max d H (v ′ , E) < max d H (v, E)
where max d H (v, E) is the maximum of all the distances d H (v, ϕ i ) between v and the elements ϕ i of E. For example, || max ⊤ (p∧q, ¬p∧¬q)|| = {v : v(p) v(q)} = ||p⊕q|| because for the valuations v such that v(p) v(q) we have that d H (v, p∧q, ¬p∧¬q ) equals 1, 1 (and therefore the maximum of that vector is 1), while for the v such that v(p) = v(q) the distance d H (v, p∧q, ¬p∧¬q ) is either 0, 2 or 2, 0 (and therefore the maximum is 2).

We recall that the max-semantics does not satisfy Konieczny and Pino Pérez's merging postulates. We also note that for the empty integrity constraint we have

|| Gmax ⊤ (E)|| ⊆ || max
⊤ (E)|| for every profile E.

DL-PA: Dynamic Logic of Propositional Assignments

In this section we define syntax and semantics of dynamic logic of propositional assignments DL-PA and state complexity results. The star-free fragment of DL-PA was introduced in [START_REF] Herzig | A dynamic logic of normative systems[END_REF], where it was shown that it embeds Coalition Logic of Propositional Control [START_REF] Van Der Hoek | On the logic of cooperation and the transfer of control[END_REF][START_REF] Van Der Hoek | On the dynamics of delegation, cooperation and control: A logical account[END_REF][START_REF] Van Der Hoek | On the logic of cooperation and propositional control[END_REF]. The full logic with the Kleene star was further studied in [START_REF] Balbiani | Dynamic logic of propositional assignments: A wellbehaved variant of PDL[END_REF].

Language

The language of DL-PA is defined by the following grammar:

π p←⊤ | p←⊥ | π; π | π∪π | ϕ? | π * ϕ p | ⊤ | ⊥ | ¬ϕ | ϕ∨ϕ | π ϕ
where p ranges over the set of propositional P. So the atomic programs of the language of DL-PA are of the form p←⊤ and p←⊥. The operators of sequential composition (";"), nondeterministic composition ("∪"), unbounded iteration ("(.) * ", the so-called Kleene star), and test ("(.)?") are familiar from Propositional Dynamic Logic PDL.

The length of a formula ϕ, denoted |ϕ|, is the number of symbols used to write down ϕ, without " ", " ", parentheses and commas. For example, |q∧r| = |¬(¬q∨¬r)| = 6 and | q←⊤ (q∧r)| = 2+6 = 8. The length of a program π, denoted |π|, is defined in the same way. For example, |p←⊥; p?| = 5.

We abbreviate the logical connectives ∧, →, ↔, and ⊕ in the usual way. Moreover, [π]ϕ abbreviates ¬ π ¬ϕ. Several program abbreviations are familiar from PDL. First, skip abbreviates ⊤? ("nothing happens"). Second, the loop "while A do π" can be expressed as the DL-PA program (A?; π) * ; ¬A?. Third, for n ≥ 0, the n-th iteration of π is defined inductively as:

π 0 = skip π n+1 = π n ; π
Let us now introduce the assignment of literals to variables by means of the following abbreviations that are proper to DL-PA: p←q = (q?; p←⊤) ∪ (¬q?; p←⊥) p←¬q = (q?; p←⊥) ∪ (¬q?; p←⊤)

The former assigns to p the truth value of q, while the latter assigns to p the truth value of ¬q. The length of p←q is (2 + 1 + 3) + 1 + (3 + 1 + 3) = 14. That of p←¬q is 14, too.

The star-free fragment of DL-PA is the subset of the language made up of formulas without the Kleene star "(.) * ".

Semantics of DL-PA

DL-PA programs are interpreted by means of a (unique) relation between valuations. The atomic programs p←⊤ and p←⊥ update valuations in the obvious way, and complex programs are interpreted just as in PDL by mutual recursion. Table 1 gives the interpretation of the DL-PA connectives. In DL-PA, all the program operators can be eliminated: for every formula ϕ there is a formula equivalent ϕ ′ such that no program operator occurs in ϕ ′ [1, Theorem 1]. For example, p←⊤ * r is equivalent to p ∨ p←⊤ r and p←⊤; q←⊤ r is equivalent to p←⊤ q←⊤ r. This contrasts with PDL, where this is not the case. Once all the program operators have been eliminated, modal operators only contain atomic programs. The latter are both serial and deterministic modal operators and therefore distribute over negation and disjunction. They can finally be eliminated when they face a propositional variable, according to the following equivalences:

||p←⊤|| = { v 1 , v 2 : v 2 = v 1 ∪ {p}} ||p←⊥|| = { v 1 , v 2 : v 2 = v 1 \ {p}} ||π; π ′ || = ||π|| • ||π ′ || ||π ∪ π ′ || = ||π|| ∪ ||π ′ || ||π * || = k∈N 0 (||π||) k ||ϕ?|| = { v, v : v ∈ ||ϕ||} ||p|| = {v : p ∈ v} ||⊤|| = V = 2 P ||⊥|| = ∅ ||¬ϕ|| = 2 P \ ||ϕ|| ||ϕ∨ψ|| = ||ϕ|| ∪ ||ψ|| || π ϕ|| = v : there is v 1 s.t. v, v 1 ∈ ||π|| and v 1 ∈ ||ϕ||
p←⊤ q ↔        ⊤ if q = p q otherwise p←⊥ q ↔        ⊥ if q = p q otherwise
All together, we have a complete set of reduction axioms: every formula reduces to a Boolean formula [START_REF] Balbiani | Dynamic logic of propositional assignments: A wellbehaved variant of PDL[END_REF]Theorem 2].

Theorem 1. For every DL-PA formula ϕ there is a Boolean formula ϕ ′ such that ϕ ↔ ϕ ′ is DL-PA valid.

For example, for different propositional variables r and p, the formula p←q (p ∨ r) is successively equivalent to p←q p ∨ p←q r and to q ∨ r.

It is proved in [START_REF] Herzig | A dynamic logic of normative systems[END_REF] that both model and satisfiability checking are PSPACE complete for the star-free fragment of DL-PA.

Observe that if p does not occur in ϕ then both ϕ → p←⊤ ϕ and ϕ → p←⊥ ϕ are valid. This is due to the following semantical property that we will use later.

Proposition 1. Suppose P ϕ ∩ P = ∅, i.e., none of the variables in P occurs in ϕ. Then v ∪ P ∈ ||ϕ|| iff v \ P ∈ ||ϕ||.

In the rest of the paper we write ||ϕ|| DL-PA in order to distinguish the interpretation of DL-PA formulas from the interpretation of the merging language.

Some Useful DL-PA Expressions

Table 2 collects some DL-PA expressions that are going to be convenient abbreviations. 4The program vary(P) nondeterministically changes the truth value of some of the variables in P. Its length is linear in the cardinality of P. So the program vary(P A ); A? accesses all A-valuations that preserve the values of all those variables not occurring in A. Satisfiability of the Boolean formula A can be expressed in DL-PA by the formula vary(P A ); A? ⊤ or the equivalent vary(P A ) A. The program flip 1 (P) changes the truth value of exactly one of the variables in P. The programs flip ≤m (P) flip the truth value of at most m of the variables in P. The lengths of flip m (P) and flip ≤m (P) are quadratic in n. The formula H(ϕ, ≥d) is true in all those valuations whose Hamming distance to ϕ is d.

vary(P) = (p 1 ←⊤ ∪ p 1 ←⊥); • • • ; (p n ←⊤ ∪ p n ←⊥) flip m (P) =        skip if m = 0 p 1 ←¬p 1 ∪• • •∪p n ←¬p n ; flip m-1 (P) if m ≥ 1 flip ≤m (P) =        skip if m = 0 skip∪flip 1 (P) ; flip ≤m-1 (P) if m ≥ 1 H(ϕ, d) =        ϕ if m = 0 ¬ flip ≤d-1 (P ϕ ) ϕ ∧ flip d (P ϕ ) ϕ if m ≥ 1
For example:

H(p, 1) = ¬ flip ≤0 ({p}) p ∧ flip 1 ({p}) p ↔ ¬p ∧ p←¬p p ↔ ¬p ∧ ¬p ↔ ¬p H(¬p∨q, 0) ↔ ¬p∨q H(¬p∨q, 1) ↔ ¬(¬p∨q) ∧ p←¬p (¬p∨q) ↔ p ∧ ¬q ∧ (p∨q) ↔ p ∧ ¬q H(¬p∨q, 2) = ¬ (skip ∪ p←¬p); skip (¬p∨q) ∧ p←¬p; p←¬p (¬p∨q) ↔ ¬ (¬p∨q) ∨ (p∨q) ∧ (¬p∨q) ↔ ⊥ Lemma 2.
The following hold:

1. v 1 , v 2 ∈ ||vary(P)|| iff (v 1 \ v 2 ) ∪ (v 2 \ v 1 ) ⊆ P. 2. v 1 , v 2 ∈ ||flip 1 (P)|| iff v 1 , v 2 ∈ ||vary(P)|| and card(v 1 -v 2 ) = 1. 3. v 1 , v 2 ∈ ||flip ≤m (P)|| iff v 1 , v 2 ∈ ||vary(P)|| and card(v 1 -v 2 ) ≤ m. 4. v ∈ ||H(ϕ, d)|| iff d H (v, ϕ) = d.
Note that flip m (P) is nothing but the m-th iteration of flip 1 (P), so one variable might be switched twice and therefore v 1 , v 2 ∈ ||flip m (P)|| does not in general imply that the Hamming distance between v 1 and v 2 is m.

Embedding Merging Operators into DL-PA

In this section, we define a translation tr(.) by induction over the formulas of our merging language L . To every formula ϕ of our merging language L we associate a DL-PA formula tr(ϕ). The Boolean part is translated as follows:

tr(p) = p tr(¬ϕ) = ¬tr(ϕ) tr(ϕ ∨ ψ) = tr(ϕ) ∨ tr(ψ)
In the three subsections we give the inductive cases of the definition of tr(.) for Σ , Gmax and max . We then prove that the translation is correct and that it gives us an algorithm to reason in L from an algorithm to reason in DL-PA. The reader may observe that our encodings are not particularly sophisticated and follow the semantic definitions in a fairly straightforward manner.

Embedding the Σ-Semantics

Let us define the translation for the Σ as follows. Given a profile E = ϕ 1 , . . . , ϕ n , we define:

tr( Σ ψ (E)) = tr(ψ) ∧ d 1 ,...,d n ,d k ≤card(P ϕ k ) i≤n H(tr(ϕ i ), d i ) ∧ ¬ vary(P E ) tr(ψ) ∧ d ′ 1 ,...,d ′ n , k≤n (d ′ k )< k≤n (d k ) i≤n H(tr(ϕ i ), d ′ i ) .
Intuitively, the translation does the following: first, the integrity constraint is required to be true (by tr(ψ)), second, it is checked that there is some vector d 1 , . . . , d n of integers such that the Hamming distance from the present valuation to each tr(ϕ i )-valuation is d i (by H(tr(ϕ i ), d i )) and such that one cannot go to another valuation (by ¬ vary(P E ) ) satisfying the constraint and whose sum of distances to the tr(ϕ i )-valuations is smaller. As we are going to show, every model of the formula tr( Σ ψ (E)) is indeed a model of the merged profile.

For example, tr( Σ ⊤ (p, ¬p∨q) ) is

⊤ ∧ H(p, 0) ∧ H(¬p∨q, 0) ∧ ¬ vary({p, q}) ⊤ ∧ ⊥ ∨ H(p, 0) ∧ H(¬p∨q, 1) ∧ ¬ vary({p, q}) ⊤ ∧ H(p, 0) ∧ H(¬p∨q, 0) ∨ H(p, 1) ∧ H(¬p∨q, 0) ∧ ¬ vary({p, q}) ⊤ ∧ H(p, 0) ∧ H(¬p∨q, 0) ∨ H(p, 1) ∧ H(¬p∨q, 1) ∧ ¬ vary({p, q}) ⊤ ∧ ((H(p, 0) ∧ H(¬p∨q, 0)) ∨ • • • ) which is equivalent to (p ∧ (¬p ∨ q) ∧ ⊤) ∨ (p ∧ (p ∧ ¬q) ∧ ⊥) ∨ (¬p ∧ (¬p ∨ q) ∧ ⊥) ∨ (¬p ∧ (p ∧ ¬q) ∧ • • • ),
i.e., to p ∧ q.

Here is another example:

tr( Σ ⊤ (p∧q, ¬p∧¬q)) ↔ ⊤ ∧ H(p∧q, 0) ∧ H(¬p∧¬q, 2) ∨ ↔ ⊤∧ H(p∧q, 1) H(¬p∧¬q, 1) ∨ ↔ ⊤∧ H(p∧q, 2) ∧ H(¬p∧¬q, 0) ↔ (p∧q) ∨ ↔ (¬p∧q) ∨ (p∧¬q) ∨ ↔ (¬p∧¬q) ↔ ⊤

Embedding the Gmax-Semantics

The embedding of the Gmax-operator is in the same spirit as that of the previous operator. Given a profile E = ϕ 1 , . . . , ϕ n , we define:

tr( Gmax ψ (E)) = tr(ψ) ∧ d 1 ,...,d n , d k ≤card(P ϕ k ) i≤n H(tr(ϕ i ), d i ) ∧ ¬ vary(P E ) tr(ψ) ∧ d ′ 1 ,...,d ′ n ,sort(d ′ 1 ,...,d ′ n )< lex sort(d 1 ,...,d n ) i≤n H(tr(ϕ i ), d ′ i ) .
Intuitively, the translation checks the integrity constraints and checks for the vector characterising the Hamming distances to the ϕ i -valuations that there exists no other valuation tr(ψ) whose distance vector is smaller according to the sorted lexicographic ordering. Table 3 contains an example. Another example is tr( Gmax ⊤ (p∧q, ¬p∧¬q)), which reduces to p ↔ q.

Embedding the max-Semantics

In a first try we have:

tr( ψ (E)) = tr(ψ) ∧ d 1 ,...,d n , d k ≤card(P ϕ k ) i≤n H(tr(ϕ i ), d i ) ∧ ¬ vary(P E ) tr(ψ) ∧ d ′ 1 ,...,d ′ n ,max k≤n (d ′ k )<max k≤n (d k ) i≤n H(tr(ϕ i ), d ′ i ) .
This can actually be made more concise, and our official definition of the translation is as follows:

tr( ψ (E)) = tr(ψ) ∧ d,
= ⊤ ∧ H(p, 0) ∧ H(p, 0) ∧ H(¬p, 0) ∧ ¬ vary({p}) (⊤ ∧ ⊥) ∨ ⊤ ∧ H(p, 0) ∧ H(p, 0) ∧ H(¬p, 1) ∧ ¬ vary({p}) (⊤ ∧ H(p, 0) ∧ H(p, 0) ∧ H(¬p, 0)) ∨ ⊤ ∧ H(p, 0) ∧ H(p, 1) ∧ H(¬p, 0) ∧ ¬ vary({p}) (• • • ) ∨ ⊤ ∧ H(p, 0) ∧ H(p, 1) ∧ H(¬p, 1) ∧ ¬ vary({p}) (• • • ) ∨ ⊤ ∧ H(p, 1) ∧ H(p, 0) ∧ H(¬p, 0) ∧ ¬ vary({p}) (• • • ) ∨ ⊤ ∧ H(p, 1) ∧ H(p, 0) ∧ H(¬p, 1) ∧ ¬ vary({p}) (• • • ) ∨ ⊤ ∧ H(p, 1) ∧ H(p, 1) ∧ H(¬p, 0) ∧ ¬ vary({p}) (• • • ) ∨ ⊤ ∧ H(p, 1) ∧ H(p, 1) ∧ H(¬p, 1) ∧ ¬ vary({p}) (• • • ) ↔ (p ∧ p ∧ ¬p ∧ ¬⊥) ∨ (p ∧ p ∧ p ∧ ¬⊥) ∨ (p ∧ ¬p ∧ ¬p ∧ ¬⊥) ∨ (p ∧ ¬p ∧ p ∧ ¬⊥) ∨ (¬p ∧ p ∧ ¬p ∧ ¬⊥) ∨ (¬p ∧ p ∧ p ∧ ¬⊥) ∨ (¬p ∧ ¬p ∧ ¬p ∧ ¬⊤) ∨ (¬p ∧ ¬p ∧ p ∧ ¬⊥) ↔ p
Intuitively, the integrity constrained is enforced and it is checked for some integer d that first, each ϕ i in the profile has distance at most d and second, that there is no other valuation that both satisfies the integrity constraint and is strictly less than d away from each ϕ i . Proof. The proof is by induction on the form of ϕ. The only interesting case is that of merging operators. Let us consider the case of Σ . We prove in detail that Item 2 means that the formula

Correction of the Translations

|| Σ ψ (E)|| = ||tr( Σ ψ (E))|| DL-PA . Let v ∈ V be a valuation. We have v ∈ || Σ ψ (E)|| iff v ∈ ||ψ||
d ′ 1 ,••• ,d ′ n , k (d ′ k )< k (d k ) i≤n H(tr(ϕ i ), d ′ i )
is unsatisfiable. According to Lemma 2 and Proposition 1, all the relevant valuations are accessed by the program vary(P E ). Therefore Item 2 is equivalent to

v ∈ ||¬ vary(P E ) tr(ψ) ∧ d ′ 1 ,••• ,d ′ n , k≤n (d ′ k )< k (d k ) i≤n H(tr(ϕ i ), d ′ i ) || DL-PA .
Putting things together, items 1 and 2 are equivalent to v ∈ ||tr(

Σ ψ (ϕ 1 , • • • , ϕ n ))|| DL-PA .
It follows from the above theorem that the merging of the Boolean profile

B 1 , • • • , B n under the Boolean constraint C equals ||tr( σ C (B 1 , • • • , B n ))|| DL-PA . The length of tr(ϕ) is however exponential in the length of ϕ. Nevertheless, if we consider 'big disjunctions' such as d 1 ,...,d n ,d k ≤card(P ϕ k ) , d ′ 1 ,...,d ′ n , k (d ′ k )< k (d k ) etc
. to be connectives of the object language-i.e., as symbolic disjunctions that are parametrised by sets and that are not defined as abbreviations, but are proper connectives-then the length of tr(ϕ) is still polynomial in the length of ϕ. For instance, the length of

d ′ 1 ,••• ,d ′ n , k (d ′ k )< k (d k ) i≤n H(ϕ Σ i , d ′ i ) is O(n) plus the length of H(ϕ Σ i , d ′ i ).
Corollary 1. Both model checking and satisfiability checking of L -formulas is in PSPACE.

Proof. First we give the argument why both model and satisfiability checking are PSPACE-complete for the star-free fragment of DL-PA if we allow symbolic disjunctions in DL-PA formulas. We do so by adapting the proof of PSPACE membership of [START_REF] Herzig | A dynamic logic of normative systems[END_REF]: in order to check whether

d ′ 1 ,...,d ′ n , k (d ′ k )< k (d k ) ψ is true at a valuation v we backtrack and test all the choices d ′ 1 , . . . , d ′ n such that k (d ′ k ) < k (d k )
. This backtrack process can be implemented as an algorithm that only uses a polynomial amount of memory. By Theorem 2 we then reduce polynomially model (satisfiability) checking of L ∆ formulas to model (satisfiability) checking of a DL-PA-formulas, where 'big disjunctions' are viewed as being symbolic.

Note that the language of DL-PA is more succinct than that of Boolean formulas: although every formula of DL-PA is equivalent to a Boolean formula, equivalent Boolean formulas can be exponentially bigger. So SAT techniques for propositional logic do not provide interesting decision procedures for L .

We have defined a single L in which all merging operators are in the object language: they are considered to modal operators and can be nested. This differs with other approaches such as [START_REF] Liberatore | Brels: A system for the integration of knowledge bases[END_REF] and [START_REF] Gorogiannis | Implementing semantic merging operators using binary decision diagrams[END_REF]. As far as we know, the only similar approach is [START_REF] Lang | Reasoning under inconsistency: forgetting-based approach[END_REF], where the merging operator (as well as the comma separating the elements of profiles) are considered to be in the object language.

We have then embedded this language into Dynamic Logic of Propositional Assignments, DL-PA. This has enabled us to give syntactic counterparts to the most popular semantically defined merging operations. Using the reduction principles of DL-PA we can therefore rewrite formulas to Boolean formulas. As our examples show, such formulas may be quite long; in particular, they typically contain a lot of disjunctions. They can however often be simplified by means of standard syntactical operations. This provides interesting syntactical representations of merged belief bases.

The logic DL-PA actually provides a sort of assembler language for merging operators. Its use avoids the design of specific tools implementing merging operators. Unfortunately, no efficient reasoning mechanisms for DL-PA exist up to now, and it would be interesting to have such tools. (It could also be based on Binary Decision Diagrams as in [START_REF] Gorogiannis | Implementing semantic merging operators using binary decision diagrams[END_REF].) As we have seen, if we want the embeddings to be polynomial then such tools should be able to handle 'big disjunctions' and 'big conjunctions'.

The star-free fragment of DL-PA into which we have mapped various merging operators has PSPACE complexity (both model checking and satisfiability). This induces a result for our merging language L , which is new because L authorizes arbitrary nesting of merging operators. It is possible that the translated formulas however have patterns that are less complex.

As to future work, a first perspective is to study the mathematical properties of merging operators in more detail. One example is the behaviour of iterated merging operators (which is a research project similar to that for iterated belief revision, see e.g. [START_REF] Darwiche | On the logic of iterated belief revision[END_REF].) Reasoning should be considerably facilitated by the help of a DL-PA reasoner. For instance, suppose we want to know whether the operator max ⊤ is associative. We may run the following experimental protocol: first, choose some Boolean formulas A, B, C and write down the formula max ⊤ (A, max ⊤ (B, C)) ↔ max ⊤ ( max ⊤ (A, B), C); second, translate this formula into DL-PA; third, run a DL-PA reasoner. Note however that one cannot use the theorem proving procedure for DL-PA because it only works for formula instances and not for formula schemas. (This is related to the fact that the rule of uniform substitution does not preserve validity in DL-PA, which generally fails in dynamic logics).

Our embeddings are somewhat simpler than the embeddings of belief change operations into QBF as done in [START_REF] Delgrande | On computing belief change operations using quantified boolean formulas[END_REF] since DL-PA is a logic of programs. The same argument applies to embeddings of merging problems into MSO. Our approach may also be useful to capture semantics of merging: one may think in particular of new semantics requiring loops, which can be directly captured in DL-PA by the Kleene-star operator, whereas the encoding as a QBF will most probably be trickier.

A second perspective is to focus on embeddings of other existing operations. We did not succeed yet in embedding other approaches to merging such as [START_REF] Konieczny | On the difference between merging knowledge bases and combining them[END_REF] and syntaxbased operations such as MCS of [START_REF] Baral | Combining knowledge bases consisting of first-order theories[END_REF]. Note that in principle this might however be feasible: while the Hamming distance is a semantical notion, the function P ϕ is syntactic.

There exist also tentatives to define merging operations in first order logic [START_REF] Gorogiannis | Merging first-order knowledge using dilation operators[END_REF]. In long run, we may plan to extend DL-PA with first order constructions in order to capture those merging operations.

2 .

 2 The function || • || is the interpretation we are currently defining by induction over the formulas of L . The integer d H (v, E) is the sum of the elements of the vector d H (v, E). For example, || Σ ⊤ (p∧q, ¬p∧¬q)|| = ||⊤|| = 2 P .

Theorem 2 .

 2 Let ϕ be an L formula. Then ||ϕ|| = ||tr(ϕ)|| DL-PA .

Table 1 .

 1 Interpretation of the DL-PA connectives

  Two formulas ϕ 1 and ϕ 2 are formula equivalent if ||ϕ 1 || = ||ϕ 2 ||. Two programs π 1 and π 2 are program equivalent if ||π 1 || = ||π 2 ||. In that case we write π 1 ≡ π 2 . For example, the program equivalence π; skip ≡ π holds. A formula ϕ is DL-PA valid if it is formula equivalent to ⊤, i.e., if ||ϕ|| = 2 P . It is DL-PA satisfiable if it is not formula equivalent to ⊥, i.e., if ||ϕ|| ∅. For example, the formulas p←⊤ ⊤ and p←⊤ ϕ ↔ ¬ p←⊤ ¬ϕ are DL-PA valid. Other examples of DL-PA validities are p←⊤ p and p←⊥ ¬p.

Table 2 .

 2 Some useful DL-PA expressions, for P = {p 1 , . . , p n }, where m ≤ n in flip m (P) and flip ≤m (P), and where d ≤ card(P ϕ ) in H(ϕ, d)

  d≤max k≤n (card(P ϕ k )) i≤n

	flip ≤d (P ϕ i ) tr(ϕ i ) ∧
	¬ vary(P E ) tr(ψ) ∧

i≤n flip ≤d-1 (P ϕ i ) tr(ϕ i ) .

Table 3 .

 3 Example: translation of the Gmax merging of the profile p, p, ¬p under the integrity constraint ⊤

	tr( Gmax ⊤	(p, p, ¬p))

  and there is no otherψ-valuation v ′ such that d H (v ′ , E) < d H (v, E).The latter is the case iff v ∈ ||ψ|| and there are d 1 , . . . , d n such that 1. d H (v, ϕ i ) = d i for every i, and 2. there is no ψ-valuation v ′ and vector d ′ 1 , • • • , d ′ n such that d H (v ′ , ϕ i ) = d ′ i for every i and d i < d ′ i . By induction hypothesis, v ∈ ||ψ|| iff v ∈ ||tr(ψ)|| DL-PA and v ∈ ||ϕ i || iff v ∈ ||tr(ϕ i DL-PA . Therefore H(ϕ i , d i ) equals H(tr(ϕ i ), d i ). We note that by Lemma 1 it is in order to only consider the d i such that d i ≤ card(P ϕ i ). By Lemma 2, Item 1 means that v ∈ ||H(tr(ϕ i ), d i )|| DL-PA for every i.

While the term 'merging operator' is customary in the literature, our terminology is in line with that of abstract algebra.

More precisely, we do not have a single operator but a family of operators σ,n (.) that is parametrized by the length n of the profile vector. We abstract away from this here.

An expression is a formula or a program. When we say that two expressions are equivalent we mean program equivalence if we are talking about programs, and formula equivalence otherwise.

Acknowledgements. We wish to thank the three FOIKS reviewers for their critical comments and pointers to relevant work that we had not considered at the time of the submission.


FRENCH MUSICAL BROADCASTING BETWEEN 1925 AND 1939: A DOMINATION OF CLASSICAL MUSIC

In the early 1980's, historian René Duval released a publication which became a reference on the topic of French Radio. He especially focused on pre-war stations and cleared a vast uninvestigated ground. Throughout a chronological survey, where he describes every situation that contributes to bringing about some thirty broadcasting stations on the French territory, Duval emphasized similarities that occurred in the Thirties between the programs of public and private stations' 1 . He particularly showed that music was the basic broadcasting material of the very first French stations. Whatever the network or the power of diffusion, broadcasted concerts, in which musical art dominates, were at that time the "trading business" of broadcasting stations whose major listeners were members of the local bourgeois middle class 2 . Sketching a first picture of the links and political, socioeconomic and artistic factors, this researcher paved the way for new historical and musicological prospects.

TWO STUDIES ON PRE-WAR MUSICAL BROADCASTING ART MUSIC ON PARISIAN STATIONS AROUND 1925

Backing on first university research carried out on Radio History, Sylvie Garrec proposes an original musicological study dealing with the first-hour's medium 3 . Focusing on the musical programs or concerts that they offer, she looks into the musical contents of the four stations then existing in Paris one by one and compares them 4 . She also draws a very precise list of the composers who were mentioned between March 1924 and March 1925. This inventory highlights the primacy, on Parisian wires, of French 20 th century music. On the top board are in fact some particularly recurrent musicians: Gabriel Fauré, Reynaldo Hahn, Paul Vidal, Gabriel Pierné, followed by Cécile Chaminade, Maurice Ravel, Georges Hüe, Henri Busser and Florent Schmitt 5 . Beside her quantifications, Garrec submits the following hypothesis: "the main problem of broadcasters was to enhance modern music, to broadcast it without scaring away (and then losing) the majority of their audiences"6 . If she especially concentrates on "serious music" ("musique sérieuse"), meaning classical music as it was then called, she also examines the composers of minority genres, like jazz or military music, about whom she indicates: "It was actually impossible to find out any biography reference for some of the composers who are completely unknown nowadays. This fact reinforces the feeling of amateurism that the study of broadcasts from 1924 to 1925 suggests: a system of personal relationship may have played a role in the broadcasting of these musicians.7 " Besides, Syvie Garrec explains that classifying the composers broadcasted poses musicological problems such as matching yesterday's sections with current segments and definitions. The undertaking, she goes on, is to "formulate an aesthetic judgment apart from its context". Inaugurating new methodological and investigation processes, she especially highlights the age-old influence of those at the receiving end over those broadcasting as far as radio musical broadcasting is concerned.

A PROGRESSIVE DROP OF CLASSICAL MUSIC DURING THE THIRTIES

Devoting a thesis to French Radio in the Thirties, Cécile Méadel places some of the activities of the major stations in perspective with the socioeconomic and political context of the growing up of the medium8 . The complex muddle of factors which weigh on this evolution has inevitable impacts on the broadcasts, which the historian segmented into themes, so as to outline its features. In the chapter dedicated to music, she indicates that, apart from mutations that occurred in the mid-Thirties, music invariably accounts for 60% of the programs and budgets of the stations9 .

In order to support her analysis of broadcasted music, she uses the same method as Sylvie Garrec, examining, on the one hand, the types of programs (under the titles provided by specialized magazines) and, on the other hand, the statistics of the composers mentioned.

As far as the first are concerned, "due to hazy groups ("musique légère", symphonic concert, mood music, lyrical program, records or more simply concert)", samplings only enabled her to make out a "musical orientation" of the stations 10 . Her analysis of Radio-Paris' musical styles, for instance, shows the discontinuity of its musical broadcasting across the years 11 . At the most, she explains, it can be noted that "compared to other stations, this one rather substantially broadcasts classical music 12 ".

In order to assess the evolution of broadcasting through the angle of composers, Cécile Méadal carried out a sampling of the programs of two stations that were comparable in 1932 (Radio-Paris and Le Poste Parisien). She then compared these samplings to other ones from 1937 13 . The results she obtained show a noticeable evolution of the groups of composers which she classified chronologically, "respecting the criteria used by stations to qualify classical composers as such" (from the 18 th century to the 20 th ) :

« Mood music or pop music (apparently difficult to dissociate) head the most played genres in 1937 on both stations, whereas five years before, this commercial music was overstepped by 19 th century music. […] The 19 th century is a golden mine for station broadcasting, mainly in 1932. Some forty composers altogether were shared by the two stations. Between 1932 and 1937, however, their appearances are going down in absolute value. This fact is more particularly true for Le Poste Parisie : while they used to account for almost one half of the programs in 1932, they hardly represent one seventh five years later. On Radio-Paris, the figure is shrinking from 22% to 12% of the composers mentioned . 20 th century music faces a similar evolution. 14 " These two comparative studies screening the appearances of both programs and composers broadcasted lead Cécile Méadel to consider the "Musical Babel" as one of the characteristic features of the music of the Thirties 15 . But her findings mainly tend to unveil the invention of its proper stylistic patterns, delimiting an "entertainment" genre and a "highbrow" register, which could be found in no other musical area. Without attempting to explain how the blend of song, opera and symphonic music can constitute a coherent mixture, Méadel comes to the conclusion that the very notion of music itself acquires a uniformity which it hadn't got before: "With Radio, the mere genre of music becomes a unity 16 ".

A MORE ACCURATE VISION OF MUSICAL BROADCASTING IN FRANCE IN THE THIRTIES

A more recent university research highlights some of the zones that the pioneer work of Cécile Méadel left in the shadow. The thesis which the author of this article defended a few years ago confirms the hegemony of classical music on the wires, while revealing the 11 Contrary to Sylvie Garrec's study which proposed a picture of musical broadcasting within a whole season, Cécile Méadel attempted to monitor an evolution of the dispatching of musical genres throughout the time. Her samplings of Radio-Paris (a week of programs) concerned several years : 1930, 1932, 1934, 1935, 1936, 1937, 1939. 12 MÉADEL, Cécile,op. cit.,p. 316. 13 Jotting down the names of the composers played for one week of 1937 and two of 1932 (when the information released was too short to provide relevant data), she found a result of 349 musicians representing a total of 465 pieces performed. 14 MÉADEL, Cécile,op. cit., La radio des années trente [thesis], p. 703. 16 Ibid., chapter « De la musique avant toute chose », p. 329. circumstances of its "cohabitation" with emerging softer, more entertaining and more popular aesthetics, 17 .

In order to understand the musical features that emerged on the Radio of the Thirties, multiple angles of monitoring were used that highlighted both the mechanisms of musical production and the latter's own features. In the purpose of recounting actual facts in their dynamics and immediate reality, we decided to make samplings throughout the whole decade.

TWO MODELS OF STATIONS FOR THE DECADE

Two of the some thirty stations existing in the Thirties perfectly represent the evolution: Radio-Paris / Poste national and Radio-LL which is to become, under the name of Radio-Cité, one of the most popular private stations of the pre-war period. These two models of stations are as representative of the beginning of the decade (when there was a split between big and handmade local stations) as of the pre-war period (when the cleavage was between government-owned public stations post controlled by the "PTT" administration of and powerful commercial stations).

Due to the inequality of programs depending on the seasons, a picture taken every year at the same time was preferred to random measurements. The month of June was chosen as a standard of the decade because it happened to follow a kind of average pattern between the "full" season and the summer period, usually emptier in the matter of programs.

A typology of radio broadcasts, quantified by genre, by the number of sets and by duration was built to facilitate the understanding of this corpus of 10 months of broadcasting 18 .

CONFRONTING CONTENTS AND ARGUMENTS

Studying the occurrences of composers was as interesting as monitoring musical performers, who were also ever-present in the printed programs. Gathering respectively 2 185 composers and 2 012 performers, the stocklists built from the rewriting of the programs show a qualitative and quantitative picture of the musical broadcasting of the Thirties. In fact, bringing to light the categories and stylistic subdivisions in which these musicians evolved, these indexes precisely show their recurrence, for both the composers and the noticed performers are listed with an indication of the number of their references (meaning their cited works) and the years when they appeared 19 .

Two complementary purposes motivated the building of another corpus gathering the arguments (in both meanings of the term !) of the actors of French musical broadcasting in the 18 These 5 360 programs, corresponding to more than 3 350 broadcasting hours provide a wide database that can be exploited either in a progressive perspective or in a comparative or global view. 19 Composers and performers listed in these both indexes generate 15 874 references that had to be classified in order to bring any sense. This database is currently being posted on line at: http://www.plm.parissorbonne.fr/spip.php?rubrique6 .

Thirties, firstly explaining some aspects of acting which the indexes left unlighted and enhancing the conditions of broadcasting and receiving. On the other hand, the purpose was to verify the consistency between the two models of stations and other stations of the French network. This corpus of database was built from a scrupulous monitoring of broadcasting press organs readable either at Radio France (department of the written archives) or National Library Francois-Mitterrand (audiovisual department) and Inathèque de France (same site). Including some 900 press articles, this database appears to be relevant since it gathers diverse columnists' orientations.

1930-1935: BETWEEN THE TRADITIONNAL CONCERT PATTERN AND AN EMERGING BROADCASTING GENRE

Building corpuses from multiple sources led to a necessary temporal separation in the chronological study of musical broadcasting. Historian Christian Brochand had suggested periodical frames that perfectly apply to our topic. Considering the process of professionalization of broadcasting programs, he defined 1935 as a "go-between year" between a "transitional Radio (1929-1935)" and a "modern Radio (1935-1040)" 20 .

ECLECTIC PROGRAMS AND MYRIADS OF COMPOSERS

The strong diversity shown by the typology of programs (29 categories 21 ) reveals that the broadcasting managers intend to satisfy a broad panorama of listeners. Despite the economic contingencies that the station faces, they try to provide coherent broadcasting, instituting listening habits which give them their tempo: at noon, in the evening, on Sundays. For either nationwide or self-made local stations, the apparent confusion of programs should mainly be seen as a melting-pot of genres that would be considered today as an aberration. Apart from classical concerts, they often produce successions of entertaining commercial dance music which they borrow respectively from café-concerts or music-and dance-halls, thus progressively building a principle of entertaining music. We can see that from its very beginning Le Poste national (the other name of Radio-Paris at the time when the French Government bought it back in 1933) imitates and leads this musical innovation further. The apparition of numerous little orchestral groups is indeed significant: their adaptability enables them to perform either a repertory from the Romantic period (a recurrent style) or a vocal program with songs and pieces of dancing music. Copying, on the one hand, existing schemes of aesthetically consistent shows, and inventing, on the other hand, heterogeneous sequences of playing records, sometimes "humanized" by small station-orchestras, The radio of the first 20 BROCHAND, Christian, Histoire générale de la radio et de la télévision, t. I : 1921-1944, p. 390 et 406. 21 These typologies of programs, composers and performers are shown in detail in a previous article: BENNET, Christophe, « La programmation musicale en 1936 », in Cahiers d'histoire de la radiodiffusion n°88 April-June 2006: http://web.chr2009.free.fr/?p=667 .

half of the Thirties has already found its proper style. The mixture of improvisation and reproduction contributes to the emergence of typically "radiophonic" musical programs22 .

The association of programs' and composers' typologies enhances an interesting fact: the celebrity of musicians appears in their capability of belonging to any program declined, from a classical concert to the musical "middle-of-the-road" series ("light and mixed music" or "musique légère et variée"). Protagonists of a "middle genre", like those of "light music" or operetta, drift as easily into classical music programs as in entertaining series. Viennese composer Franz Lehar perfectly embodies this versatility since he can be found either in symphonic or lyrical concerts or in music-hall and movies' music programs. The large range of musical writing, in which "operatic" occupies a golden place, is indisputably one of the vectors of the frequent appearances of several composers. Those who could be qualified as "unspecialized or universal musicians", in opposition to their counterparts focusing on a precise genre, are easily inserted, thanks to carefully chosen titles, in the multiple thematic series whose unity was only due to their ambiance. Innumerable "little masterpieces" utilized by the broadcasters of the Thirties both enable them to feed these multicolored programs and to introduce indisputable values in the matter of cultural legitimacy. However, stations would probably not broadcast such "tonal" pieces more meeting an intellectual demand than for their inexhaustible musical variety. Besides, in the first half of the decade, a relative relationship could be underlined between the programs of a big national station and those of a modest local station. Yet, considering both Radio-LL's programs and composer lists, a slight decrease of classical programs can be observed 23 By associating the databases of programs, composers and performers of both stations, two opposite tendencies appear. On Radio-Paris, Classical music dominates24 . Whereas these programs are mainly produced "live" from the studios of the station, the category of Classical music largely oversteps the categories of "entertaining music" (mostly recorded), and "middle music". In such little studios thin orchestras of a dozen musicians are used to mixing symphonic works with commercial songs and dances, as if they tried to imitate traditional programs of record combinations.

Lacking such a median tool, Radio-LL's programs are more thematically consistent and segmented. The microphone is the main vector of entertaining music. At the end of this six-year period, this model of program insensitively oversteps classical music, mostly broadcasted, through records playing 25

DIVERGENCES OF IDEAS AND INTERESTS

Globalizing the arguments of the actors of the decade's broadcasting, we can underline the action of a managing minority, intellectually demanding, open to classical music, to the art of broadcasting and apparently motioned by a project of masses acculturation in the field of music. Those who can be qualified as an elite are opposing a majority of listeners who are, if not growing, at least composed of sharply critical customers who steadily express their aspirations and dislikes more openly. Although they acknowledge the legitimacy of the use of the medium for pedagogical purposes, they however reject this principle the moment they are listening! Year after year, evidences and statements add up to denounce a saturation of "highbrow music" (informally called "Grande musique" by French people).

What however happens is that programs-makers, cautiously progressing against winds and tides, are not so awkward, given their modest resources. At a time when the economic background is unfavorable, Radio managers attempt to spare their audiences, without any help (a euphemism!) from their potential allies: record-making industries, the national lyrical theatres, and musical performers 26 . What's more, it is hardly likely that the huge broadcasting of classical music was meant only with the purpose of mass acculturation. The broadcasting of a symphony by Beethoven, which might be perceived by some listeners as a boring music lesson, would nonetheless be felt as actual entertainment by others. Without any genuine "bill of specifications", the radio steadily grows up on the basis of its prime. It becomes progressively free from the recitals of chamber music, from the "t1926-type" radio-concerts as a disgruntled listener qualified them in La Parole libre TSF 27 . In the very first hours of broadcasting, this profusion of traditional broadcasts was hardly astonishing, since what we could call an "average audience" came from the bourgeoisie, acclimated to the values of 25 Cf. the graph « évolution de la musique de divertissement sur Radio-LL de 1930 à 1935 » and read the chapter concerning performers scheduled at this period: « la forte valeur identitaire des musiciens de stations ». 26 At the beginning of the decade, all this actors keep striking radio, considering it more as a potential rival than as a possible partner. 27 La Parole libre TSF n°115 of July 13 th , 1930, p. 2: « La composition des programmes ». The listener denounces « the alternation of singing, piano solo, adagio for cello and sonata for violin ».

music as an art. The more we progress in the decade, the less this is true. As far as the public / private cleavage is concerned, the monitoring of the different arguments through the broadcasting press confirms what quantitative tools had suggested. Whatever the political orientation of the magazine, the actors before 1935 are therefore more willing to express themselves about the radio in a broad sense than on the difference between two distinct models of broadcasting.

1936-1939: SIMILARITIES ON THE GROUND AND DIFFERENCES ON THE FORM

Throughout the second half of the decade, the interference of several evolution factors is shaking up the programs of French radio. Successive governments are perfectly aware of the decrease of the audience that the national network faces. In spite of an insidious reinforcement and its involvement in program organization, and despite the enhancement of its artistic supply (due to the complementarity of territorial resources), the public sector struggles to prevent the fleeing of audience toward commercial stations. Responding to their aspirations, private stations imagine new ways of conceiving programs and making Radio. Often composed in relation with publicity specialists and corresponding to the wishes of a growing multitude, their programs match their likely tastes. Faced with a sophisticated way of speaking, an administrative routine, the endless pressure of public policies, private stations play on the ground of distraction, fantasy and imagination. Every year more numerous, listeners prefer them to Government's stations, because they're more interesting, younger, more active and happier.

AN AUDIENCE IS TO ACCULTURATE

Examining some of the statements of managers is particularly meaningful: either acting in favor of the public network or for a big private station, the personalities heading musical programs express conceptions that are eventually convergent. Faced with the listener's boredom inspired by unknown aesthetical expressions which they appeared to be fed up with, the only solution is to conceal their purpose of acculturation. The project eventually consists in cautiously infiltrating the listeners' culture (or non-culture?), in situations that they don't consider as educative (operettas, well-known masterpieces, short sequences). These managers commonly estimate they would help their listeners to assimilate music which doesn't belong to their culture through the progressive capitalization of a minimum of "middle-of-the-road values". On the side of the public network, Désiré-Émile Inghelbrecht, who is responsible for "high surveillance of Paris-PTT's programs" and is in charge of the artistic management of federal programs, explains that "we should not be upset by a too beautiful music, but abandon summits to alpinists and just bring the masses to mid-slope.28 ". On the private side, Jean-Guignebert, editor-in-chief of "La Voix de Paris" on Radio-Cité, suggests impregnating their intelligence without their knowledge:

« Of course the hearing of light music won't bring a considerable enrichment to the brain but it will extend knowledge, will polish the slightest bit of sensitivity and will pave the way for the listening of deeper music.29 » Believing either of them, the listeners make an obstruction to any "attempt" at acculturation. And this is mainly due to their incapacity to decode these sophisticated musical expressions. These managers' records and stances are rather similar. However, their implementations and the results of their respective policies (at least in terms of public opinion) are different.

RADIO-PARIS: ACCULTURATION THROUGH THE MUSICAL DIVERSITY OF THE CONCERTS

From the very first years of the decade, Radio-Paris, without being an exception, took to flooding its listeners with heterogeneous musical programs. The purpose consisted in interfering in the listeners' auditive habits. In an article titled "For a musical education of masses", columnist Paul Dermée had interpreted this choice of the broadcasters as a will of not being too didactic or too austere. Thus, diversity, a variety of music, appears to be felt by the actors of broadcasting as synonymous with entertainment. According to this observer, dreadful mixtures resulting from this conception reduce the pedagogic impact of the medium. Yet he admits that eventually these colorful broadcasts indeed enabled many consumers to accustom themselves to some of the greatest composers and to their works 30 . In June 1939, on Radio-Paris (which had then become 'Le Poste National') there is still a plethora of "concert variés" (mixed programs), "light music" ("musique légère"), and series of record-playing entitled "light music concerts". Conducted by François Gras, the concert broadcasted on Sunday, June 4 th , 1939 illustrates both the partial legitimacy of such mixtures and the contests they inspire. For the beginning of this Sunday afternoon, here is what Le Petit Radio announced:

« Concert, direction Fr. Gras : Old Nick (Tzipine) ; La pie voleuse, ouverture (Rossini) ; La Housarde (Ganne) ; Blanche Neige et les sept nains, sélection (Churchill) ; Yvonette (Jeanjean) ; En relisant vos lettres (Masson-Kick) ; Saltarelle (Gounod) ; The Donkey Serenade (Friml) ; Boublichka (Némo et Mills) ; Jubilee Stomp (Ellington) ».

It clearly appears that the program of the concert is mainly oriented in a "light music" spirit. Through a kind of aesthetical neighborhood all this tunes that are not properly speaking from the symphonic field may be related to a formal, rather accessible, musical classification, a "middle style" music that could be linked to the "mid-slope" which Inghelgrecht was talking about. Considered separately on basic criteria of writing, however, some of these works are very distant. Nowadays it would be difficult to match Ellington's swing with Exquisite Romances by Gounod or the flowing themes from The Thieving Magpie by Rossini with the simple melodies of Snow White and the Seven Dwarfs, conceived to be easily memorized and hummed. Yet the Radio-Paris program makers precisely dare such mixture, thanks to the arrays of entertainment and symphonic pieces ("musique légère et variée"). The concept of "rather classical but accessible aesthetics" is a principle that favors sliding from one style to another.

On Radio-Cité, classical music is far from being neglected, as the high proportion of composers of this category witnesses. But the recipe is utterly different.

HETEROGENEOUS AND APPEALING MUSICAL CAPSULES ON RADIO-CITÉ

Radio-Cité addresses a probably more popular public than Radio-Paris'. Without making any pejorative distinction, without positioning any genre above another, the station wishes to broadcast the best pieces of every genre. Beside celebrities of dancing, commercial songs and music-hall shows, broadcasters regularly program performers whose aesthetic is more classical, such as organist Charles Tournemire, operatic singer Lucienne Astruc and pianist Walter Joseph. These last two are used to regularly performing through recitals of sonatas in a program called "Vendredis musicaux de Radio-Cité" ("Musical Fridays on Radio-Cité"), at 3.30 p.m. Either giving a sweet lesson of some musical abstracts or stepping in as performers, these characters, who represent multiple genres, never stay in front of the microphone for long, but frequently come back to it. These short musical series seem to be all the less repetitive as they appear in program schedules that are always being reshaped.

From 1938 on, a daily program aims to honor great musical art through the recordings of masters. For about twenty minutes, this music lovers' rendezvous marks the beginning of the evening programs, at 6.30 p.m,. As an example, we could show the program of the week of June 4 th , 1939, published in the station's magazine in a box entitled "Radio-Cité's 'musical moment': By 1939, the very young Paris Philharmonic Orchestra becomes a regular guest of the studio located, in "la rue de Washington". This orchestra provides, in exclusivity for Radio-Cité, prestigious concerts, such as the "8 th gala by the Paris Philharmonic Orchestra [performed on June 4 t ] under the baton of soloist Jacques Thibaud. 32 " Showing French musical broadcasting in the Thirties through two models of stations confirms the hypotheses founded upon some of the pioneer works : highly listened private stations were wishing to satisfy a demand of musical entertainment contrary to a stubbornly cultural supply, embodied by a public network desperately seeking audiences. However, if one examines the most characteristic aspects of each of the two conceptions of the medium, such as the narrow links between music and advertisement 33 , the handling of the microphone by listeners or the emergence of didactic programs, we on the contrary perceive connections that were unsuspected so far. These similarities, a kind of look-alike, constitute the only substance of musical broadcasting of the decade. Split between their convictions and the maintaining of an audience, broadcasting stations hesitate, seek, find, invent and copy each other. Generalist as a fact, they are confronted with antagonistic audiences, the invisible mass thought to be "noisy" and demanding. Henceforth, we can authenticate the specificity of musical broadcasting in the Thirties by this weird dichotomy: the omnipresence of lighthearted song and the pregnancy of Classical music. But, characteristic it is, this Radio sets up the integrality of modern radio paradigms. Bt reconciling the general interest with particular stakes, "highbrow" and popular expressions, entertainment and education, program-makers inaugurated and implemented all the patterns of our current audiovisual media.

Many thanks to Mr. Gérard Hocmard for his help regarding the language issues.

  17 BENNET, Christophe, Musique et Radio dans la France des années trente : la création d'un genre radiophonique, thesis of doctorate in History of Music and Musicology of University of Paris-Sorbonne, held in june 2007 under the direction of en Michèle Alten. This thesis was published under the following title: La Musique à la Radio dans les années Trente, Paris, L'Harmattan, 2010: http://www.editionsharmattan.fr/index.asp?navig=catalogue&obj=livre&no=31655 .

«

  Dimanche à 18h17 -Debussy : Sonate pour flûte, alto et harpe. Lundi à 18h25 -J.-S. Bach : Cantate, par les choeurs et orchestre de la Société Bach. Mardi à 18h25 -Vaughan Williams : Sérénade à la Musique, solistes et orchestre sous la direction de Sir Henry Wood. Mercredi à 18h45 -Liszt : Légende de Saint François de Paule marchant sur les flots , Valse oubliée, La Campanella. Jeudi à 18h22 -Berlioz : La Damnation de Faust (extraits) avec Charles Panzéra , José de Trévi et M. Berthon. Vendredi à 18h23 -Chausson : Le Roi Artus, avec Endrèze et Poème pour violon et Yehudi Menuhin. Samedi à 18h17 -Florent Schmitt : Suite en Rocaille, par le Quintette Instrumental de Paris. 31 »

31

  Ici…Radio-Cité n°74 du 2 juin 1939, p. 2. 32 This renowned artist attended a few times before the inauguration of the new studio [Ici…Radio-Cité n°69 May, 5 th 1939, p. 6 : « La brillante inauguration du studio Washington »]. 33 An article on this topic is called: Radio Advertising in the Music Broadcasting in France in the Thirties. It can be found on the site of PLM: http://www.plm.paris-sorbonne.fr/spip.php?article616

  .

		Evolution de la musique savante sur Radio-Paris
				de 1930 à 1935
	80%
	70%
	10% 60% 50% 40% 30% 20%					% des heures d'émissions % des références d'auteurs % des références d'interprètes
	0%
	juin	juin	juin	juin	juin	juin
	1930	1931	1932	1933	1934	1935

  .

	Evolution de la musique de divertissement sur Radio-LL
				de 1930 à 1935
	100%
	80%					% des heures
						d'émissions
	60%					% des références
	40%					d'auteurs
	20%					% des références d'interprètes
	0%
	juin	juin	juin	juin	juin	juin
	1930	1931	1932	1933	1934	1935

Ibid., p. 21.

Ibid., p. 41. Speaking about her attempts of identification of musicians, the auteur indicates (p. 4) that 3 letters addressed in this purpose to la Sacem (French Society dealing with musician play rights) remained unanswered.

MÉADEL, Cécile, Histoire de la radio des années trente, Phd in History under the direction of Jean-Noël Jeanneney, Institut d'Études Politiques de Paris, 1992. This thesis was published afterward under the title of : Histoire de la radio des années trente, Paris, Anthropos / INA, 1994.

MÉADEL, Cécile., op. cit., p. 323. Tiitled « De la musique avec toute chose », referring to Verlaine's quote and reemployed by Robert Jardillier in October of 1938, Chapter XIV can be found p 313-329.

Musique et Radio dans la France des années trente, op. cit. « Des programmes privilégiant l'éclectisme », p. 25-52.

Ibid., « Une myriade d'auteurs », p. 53-82.

Cf. the graph « évolution de la musique savante sur Radio-Paris de 1930 à 1935 ».

TSF Programmes n°202 July

th , 1934, p. 45 : « Quelques instants avec D.-E. Inghelbrecht », by Pierre Keszler.

Ici…Radio-Cité n°10 March 12 th , 1938, p. 6 : « La boîte aux lettres ».

La parole libre TSF n°181 du 18 octobre 1931, p. 3 : « Pour l'éducation musicale des masses » by Paul Dermée