Author: "Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME)" / Search Limiters: Available in Library Collection - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME)"' showing total 39 results

Start Over Author "Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME)" Search Limiters Available in Library Collection

39 results on '"Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME)"'

1. The IO and OI hierarchies revisited

Author: Sylvain Salvati, Gregory M. Kobele, Computation Institute [Chicago], University of Chicago, Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Models for a Structured Programming of Space and Time (PoSET), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), ANR-12-CORD-0004,Polymnie,Analyse et synthèse dans les grammaires catégorielles abstraites : du lexique au discours(2012), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: ACM: F.: Theory of Computation/F.3: LOGICS AND MEANINGS OF PROGRAMS/F.3.3: Studies of Program Constructs/F.3.3.3: Program and recursion schemes, Formal semantics (linguistics), ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.3: Formal Languages/F.4.3.3: Decision problems, Montague semantics, 0102 computer and information sciences, 01 natural sciences, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], Theoretical Computer Science, Denotational semantics, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Rule-based machine translation, Computer Science::Logic in Computer Science, Higher-order grammars, ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.2: Grammars and Other Rewriting Systems, ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.2: Grammars and Other Rewriting Systems/F.4.2.3: Parsing, Gödel's completeness theorem, Formal language theory, 0101 mathematics, ACM: F.: Theory of Computation/F.3: LOGICS AND MEANINGS OF PROGRAMS/F.3.2: Semantics of Programming Languages/F.3.2.1: Denotational semantics, Mathematics, Discrete mathematics, Simply typed lambda-calculus, Simply typed lambda calculus, OI, ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.3: Formal Languages, 010102 general mathematics, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing), IO, Montague grammar, ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.2: Grammars and Other Rewriting Systems/F.4.2.0: Decision problems, 16. Peace & justice, Computer Science Applications, Decidability, ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.1: Mathematical Logic/F.4.1.2: Lambda calculus and related systems, Algebra, Membership problem, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, Computational Theory and Mathematics, 010201 computation theory & mathematics, TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, Emptiness, Computer Science::Formal Languages and Automata Theory, Natural language, Information Systems
Abstract: International audience; We study languages of lambda-terms generated by IO and OI unsafe grammars. These languages can be used to model meaning representations in the formal semantics of natural languages following the tradition of Montague. Using techniques pertaining to the denotational semantics of the simply typed lambda-calculus, we show that the emptiness and membership problems for both types of grammars are decidable. In the course of the proof of the decidability results for OI, we identify a decidable variant of the lambda-definability problem, and prove a stronger form of Statman's finite completeness Theorem.
Published: 2015
Full Text: View/download PDF

2. Causalité dans les calculs d'événements

Author: Serpette, Bernard, Janin, David, Secure Diffuse Programming (INDES), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Models for a Structured Programming of Space and Time (PoSET), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Serpette, Bernard, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), and Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest
Subjects: [INFO.INFO-CL] Computer Science [cs]/Computation and Language [cs.CL], [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL]
Abstract: National audience; Si l'on considère un événement comme une valeur quelconque associée à une date de réception, un calcul d'événements est une fonction produisant un ensemble d'événements à partir d'un ensemble d'événements reçus. Un sous-ensemble particulièrement intéressant de ces fonctions correspond aux fonctions causales dont les événements produits avant une date donnée ne dépendent que des événements reçus avant cette même date. Dans cet article, nous proposons une définition très simple permettant de caractériser ces fonctions causales.
Published: 2017

3. Authoring and automatic verification of interactive multimedia scores

Author: Jaime Arias, Myriam Desainte-Catherine, Jean-Michaël Celerier, Models for a Structured Programming of Space and Time (PoSET), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université de Bordeaux (UB), Blue Yeti [St Georges de Didonne], ANR-12-CORD-0024,OSSIA,Open Scenario System for Interactive Application(2012), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Model checking, Correctness, Visual Arts and Performing Arts, Computer science, Process (engineering), 0102 computer and information sciences, 02 engineering and technology, computer.software_genre, 01 natural sciences, Software, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Encoding (memory), interactive multimedia scenarios, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC], Timed automata, business.industry, Programming language, [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM], 020207 software engineering, Interactive scores, Automaton, UPPAAL Model Checker, 010201 computation theory & mathematics, business, computer, Music, Interactive media
Abstract: International audience; The advances in authoring of interactive scores call for a thorough analysis of the written scores. A possible way to ensure correctness of an interactive score is through the use of formal techniques such as model checking. In this work, we present a visual model of the inter-media sequencer i-score and we propose a Timed Automata encoding to reason about the interactive scores written in this software. The verification of some properties of interactive scores is presented, along an evaluation of the performance of the model-checking process with uppaal.
Published: 2016
Full Text: View/download PDF

4. Graphical Temporal Structured Programming for Interactive Music

Author: Celerier, Jean-Michaël, Desainte-Catherine, Myriam, Couturier, Jean-Michel, Blue Yeti [St Georges de Didonne], Models for a Structured Programming of Space and Time (PoSET), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Convention CIFRE 1181-2014., Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Celerier, Jean-Michaël
Subjects: [INFO.INFO-MM] Computer Science [cs]/Multimedia [cs.MM], [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], interactive music, [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM], i-score, music computing, [INFO.INFO-PL] Computer Science [cs]/Programming Languages [cs.PL]
Abstract: International audience; The development and authoring of interactive music or applications , such as user interfaces for arts & exhibitions has traditionally been done with tools that pertain to two broad metaphors. Cue-based environments work by making groups of parameters and sending them to remote devices , while more interactive applications are generally written in generic art-oriented programming environments, such as Max/MSP, Processing or openFrameworks. In this paper, we present the current version of the i-score se-quencer. It is an extensive graphical software that bridges the gap between time-based, logic-based and flow-based interactive application authoring tools. Built upon a few simple and novel primitives that give to the composer the expressive power of structured programming, i-score provides a time line adapted to the notation of parameter-oriented interactive music, and allows temporal scripting using JavaScript. We present the usage of these primitives, as well as an i-score example of work inspired from music based on polyvalent structure.
Published: 2016

5. Rethinking The Audio Workstation : Tree-Based Sequencing With I-Score And The Libaudiostream

Author: Celerier, Jean-Michaël, Desainte-Catherine, Myriam, Couturier, Jean-Michel, Celerier, Jean-Michaël, Models for a Structured Programming of Space and Time (PoSET), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Blue Yeti [St Georges de Didonne], Financement CIFRE 1181-2014, PoSET, Rolf Großmann, Georg Hajdu, Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
Subjects: [INFO.INFO-MM] Computer Science [cs]/Multimedia [cs.MM], [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, [INFO.INFO-TS] Computer Science [cs]/Signal and Image Processing, [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM]
Abstract: International audience; The field of digital music authoring provides a wealth of creative environments in which music can be created and authored: patchers, programming languages, and multi-track sequencers. By combining the i-score interactive sequencer to the LibAudioStream audio engine, a new music software able to represent and play rich interactive audio sequences is introduced. We present new stream expressions compatible with the LibAudioStream, and use them to create an interactive audio graph: hierarchical stream and send-return streams. This allows to create branching and arbitrarily nested musical scores, in an OSC-centric environment. Three examples of interactive musical scores are presented: the recreation of a traditional multi-track sequencer, an interactive musical score, and a temporal effect graph.
Published: 2016
Full Text: View/download PDF

6. Automatic Construction of Interactive Machine Improvisation Scenarios from Audio Recordings

Author: Jaime Arias, Myriam Desainte-Catherine, Shlomo Dubnov, Models for a Structured Programming of Space and Time (PoSET), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université de Bordeaux (UB), University of California [San Diego] (UC San Diego), University of California, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and University of California (UC)
Subjects: Factor Oracle, Interactive Scores, InformationSystems_INFORMATIONINTERFACESANDPRESENTATION(e.g.,HCI), Improvisation machine, Petri Net, [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM], i-score, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract: International audience; We describe a system that allows improvisers and composers to construct an interactive musical environment directly from a musical recording. Currently, interactive music pieces require separate phases of constructing generative models and structuring them into a larger compositional plan. In the proposed system we combine machine improvisation tools based on Variable Markov Oracle (VMO) with an interactive score (i-score) to control the improvisation according to larger structures found in that recording. This allows construction of improvisation scenarios in ways that are organic with the musical materials used for generating the music. The method uses new results of audio segmentation based on VMO and translates it into a Petri Net (PN) model with transition rules left open to be defined by a musician. The PN structure is finally translated into a timed representation for a live i-score control.
Published: 2016
Full Text: View/download PDF

7. Techniques vidéo-ludiques pour logiciel auteur multimédia

Author: Celerier, Jean-Michaël, Models for a Structured Programming of Space and Time (PoSET), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Blue Yeti [St Georges de Didonne], Thèse CIFRE N° 1181/2014, LaBRI, Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Celerier, Jean-Michaël
Subjects: [INFO.INFO-MM] Computer Science [cs]/Multimedia [cs.MM], [INFO.INFO-SE] Computer Science [cs]/Software Engineering [cs.SE], [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM], [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE]
Abstract: Problématique : Conception d'un logiciel d'écriture temporelle amené à être utilisé en production par des artistes tout en servant de plateforme de recherche extensible pour des technologies multimédia. Méthode : Conception en entité-composant-système avec hiérarchies symétriques d'entités et de composants. Plusieurs moteurs opèrent en parallèle, avec une conception modulaire pour étendre le modèle. Création d'entités sémantiques fortes par héritage, puis d'extensions faibles par composition. Hiérarchie : création automatique de composants enfants à la création de nouvelles entités. Résultats : Plusieurs moteurs sont implémentés de cette manière : il est en pratique souvent nécessaire d'avoir des graphes miroirs du graphe principal avec des données supplémentaires.
Published: 2016

8. Pour un raffinement spatio-temporel tuilé

Author: Archipoff, Simon, Janin, David, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Models for a Structured Programming of Space and Time (PoSET), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Archipoff, Simon
Subjects: [INFO.INFO-MO] Computer Science [cs]/Modeling and Simulation, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation
Abstract: National audience; Dans le domaine de la construction et de la manipulation par programme de flux média temporisé, nous étudions la problématique du raffinement, c'est-à-dire le problème de la substitution de flux élémentaires par des flux plus complexes. Dans le cas de construction purement séquentielle, la notion de liste permet de faire cela sans difficulté. C'est du raffinement temporel. Le bind de la monade liste permet de réaliser ces substitutions. En présence de parallélisme, les choses sont plus complexes : aucune construction ne semble s'imposer a priori. Dans cet article, nous montrons comment la modélisation par tuilage, qui explicite dans sa syntaxe les points de synchronisation qui doivent être préservés lors d'un raffinement, permet de définir, sans ambiguïté et tout aussi simplement que dans le cas des listes, un raffinement spatio-temporel. Incidemment, cette approche rompt avec l'usage usuel des monades en programmation fonctionnelle qui permettent de représenter la séquentialité. Sur la monade des tuiles comme sur la monade des listes, le bind permet aussi de modéliser le raffinement.
Published: 2016

9. Walking automata in free inverse monoids

Author: David Janin, Models for a Structured Programming of Space and Time (PoSET), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), ANR-12-CORD-0009,INEDIT,INteractivité dans l'Ecriture De l'Interaction et du Temps(2012), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Janin, David, and Contenus et Interactions - INteractivité dans l'Ecriture De l'Interaction et du Temps - - INEDIT2012 - ANR-12-CORD-0009 - CONTINT - VALID
Subjects: regular expressions, TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, Semantics (computer science), 0102 computer and information sciences, F.1.1 Models of Computation, F.4.1 Mathematical Logic, F.4.3 Formal Languages, 01 natural sciences, Combinatorics, pebble automata, Regular language, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Quantum finite automata, 0601 history and archaeology, Regular expression, Algebraic number, [INFO.INFO-FL] Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Mathematics, Discrete mathematics, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], 060102 archaeology, walking automata, 06 humanities and the arts, [INFO.INFO-PL] Computer Science [cs]/Programming Languages [cs.PL], Automaton, Inverse semigroup, [MATH.MATH-LO]Mathematics [math]/Logic [math.LO], TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, 010201 computation theory & mathematics, [MATH.MATH-LO] Mathematics [math]/Logic [math.LO], Automata theory, inverse monoids, Computer Science::Formal Languages and Automata Theory, MathematicsofComputing_DISCRETEMATHEMATICS, birooted graphs
Abstract: International audience; Walking automata, be they running over words, trees or even graphs, possibly extended with pebbles that can be dropped and lifted on vertices, have long been defined and studied in Computer Science. However, questions concerning walking automata are surprisingly complex to solve. In this paper, we study a generic notion of walking automata over graphs whose semantics naturally lays within inverse semigroup theory. Then, from the simplest notion of walking automata on birooted trees, that is, elements of free inverse monoids, to the more general cases of walking automata on birooted finite subgraphs of Cayley's graphs of groups, that is, elements of free E-unitary inverse monoids, we provide a robust algebraic framework in which various classes of recognizable or regular languages of birooted graphs can uniformly be defined and related one with the other.
Published: 2016

10. Structured reactive programming with polymorphic temporal tiles

Author: Simon Archipoff, David Janin, Models for a Structured Programming of Space and Time (PoSET), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Sequence, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], Event (computing), Computer science, [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM], 020207 software engineering, 02 engineering and technology, Field (computer science), Domain (software engineering), [MATH.MATH-LO]Mathematics [math]/Logic [math.LO], System programming, Simple (abstract algebra), [INFO.INFO-SD]Computer Science [cs]/Sound [cs.SD], 0202 electrical engineering, electronic engineering, information engineering, Reactive programming, 020201 artificial intelligence & image processing, Algorithm, Functional reactive programming, [MATH.MATH-CT]Mathematics [math]/Category Theory [math.CT]
Abstract: International audience; In functional reactive programming (FRP), system inputs and outputs are generally modeled as functions over continuous time (behaviors) whose future values are governed by sudden changes (events). In this approach, discrete events are embedded into piece-wise continuous behaviors. In the field of reactive music system programming, we develop an orthogonal approach that seems to better fit our need. Much like piano keys can be played and combined both in sequence and in parallel, we model system inputs and outputs as spatio-temporal combinations of what we call temporal values: continuous functions over time whose domain lays between two events: a start and a stop event. Various high level data types and program constructs can then be derived from such a model. They are shown to satisfy robust algebraic and category theoretic properties. Altogether, this eventually provides a simple, robust and elegant programming front-end, temporal tile programming, for reading, memorizing, stretching, combining and transforming flows of inputs into flows of outputs. Although at its infancy, the resulting approach has been experimentally validated for reactive and real-time music system programming.
Published: 2016
Full Text: View/download PDF

11. Ordered Tree-Pushdown Systems

Author: Clemente, Lorenzo, Parys, Pawel, Salvati, Sylvain, Walukiewicz, Igor, Département d'Informatique [Bruxelles] (ULB), Faculté des Sciences [Bruxelles] (ULB), Université libre de Bruxelles (ULB)-Université libre de Bruxelles (ULB), Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), University of Warsaw (UW), Models for a Structured Programming of Space and Time (PoSET), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
Subjects: FOS: Computer and information sciences, 000 Computer science, knowledge, general works, TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, D.1.1, Formal Languages and Automata Theory (cs.FL), D.2.4, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Computer Science - Formal Languages and Automata Theory, 0102 computer and information sciences, 02 engineering and technology, F.1.1, F.3.1, F.4.1, 01 natural sciences, [INFO.INFO-PF]Computer Science [cs]/Performance [cs.PF], TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], 010201 computation theory & mathematics, Computer Science::Logic in Computer Science, Computer Science, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, [INFO]Computer Science [cs], Computer Science::Formal Languages and Automata Theory
Abstract: We define a new class of pushdown systems where the pushdown is a tree instead of a word. We allow a limited form of lookahead on the pushdown conforming to a certain ordering restriction, and we show that the resulting class enjoys a decidable reachability problem. This follows from a preservation of recognizability result for the backward reachability relation of such systems. As an application, we show that our simple model can encode several formalisms generalizing pushdown systems, such as ordered multi-pushdown systems, annotated higher-order pushdown systems, the Krivine machine, and ordered annotated multi-pushdown systems. In each case, our procedure yields tight complexity., Comment: full technical report of FST-TCS'15 paper
Published: 2015

12. An Efficient Implementation of Tiled Polymorphic Temporal Media

Author: Simon Archipoff, Models for a Structured Programming of Space and Time (PoSET), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), ACM SIGPAN, ANR-12-CORD-0009,INEDIT,INteractivité dans l'Ecriture De l'Interaction et du Temps(2012), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Functional programming, multimedia, ACM: H.: Information Systems/H.5: INFORMATION INTERFACES AND PRESENTATION (e.g., HCI)/H.5.5: Sound and Music Computing, lazy scheduling, Computer science, timed programming, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Multimedia streams, Parallel computing, ENCODE, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, Rendering (computer graphics)
Abstract: International audience; Tiled Polymorphic Temporal Media (TPTM) are a convenient way to describe, compose and encode multimedia streams. This paper presents a TPTM encoding that allows simple and efficient implementation of both composition and rendering. In particular, an on-the-fly rendering procedure is provided in order to handle infinite (lazy) TPTM.
Published: 2015
Full Text: View/download PDF

13. Foundations for Reliable and Flexible Interactive Multimedia Scores

Author: Jaime Arias, Camilo Rueda, Myriam Desainte-Catherine, Carlos Olarte, Models for a Structured Programming of Space and Time (PoSET), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Universidade Federal do Rio Grande do Norte [Natal] (UFRN), Departamento de Electrónica, Pontificia Universidad Javeriana, Pontificia Universidad Javeriana (PUJ), ANR-12-CORD-0024,OSSIA,Open Scenario System for Interactive Application(2012), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
Subjects: Theoretical computer science, Computer science, 0102 computer and information sciences, 02 engineering and technology, USable, computer.software_genre, 01 natural sciences, Operational semantics, Tree Structures, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], 0202 electrical engineering, electronic engineering, information engineering, Formal verification, Execution model, Implementation, Formal Verification, Interactive Scores, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], Programming language, business.industry, Operational Semantics, [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM], [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Linear Logic, Linear logic, Tree structure, 010201 computation theory & mathematics, 020201 artificial intelligence & image processing, business, computer, Interactive media
Abstract: International audience; Interactive Scores (IS) is a formalism for composing and performing interactive multimedia scores with several applications in video games, live performance installations, and virtual museums. The composer defines the temporal organization of the score by asserting temporal relations (TRs) between temporal objects (TOs). At execution time, the performer may modify the start/stop times of the TOs by triggering interaction points and the system guarantees that all the TRs are satisfied. Implementations of IS and formal models of their behavior have already been proposed, but these do not provide usable means to reason about their properties. In this paper we introduce ReactiveIS, a programming language that fully captures the temporal structure of IS during both composition and execution. For that, we propose a semantics based on tree-like structures representing the execution state of the score at each point in time. The semantics captures the hierarchical aspects of IS and provides an intuitive representation of their execution. We also endow ReactiveIS with a logical semantics based on linear logic, thus widening the reasoning techniques available for IS. We show that ReactiveIS is general enough to capture the full behavior of IS and that it provides declarative ways to increase IS expressivity with, for instance, conditional statements and loops.
Published: 2015
Full Text: View/download PDF

14. OSSIA: towards a unified interface for scoring time and interaction

Author: Celerier, Jean-Michaël, Baltazar, Pascal, Bossut, Clément, Vuaille, Nicolas, Couturier, Jean-Michel, Desainte-Catherine, Myriam, Battier, Marc, Bresson, Jean, Couprie, Pierre, Davy-Rigaux, Cécile, Fober, Dominique, Geslin, Yann, Genevois, Hugues, Picard, François, Tacaille, Alice, Blue Yeti [St Georges de Didonne], GMEA [Albi], Centre National de Création Musicale, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Models for a Structured Programming of Space and Time (PoSET), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-12-CORD-0024,OSSIA,Open Scenario System for Interactive Application(2012), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Celerier, Jean-Michaël, Contenus et Interactions - Open Scenario System for Interactive Application - - OSSIA2012 - ANR-12-CORD-0024 - CONTINT - VALID, Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Bordeaux Segalen - Bordeaux 2, Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université Sciences et Technologies - Bordeaux 1-Université Bordeaux Segalen - Bordeaux 2, Institut national universitaire Champollion [Albi] (INUC), and Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées
Subjects: [INFO.INFO-MM] Computer Science [cs]/Multimedia [cs.MM], [INFO.INFO-SD]Computer Science [cs]/Sound [cs.SD], [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM], ComputingMilieux_MISCELLANEOUS
Abstract: International audience; The theory of interactive scores addresses the writing and execution of temporal constraints between musical objects, with the ability to describe the use of interactivity in the scores. In this paper, a notation for the use of conditional branching in interactive scores will be introduced. It is based on a high level formalism for the authoring of interactive scores developed during the course of the OS-SIA research project. This formalism is meant to be at the same time easily manipulated by composers, and translat-able to multiple formal methods used in interactive scores like Petri nets and timed automaton. An application programming interface that allows the interactive scores to be embedded in other software and the authoring software, I-SCORE, will be presented.
Published: 2015
Full Text: View/download PDF

15. A logical approach to grammar description

Author: Jérôme Kirman, Sylvain Salvati, Lionel Clément, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Models for a Structured Programming of Space and Time (PoSET), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), ANR-12-CORD-0004,Polymnie,Analyse et synthèse dans les grammaires catégorielles abstraites : du lexique au discours(2012), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Linguistics and Language, ACM: I.: Computing Methodologies/I.2: ARTIFICIAL INTELLIGENCE/I.2.7: Natural Language Processing/I.2.7.2: Language models, Abstract Categorial Grammars, logical transduction, lambda calculus, 0102 computer and information sciences, ACM: I.: Computing Methodologies/I.2: ARTIFICIAL INTELLIGENCE/I.2.7: Natural Language Processing/I.2.7.3: Language parsing and understanding, computer.software_genre, 01 natural sciences, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], grammar description, ACM: I.: Computing Methodologies/I.2: ARTIFICIAL INTELLIGENCE/I.2.7: Natural Language Processing, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], lcsh:P1-1091, Computer Science::Logic in Computer Science, Finite State Automata, computer.programming_language, Mathematics, 060201 languages & linguistics, logic, Natural deduction, Syntax (programming languages), Categorial grammar, Programming language, business.industry, Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing), 06 humanities and the arts, Combinatory categorial grammar, [SCCO.LING]Cognitive science/Linguistics, Computer Science Applications, Tree-adjoining grammar, lcsh:Philology. Linguistics, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, 010201 computation theory & mathematics, Modeling and Simulation, 0602 languages and literature, Artificial intelligence, L-attributed grammar, Lambda calculus, business, computer, Typed lambda calculus, Natural language processing
Abstract: International audience; In the tradition of Model Theoretic Syntax, we propose a logical approach to the description of grammars. We combine in one formalism several tools that are used throughout computer science for their power of abstraction: logic and lambda calculus. We propose then a high-level formalism for describing mildly context sensitive grammars and their semantic interpretation. As we rely on the correspondence between logic and finite state automata, our method combines con-ciseness with effectivity. We illustrate our approach with a simple linguistic model of several interleaved linguistic phenomena involving extraction. The level of abstraction provided by logic and lambda calculus allows us not only to use this linguistic model for several languages, namely English, German, and Dutch, but also for semantic interpretation.
Published: 2015
Full Text: View/download PDF

16. Inverse monoids of higher-dimensional strings

Author: David Janin, Models for a Structured Programming of Space and Time (PoSET), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), ANR-12-CORD-0009,INEDIT,INteractivité dans l'Ecriture De l'Interaction et du Temps(2012), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Janin, David, and Contenus et Interactions - INteractivité dans l'Ecriture De l'Interaction et du Temps - - INEDIT2012 - ANR-12-CORD-0009 - CONTINT - VALID
Subjects: Algebraic structure, 02 engineering and technology, 01 natural sciences, Simple set, Morphism, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Simple (abstract algebra), 0202 electrical engineering, electronic engineering, information engineering, 0101 mathematics, [INFO.INFO-FL] Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Mathematics, Discrete mathematics, [INFO.INFO-MM] Computer Science [cs]/Multimedia [cs.MM], Graph rewriting, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], 010102 general mathematics, [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM], [INFO.INFO-SD] Computer Science [cs]/Sound [cs.SD], [INFO.INFO-PL] Computer Science [cs]/Programming Languages [cs.PL], Decidability, Inverse semigroup, [MATH.MATH-LO]Mathematics [math]/Logic [math.LO], Product (mathematics), [INFO.INFO-SD]Computer Science [cs]/Sound [cs.SD], [MATH.MATH-LO] Mathematics [math]/Logic [math.LO], 020201 artificial intelligence & image processing
Abstract: International audience; Halfway between graph transformation theory and inverse semigroup theory, we define higher dimensional strings as bi-deterministic graphs with distinguished sets of input roots and output roots. We show that these generalized strings can be equipped with an associative product so that the resulting algebraic structure is an inverse semigroup. Its natural order is shown to capture existence of root preserving graph mor-phism. A simple set of generators is characterized. As a subsemigroup example, we show how all finite grids are finitely generated. Last, simple additional restrictions on products lead to the definition of subclasses with decidable Monadic Second Order (MSO) language theory.
Published: 2015

17. Le séquenceur interactif multimédia i-score

Author: Arias, Jaime, Celerier, Jean-Michaël, Jaime, Arias, Contenus et Interactions - Open Scenario System for Interactive Application - - OSSIA2012 - ANR-12-CORD-0024 - CONTINT - VALID, Models for a Structured Programming of Space and Time (PoSET), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), ANR-12-CORD-0024,OSSIA,Open Scenario System for Interactive Application(2012), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Subjects: [INFO.INFO-MM] Computer Science [cs]/Multimedia [cs.MM], [INFO.INFO-CE]Computer Science [cs]/Computational Engineering, Finance, and Science [cs.CE], [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM], [INFO.INFO-CE] Computer Science [cs]/Computational Engineering, Finance, and Science [cs.CE], [INFO.INFO-ES]Computer Science [cs]/Embedded Systems, [INFO.INFO-ES] Computer Science [cs]/Embedded Systems
Abstract: National audience; Le séquenceur interactif multimédia i-score permet de décrire le temps de manière fine avec des outils issus de la programmation, pour des personnes n’ayant pas de pratique de développement logiciel.
Published: 2015

18. Typing Weak MSOL Properties

Author: Igor Walukiewicz, Sylvain Salvati, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Models for a Structured Programming of Space and Time (PoSET), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Walukiewicz, Igor, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, Computer Science - Logic in Computer Science, [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], higher-order verification, 0102 computer and information sciences, 02 engineering and technology, computer.software_genre, 01 natural sciences, Dependent type, Curry–Howard correspondence, Denotational semantics, Computer Science::Logic in Computer Science, LambdaY-Calculus, 0202 electrical engineering, electronic engineering, information engineering, Tree automaton, 0101 mathematics, Mathematics, Soundness, Functional programming, Programming language, 010102 general mathematics, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], 020207 software engineering, 16. Peace & justice, Logic in Computer Science (cs.LO), TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, 010201 computation theory & mathematics, Completeness (logic), TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, Computer Science::Programming Languages, 020201 artificial intelligence & image processing, computer, Normalisation by evaluation
Abstract: We consider lambda-Y-calculus as a non-interpreted functional programming language: the result of the execution of a program is its normal form that can be seen as the tree of calls to built-in operations. Weak monadic second-order logic (wMSOL) is well suited to express properties of such trees. We give a type system for ensuring that the result of the execution of a lambda-Y-program satisfies a given wMSOL property. In order to prove soundness and completeness of the system we construct a denotational semantics of lambda-Y-calculus that is capable of computing properties expressed in wMSOL., Logical Methods in Computer Science ; Volume 13, Issue 1 ; 1860-5974
Published: 2015
Full Text: View/download PDF

19. MIX is a 2-MCFL and the word problem in $\mathbb{Z}^2$ is solved by a third-order collapsible pushdown automaton

Author: Salvati, Sylvain, Models for a Structured Programming of Space and Time (PoSET), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Salvati, Sylvain, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Subjects: [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], [INFO.INFO-CL] Computer Science [cs]/Computation and Language [cs.CL], [MATH.MATH-AT]Mathematics [math]/Algebraic Topology [math.AT], ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.3: Formal Languages, ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.2: Grammars and Other Rewriting Systems, [MATH.MATH-AT] Mathematics [math]/Algebraic Topology [math.AT], [MATH.MATH-GR]Mathematics [math]/Group Theory [math.GR], [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], [MATH.MATH-GR] Mathematics [math]/Group Theory [math.GR], [INFO.INFO-FL] Computer Science [cs]/Formal Languages and Automata Theory [cs.FL]
Abstract: International audience; In this work we establish that the language $MIX = \{w \in \{a;b;c\}^\ast \vert |w|_a = |w|_b = |w|_c\}$ and the language $O_2 = \{w \in \{a;\overline{a};b;\overline{b}\} \vert |w|_a = |w|_{\overline{a}} \land |w|_b = |w|_{\overline{b}}\}$ are 2-MCFLs. As 2-MCFLs form a class of languages that is included in both the IO and OI hierarchies, and as $O_2$ is the group language of a simple presentation of $\mathbb{Z}^2$ we exhibit here the first, to our knowledge, non-virtually-free group language (\textit{i.e.} non-context-free group language) that is captured by the IO and OI hierarchies. Moreover, it was a long-standing open problem whether MIX was a mildly context sensitive language or not, and it was conjectured that it was not, so we close this conjecture by giving it a negative answer.
Published: 2015

20. On labeled birooted tree languages: algebras, automata and logic

Author: David Janin, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Models for a Structured Programming of Space and Time (PoSET), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), ANR-12-CORD-0009,INEDIT,INteractivité dans l'Ecriture De l'Interaction et du Temps(2012), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Class (set theory), Semantics (computer science), formal language, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, Philosophy of language, Regular language, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Formal language, birooted tree, 0202 electrical engineering, electronic engineering, information engineering, 0101 mathematics, inverse semigroup, Mathematics, Discrete mathematics, algebraic recognizability, premorphism, 010102 general mathematics, Abstract family of languages, Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing), Computer Science Applications, Algebra, Inverse semigroup, [MATH.MATH-LO]Mathematics [math]/Logic [math.LO], TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, Computational Theory and Mathematics, Computer Science::Programming Languages, 020201 artificial intelligence & image processing, Tree (set theory), Computer Science::Formal Languages and Automata Theory, Information Systems
Abstract: International audience; With an aim to developing expressive language theoretical tools applicable to inverse semigroup languages, that is, subsets of inverse semigroups, this paper explores the language theory of finite labeled birooted trees: Munn's birooted trees extended with vertex labeling. To this purpose, we define a notion of finite state birooted tree automata that simply extends finite state word automata semantics. This notion is shown to capture the class of languages that are definable in Monadic Second Order Logic and upward closed with respect to the natural order defined in the inverse monoid structure induced by labeled birooted trees. Then, we derive from these automata the notion of quasi-recognizable languages, that is, languages recognizable by means of (adequate) premorphisms into finite (adequately) ordered monoids. This notion is shown to capture finite Boolean combinations of languages as above. Applied to a simple encoding of finite (mono-rooted) labeled tree languages in of labeled birooted trees, we show that classical regular languages of finite (mono-rooted) trees are quasi-recognizable in the above sense. The notion of quasi-recognizability thus appears as an adequate remedy to the known collapse of the expressive power of classical algebraic tools when applied to inverse semigroups. Illustrative examples, in relation to other known algebraic or automata theoretic frameworks for defining languages of finite trees, are provided throughout.
Published: 2015
Full Text: View/download PDF

21. Flux média tuilés polymorphes: une sémantique opérationnelle en Haskell

Author: Bazin, Théis, Janin, David, Janin, David, Contenus et Interactions - INteractivité dans l'Ecriture De l'Interaction et du Temps - - INEDIT2012 - ANR-12-CORD-0009 - CONTINT - VALID, École normale supérieure - Cachan (ENS Cachan), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), David Baelde, Jade Alglave, Models for a Structured Programming of Space and Time (PoSET), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), ANR-12-CORD-0009,INEDIT,INteractivité dans l'Ecriture De l'Interaction et du Temps(2012), Baelde, David, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Subjects: [INFO.INFO-MM] Computer Science [cs]/Multimedia [cs.MM], [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM], [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], [INFO.INFO-PL] Computer Science [cs]/Programming Languages [cs.PL]
Abstract: National audience; De nombreux outils sont aujourd'hui disponibles pour l'analyse et la production temps réel de flux média temporisés : son, vidéo, animation. Néanmoins, la coordination de ces outils, la synchronisation des flux qu'ils analysent et produisent, sur des échelles de temps de valeurs et même de nature différentes, reste une affaire délicate. Le modèle des Tiled Polymorphic Temporal Media (ou tptm), qui combine en un même formalisme le contenu média de ces flux et leurs marqueurs de synchronisation, vise a remédier à cela. Dans le modèle, le produit de deux flux ainsi enrichis, paramétré par ces marqueurs de syn-chronisation, est tout à la fois séquentiel et parallèle : c'est un produit tuilé. D'un point de vue théorique, la sémantique de ces flux tuilés peut être décrite à l'aide des monoïdes inversifs. Pour l'aspect pratique, nous pro-posons ici, en Haskell, la première implémentation réellement polymorphe et inversive de ces Tiled Polymorphic Temporal Media. Notre implémenta-tion permet en outre, via le mécanisme d'évaluation paresseuse d'Haskell, de distinguer simplement la syntaxe de ces flux – un système d'équations tuilées – de leur sémantique opérationnelle – la résolution de ce système à la volée.
Published: 2015

22. Using models to model-check recursive schemes

Author: Sylvain Salvati, Igor Walukiewicz, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Models for a Structured Programming of Space and Time (PoSET), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Salvati, Sylvain, Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
Subjects: Model checking, FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Property (philosophy), [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], Theoretical computer science, General Computer Science, Computer science, 0102 computer and information sciences, 01 natural sciences, Theoretical Computer Science, Operator (computer programming), [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Simple (abstract algebra), 0101 mathematics, Divergence (statistics), Mathematics, Simply typed lambda calculus, 010102 general mathematics, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Automaton, Decidability, Pure type system, Logic in Computer Science (cs.LO), TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, 010201 computation theory & mathematics, simply-typed lambda calculus, TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, verification, Algorithm, Typed lambda calculus
Abstract: We propose a model-based approach to the model checking problem for recursive schemes. Since simply typed lambda calculus with the fixpoint operator, lambda-Y-calculus, is equivalent to schemes, we propose the use of a model of lambda-Y-calculus to discriminate the terms that satisfy a given property. If a model is finite in every type, this gives a decision procedure. We provide a construction of such a model for every property expressed by automata with trivial acceptance conditions and divergence testing. Such properties pose already interesting challenges for model construction. Moreover, we argue that having models capturing some class of properties has several other virtues in addition to providing decidability of the model-checking problem. As an illustration, we show a very simple construction transforming a scheme to a scheme reflecting a property captured by a given model., Comment: Long version of a paper presented at TLCA 2013
Published: 2015
Full Text: View/download PDF

23. Non-linear Second order Abstract Categorial Grammars and deletion

Author: Sylvain Salvati, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Models for a Structured Programming of Space and Time (PoSET), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Makoto Kanazawa, ANR-12-CORD-0004,Polymnie,Analyse et synthèse dans les grammaires catégorielles abstraites : du lexique au discours(2012), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], Rule-based machine translation, abstract categorial grammars, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], linear logic, 0202 electrical engineering, electronic engineering, information engineering, ACM: F.: Theory of Computation/F.3: LOGICS AND MEANINGS OF PROGRAMS/F.3.2: Semantics of Programming Languages/F.3.2.1: Denotational semantics, Mathematics, computer.programming_language, Discrete mathematics, Categorial grammar, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Combinatory categorial grammar, lambda-calculus, 16. Peace & justice, Linear logic, Tree-adjoining grammar, ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.1: Mathematical Logic/F.4.1.2: Lambda calculus and related systems, 010201 computation theory & mathematics, 020201 artificial intelligence & image processing, L-attributed grammar, Lambda calculus, computer, Coherence (linguistics), ACM: F.: Theory of Computation/F.4: MATHEMATICAL LOGIC AND FORMAL LANGUAGES/F.4.3: Formal Languages/F.4.3.4: Operations on languages
Abstract: International audience; We prove that non-linear second order Abstract Categorial Grammars (2ACGs) are equivalent to non-deleting 2ACGs. We prove this result first by using the intersection types discipline. Then we explain how coherence spaces can yield the same result. This result shows that restricting the Montagovian approach to natural language semantics to use only ΛI-terms has no impact in terms of the definable syn-tax/semantics relations. Moreover from the ACG perspective this result is a generalization of a result by Yoshinaka: it shows that deletion add no expressive power to second order ACGs.
Published: 2015

24. Two-way automata and regular languages of overlapping tiles

Author: Anne Dicky, David Janin, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Models for a Structured Programming of Space and Time (PoSET), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-12-CORD-0009,INEDIT,INteractivité dans l'Ecriture De l'Interaction et du Temps(2012), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
Subjects: Monoid, F.1.1 Models of Computation, F.4.1 Mathematical Logic, F.4.3 Formal Languag, Nested word, TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, two-way automata, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, Combinatorics, pebble automata, Regular language, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Computer Science::Logic in Computer Science, Formal language, 0202 electrical engineering, electronic engineering, information engineering, Regular expression, 0101 mathematics, languages of words, Mathematics, Discrete mathematics, free inverse monoids, Algebra and Number Theory, languages of overlapping tiles, 010102 general mathematics, Abstract family of languages, Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing), Cone (formal languages), Pumping lemma for regular languages, [MATH.MATH-LO]Mathematics [math]/Logic [math.LO], TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, Computational Theory and Mathematics, Computer Science::Programming Languages, 020201 artificial intelligence & image processing, Computer Science::Formal Languages and Automata Theory, Information Systems
Abstract: International audience; We consider classes of languages of overlapping tiles, i.e., subsets of the McAlister monoid: the class REG of languages definable by Kleene’s regular expressions, the class MSO of languages definable by formulas of monadic second-order logic, and the class REC of languages definable by morphisms into finite monoids. By extending the semantics of finite-state two-way au- tomata (possibly with pebbles) from languages of words to languages of tiles, we obtain a complete characterization of the classes REG and MSO. In particular, we show that adding pebbles strictly increases the expressive power of two-way automata recognizing languages of tiles, but the hierarchy induced by the number of allowed pebbles collapses to level one.
Published: 2015
Full Text: View/download PDF

25. A syntactic congruence for languages of birooted trees

Author: David Janin, Achim Blumensath, Technische Universität Darmstadt (TU Darmstadt), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Models for a Structured Programming of Space and Time (PoSET), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), ANR-12-CORD-0009,INEDIT,INteractivité dans l'Ecriture De l'Interaction et du Temps(2012), Technische Universität Darmstadt - Technical University of Darmstadt (TU Darmstadt), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Inverse, 02 engineering and technology, inverse semigroups, birooted tree languages, 01 natural sciences, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], Philosophy of language, Combinatorics, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Computer Science::Logic in Computer Science, 0202 electrical engineering, electronic engineering, information engineering, Congruence (manifolds), 0101 mathematics, Algebra over a field, Mathematics, prehomomorphism, syntactic congruence, Bisimulation, Discrete mathematics, Algebra and Number Theory, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], Semigroup, 010102 general mathematics, minimal recognizer, [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM], Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing), Extension (predicate logic), Composition (combinatorics), 16. Peace & justice, partially ordered monoid, partial algebra theory, formal language theory, [MATH.MATH-LO]Mathematics [math]/Logic [math.LO], bisimulation, [INFO.INFO-SD]Computer Science [cs]/Sound [cs.SD], algebraic recognisability, 020201 artificial intelligence & image processing, Computer Science::Formal Languages and Automata Theory
Abstract: International audience; The study of languages of labelled birooted trees, that is, elements of the free inverse monoid enriched by a vertex labelling, has led to the notion of quasi-recognisability. It generalises the usual notion of recognisability by replacing homomorphisms by certain prehomomorphism into finite ordered monoids, called adequate, that only preserve some products: the so-called disjoint ones. In this paper we study the underlying partial algebra setting and we define a suitable notion of a syntactic congruence such that (i) having a syntactic congruence of finite index captures MSO-definability; (ii) a certain order-bisimulation refinement of the syntactic congruence captures quasi-recognisability in the same way.
Published: 2014
Full Text: View/download PDF

26. Tiled Polymorphic Temporal Media

Author: Paul Hudak, David Janin, Department of Computer Science (YALE), Yale University [New Haven], Models for a Structured Programming of Space and Time (PoSET), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), ANR-12-CORD-0009,INEDIT,INteractivité dans l'Ecriture De l'Interaction et du Temps(2012), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
Subjects: Monoid, Theoretical computer science, Algebraic structure, 0102 computer and information sciences, 02 engineering and technology, algebraic reasoning, 01 natural sciences, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Synchronization (computer science), 0202 electrical engineering, electronic engineering, information engineering, inverse semigroup, Mathematics, computer.programming_language, Functional programming, multimedia, temporal values, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM], Undecidable problem, Decidability, [MATH.MATH-LO]Mathematics [math]/Logic [math.LO], 010201 computation theory & mathematics, Haskell, [INFO.INFO-SD]Computer Science [cs]/Sound [cs.SD], 020201 artificial intelligence & image processing, Lazy evaluation, Algorithm, computer
Abstract: International audience; Tiled Polymorphic Temporal Media (Tiled PTM) is an algebraic approach to specifying the composition of multimedia values having an inherent temporal quality --- for example sound clips, musical scores, computer animations, and video clips. Mathematically, one can think of a tiled PTM as a tiling in the one dimension of time. A tiled PTM value has two synchronization marks that specify, via an effective notion of tiled product, how the tiled PTMs are positioned in time relative to one another, possibly with overlaps. Together with a pseudo inverse operation, and the related reset and co-reset projection operators, the tiled product is shown to encompass both sequential and parallel products over temporal media. Up to observational equivalence, the resulting algebra of tiled PTM is shown to be an inverse monoid: the pseudo inverse being a semigroup inverse. These and other algebraic properties are explored in detail. In addition, recursively-defined infinite tiles are considered. Ultimately, in order for a tiled PTM to be \emph{renderable}, we must know its beginning, and how to compute its evolving value over time. Though undecidable in the general case, we define decidable special cases that still permit infinite tilings. Finally, we describe an elegant specification, implementation, and proof of key properties in Haskell, whose lazy evaluation is crucial for assuring the soundness of recursive tiles. Illustrative examples, within the Euterpea framework for musical temporal media, are provided throughout.
Published: 2014
Full Text: View/download PDF

27. Embedding finite and infinite words into overlapping tiles

Author: David Janin, Anne Dicky, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Models for a Structured Programming of Space and Time (PoSET), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), A.A. Bulatov and A.M. Shur, ANR-12-CORD-0009,INEDIT,INteractivité dans l'Ecriture De l'Interaction et du Temps(2012), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Monoid, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], MSO, 010102 general mathematics, Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing), 0102 computer and information sciences, Characterization (mathematics), tiles overlaps, infinite strings, 01 natural sciences, formal languages, Algebra, Inverse semigroup, [MATH.MATH-LO]Mathematics [math]/Logic [math.LO], Regular language, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], 010201 computation theory & mathematics, Formal language, Embedding, 0101 mathematics, Algebraic number, Computer Science::Formal Languages and Automata Theory, Mathematics
Abstract: International audience; In this paper, we study languages of finite and infinite birooted words. We show how the embedding of free ω-semigroups of finite and infinite words into the monoid of birooted words can be generalized to the embedding of two-sorted ω-semigroups into (some notion of) one- sorted ordered ω-monoids. This leads to an algebraic characterization of regular languages of finite and infinite birooted words that generalizes and unifies the known algebraic characterizations of regular languages of finite and infinite words.
Published: 2014
Full Text: View/download PDF

28. Modelling Data Processing for Interactive Scores Using Coloured Petri Nets

Author: Camilo Rueda, Myriam Desainte-Catherine, Jaime Arias, Models for a Structured Programming of Space and Time (PoSET), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Departamento de Electrónica, Pontificia Universidad Javeriana, Pontificia Universidad Javeriana (PUJ), ANR-12-CORD-0024,OSSIA,Open Scenario System for Interactive Application(2012), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Data processing, Data Processing, Interactive Scores, Theoretical computer science, Coloured Petri Nets, Formal Specification, Computer science, business.industry, Programming language, [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM], 02 engineering and technology, Petri net, Process architecture, computer.software_genre, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, Data modeling, CPN Tools, 020204 information systems, Formal specification, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, business, computer, Execution model, Interactive media
Abstract: International audience; I-score is a system for the composition and execution of interactive multimedia scores. It uses Hierarchical Time Stream Petri Nets (HTSPN) to build an execution model of the scores. Nowadays, composers have increasingly needed to represent and manipulate complex data in their multimedia scenarios. However, HTSPN formalism does not allow to handle data. In this work, we propose a model to execute interactive multimedia scores based on Coloured Petri Nets (CPN). Our work extends the current execution model of i-score with the capability to handle complex data. Our approach consists in developing CPN modules for reading, appending and reversing audio files. We use CPN Tools for prototyping, simulating and verifying our model and discuss how to represent fundamental signal processing functions, conditionals or loops.
Published: 2014
Full Text: View/download PDF

29. Algebraic tools for the overlapping tile product

Author: Etienne Dubourg, David Janin, methodes formelles, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Models for a Structured Programming of Space and Time (PoSET), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), ANR-12-CORD-0009,INEDIT,INteractivité dans l'Ecriture De l'Interaction et du Temps(2012), Janin, David, Contenus et Interactions - INteractivité dans l'Ecriture De l'Interaction et du Temps - - INEDIT2012 - ANR-12-CORD-0009 - CONTINT - VALID, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: Monoid, TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], premorphism, Inverse, 16. Peace & justice, partially ordered monoid, Automaton, [INFO.INFO-PL] Computer Science [cs]/Programming Languages [cs.PL], Mathematical theory, Algebra, Inverse semigroup, [MATH.MATH-LO]Mathematics [math]/Logic [math.LO], TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], visual_art, restricted product, visual_art.visual_art_medium, Restricted product, [MATH.MATH-LO] Mathematics [math]/Logic [math.LO], Tile, Algebraic number, inverse semigroup, Mathematics, [INFO.INFO-FL] Computer Science [cs]/Formal Languages and Automata Theory [cs.FL]
Abstract: International audience; Overlapping tile automata and the associated notion of recognizability by means of (adequate) premorphisms in finite ordered monoids have recently been defined for coping with the collapse of classical recognizability in inverse monoids. In this paper, we investigate more in depth the associated algebraic tools that allows for a better understanding of the underlying mathematical theory. In particular, addressing the surprisingly difficult problem of language product and star, we eventually found some deep links with classical notions of inverse semigroup theory such as the notion of restricted product.
Published: 2014

30. The Failure of the Strong Pumping Lemma for Multiple Context-Free Languages

Author: Ryo Yoshinaka, Jens Michaelis, Sylvain Salvati, Makoto Kanazawa, Gregory M. Kobele, National Institute of Informatics (NII), Computation Institute [Chicago], University of Chicago, Universität Bielefeld = Bielefeld University, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Models for a Structured Programming of Space and Time (PoSET), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Graduate School of Informatics [Kyoto], Kyoto University, Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Kyoto University [Kyoto]
Subjects: Combinatorics, Discrete mathematics, Computational Theory and Mathematics, Multiple context, Multiple context-free grammar, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Pumping lemma, U-1, Pumping lemma for regular languages, [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], Theoretical Computer Science, Mathematics
Abstract: Seki et al. (Theor. Comput. Sci. 88(2):191-229, 1991) showed that every m-multiple context-free language L is weakly 2m-iterative in the sense that either L is finite or L contains a subset of the form {u0w1iu1w2miu2m|i≥0}, where w1···w2m≠ε. Whether every m-multiple context-free language L is 2m-iterative, that is to say, whether all but finitely many elements z of L can be written as z=u0w1u1w2mu2m with w1···w2m≠ε and {u0w1iu1···w2miu2m|i≥0}⊆L, has been open. We show that there is a 3-multiple context-free language that is not k-iterative for any k.
Published: 2014
Full Text: View/download PDF

31. Towards a Higher-Dimensional String Theory for the Modeling of Computerized Systems

Author: David Janin, Models for a Structured Programming of Space and Time (PoSET), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), ANR-12-CORD-0009,INEDIT,INteractivité dans l'Ecriture De l'Interaction et du Temps(2012), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
Subjects: Theoretical computer science, Computer science, inverse semigroups, 02 engineering and technology, String theory, 01 natural sciences, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Formal language, 0202 electrical engineering, electronic engineering, information engineering, 0101 mathematics, algerbaic tools, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], logic definability, Cayley graph, business.industry, 010102 general mathematics, [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM], premorphisms, formal languages, [MATH.MATH-LO]Mathematics [math]/Logic [math.LO], Inverse semigroup, Tree (data structure), [INFO.INFO-SD]Computer Science [cs]/Sound [cs.SD], Automata theory, 020201 artificial intelligence & image processing, Artificial intelligence, business, Theme (computing), Word (computer architecture), birooted graphs
Abstract: International audience; Recent modeling experiments conducted in computational music give evidence that a number of concepts, methods and tools belonging to inverse semigroup theory can be attuned towards the concrete modeling of time-sensitive interactive systems. Further theoretical developments show that some related notions of higher-dimensional strings can be used as a unifying theme across word or tree automata theory. In this invited paper, we will provide a guided tour of this emerging theory both as an abstract theory and with a view to concrete applications.
Published: 2014
Full Text: View/download PDF

32. Towards an Hybrid Temporal Paradigm for Musical Composition and Performance

Author: Desainte-Catherine, Myriam, Allombert, Antoine, Assayag, Gérard, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Models for a Structured Programming of Space and Time (PoSET), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Sciences et Technologies de la Musique et du Son (STMS), Institut de Recherche et Coordination Acoustique/Musique (IRCAM)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Représentations musicales (Repmus), Institut de Recherche et Coordination Acoustique/Musique (IRCAM)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche et Coordination Acoustique/Musique (IRCAM)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Assayag, Gérard
Subjects: [INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], constraint propagation, petri nets, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO] Computer Science [cs], [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL], [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], computer music, temporal logic, [INFO.INFO-CL] Computer Science [cs]/Computation and Language [cs.CL], [INFO]Computer Science [cs], scheduling, [INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC], [INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC]
Abstract: International audience; In this article, we consider the possibility of mixing two main paradigms of electroacoustic music: the writing-oriented and the performance-oriented paradigms.We show that these two opposing paradigms are the consequence of two corresponding conceptions of time. In addition, we assume that the temporal aspects of a performer's interpretation of a musical composition can be linked to both paradigms. Based on this theoretical study, we propose a formalism for composing pieces of electroacoustic music that can be interpreted in performance.
Published: 2013

33. A Review of Neural Network-Based Emulation of Guitar Amplifiers

Author: Tara Vanhatalo, Pierrick Legrand, Myriam Desainte-Catherine, Pierre Hanna, Antoine Brusco, Guillaume Pille, Yann Bayle, Université de Bordeaux (UB), Méthodes avancées d’apprentissage statistique et de contrôle (ASTRAL), Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Naval Group, Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Orosys, Centre National de la Recherche Scientifique (CNRS), Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), and Université Sciences et Technologies - Bordeaux 1 (UB)
Subjects: Fluid Flow and Transfer Processes, audio signal processing, neural network, Process Chemistry and Technology, electric musical instruments, General Engineering, deep learning, virtual analog modelling, modelling nonlinear audio effects, nonlinear modelling, audio effects modelling, Computer Science Applications, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], distortion effects, General Materials Science, Instrumentation
Abstract: International audience; Vacuum tube amplifiers present sonic characteristics frequently coveted by musicians, that are often due to the distinct nonlinearities of their circuits, and accurately modelling such effects can be a challenging task. A recent rise in machine learning methods has lead to the ubiquity of neural networks in all fields of study including virtual analog modelling. This has lead to the appearance of a variety of architectures tailored to this task. This article aims to provide an overview of the current state of the research in neural emulation of analog distortion circuits by first presenting preceding methods in the field and then focusing on a complete review of the deep learning landscape that has appeared in recent years, detailing each subclass of available architectures. This is done in order to bring to light future possible avenues of work in this field.
Published: 2022
Full Text: View/download PDF

34. RE.MI.DO 3.0 RECHERCHE EMOTION / MUSIQUE, INTERNET DES OBJETS

Author: Vulliard, Pierre-Henri, Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1, AFIM, and Sciencesconf.org, CCSD
Subjects: [SHS.MUSIQ] Humanities and Social Sciences/Musicology and performing arts, [SCCO]Cognitive science, [SHS.MUSIQ]Humanities and Social Sciences/Musicology and performing arts, [INFO]Computer Science [cs], [MATH] Mathematics [math], [SCCO] Cognitive science, [INFO] Computer Science [cs], [MATH]Mathematics [math]
Abstract: International audience; Pour suivre l'évolution des systèmes de communication, et celle des outils de production musicale, notre projet dans le domaine musique/émotions devait être réorienté. Notre choix a été d'utiliser ou de détourner des outils grand public, pour leur facilité d'utilisation et pour leur compatibilité entre eux. Les logiciels choisis pour la production musicale sont ceux utilisés par les Disc Jockey (DJ). Les outils de communication et de gestion des données ont, quant à eux, été sélectionnés dans le domaine de la domotique. Le contact avec le public (dans l'esprit des recherches participatives) revêtant pour nous une importance particulière, nous avons complété les expérimentations en concert par une diffusion sur le web. Nous avons opté pour une collaboration avec une « web radio », pour sa forme et ses usages parfaitement adaptés à un projet musical, son accessibilité excellente grâce aux smartphones, et son intégration dans l’environnement domotique, déjà habituelle dans certains pays grâce au boom mondial des enceintes connectées. La web radio choisie étant à vocation musicale et régionale, elle nous offre en plus un environnement extrêmement intéressant pour notre projet.
Published: 2021

35. Architecture Logicielle de la Sortie de Résidence d'Aléas

Author: Keller, Thibaud, Rocailleux, Camille, Serpette, Bernard, Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB), Compagnie EVER, Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria), Université Sciences et Technologies - Bordeaux 1, and Serpette, Bernard
Subjects: [INFO.INFO-MM] Computer Science [cs]/Multimedia [cs.MM], [INFO.INFO-PF]Computer Science [cs]/Performance [cs.PF], [INFO.INFO-PF] Computer Science [cs]/Performance [cs.PF], [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM]
Abstract: International audience; Le but du projet Aléas est de faire éclore un dialogue artistique entre l'ordinateur et l'humain, de concevoir un cadre propice à une improvisation homme-machine, de capter des mouvements et des sons pour en faire quelque chose. À mi-chemin du projet nous avons effectué une résidence de 12 jours dans le MÉCAstudio qui est un espace de l'OARA 1 à l'intérieur de la MÉCA 2 de Bordeaux. Quatre représentations sont venues clore cette résidence le 21 novembre, dans le MÉCAstudio, de 20 minutes chacune. Nous donnons ici les éléments techniques ayant contribué à la réalisation de ces événements.
Published: 2020

36. A Symbolic Model for Timed Concurrent Constraint Programming

Author: Jaime Arias, Michell Guzmán, Carlos Olarte, Models for a Structured Programming of Space and Time (PoSET), Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1-Université Sciences et Technologies - Bordeaux 1-Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Universidad del Valle, Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Universidade Federal do Rio Grande do Norte [Natal] (UFRN), Departamento de Electrónica, Pontificia Universidad Javeriana, Pontificia Universidad Javeriana (PUJ), ANR-12-CORD-0024,OSSIA,Open Scenario System for Interactive Application(2012), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Concurrent constraint logic programming, Model checking, Theoretical computer science, General Computer Science, Computer science, Concurrency, Temporal logic, computer.software_genre, Logical consequence, Operational semantics, Theoretical Computer Science, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], temporal logic, Synchronization (computer science), Constraint logic programming, Constraint programming, Time complexity, Programming language, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], 16. Peace & justice, Concurrent constraint programming, model checking, computer, Computer Science(all)
Abstract: International audience; Concurrent Constraint Programming (ccp) is a model for concurrency where agents interact with each other by telling and asking constraints (i.e., formulas in logic) into a shared store of partial information. The ntcc calculus extends ccp with the notion of discrete time-units for the specification of reactive systems. Moreover, ntcc features constructors for non-deterministic choices and asynchronous behavior, thus allowing for (1) synchronization of processes via constraint entailment during a time-unit and (2) synchronization of processes along time-intervals. In this paper we develop the techniques needed for the automatic verification of ntcc programs based on symbolic model checking. We show that the internal transition relation, modeling the behavior of processes during a time-unit (1 above), can be symbolically represented by formulas in a suitable fragment of linear time temporal logic. Moreover, by using standard techniques as difference decision diagrams, we provide a compact representation of these constraints. Then, relying on a fixpoint characterization of the timed constructs, we obtain a symbolic model of the observable transition (2 above). We prove that our construction is correct with respect to the operational semantics. Finally, we introduce a prototypical tool implementing our method.
Full Text: View/download PDF

37. Loader and Urzyczyn Are Logically Related

Author: Salvati, S., Manzonetto, G., Gehrke, M., Barendregt, H., Czumaj, A., Mehlhorn, K., Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Logic, Computation and Reasoning [Villetaneuse] (LCR), Laboratoire d'Informatique de Paris-Nord (LIPN), Université Sorbonne Paris Cité (USPC)-Institut Galilée-Université Paris 13 (UP13)-Centre National de la Recherche Scientifique (CNRS)-Université Sorbonne Paris Cité (USPC)-Institut Galilée-Université Paris 13 (UP13)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Computing Science Department (CS), Radboud university [Nijmegen], Czumaj, A., Mehlhorn, K., Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Models for a Structured Programming of Space and Time (PoSET), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1 (UB)-Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Université Paris 13 (UP13)-Institut Galilée-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS)-Université Paris 13 (UP13)-Institut Galilée-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS), and Radboud University [Nijmegen]
Subjects: Discrete mathematics, Algebra and Topology, [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], 010102 general mathematics, Data Science, 020207 software engineering, 02 engineering and technology, Type (model theory), 01 natural sciences, Undecidable problem, Combinatorics, Loader, Intersection, 0202 electrical engineering, electronic engineering, information engineering, Full model, Lecture Notes in Computer Science, 0101 mathematics, Element (category theory), Algebra en Topologie, Finite set, Mathematics
Abstract: International audience; In simply typed \lam-calculus with one ground type the following theorem due to Loader holds. $(i)$ Given the full model $\cF$ over a finite set, %with at least seven elements, the question whether some element $f\in\cF$ is \lam-definable is undecidable. In the \lam-calculus with intersection types based on countably many atoms, the following is proved by Urzyczyn. $(ii)$ It is undecidable whether a type is inhabited. Both statements are major results presented in \cite{Bare2}. We show that $(i)$ and $(ii)$ follow from each other in a natural way, by interpreting intersection types as continuous functions logically related to elements of $\cF$. From this, and a result by Joly on \lam-definability, we get that \Urz's theorem already holds for intersection types with at most two atoms.
Published: 2012

38. Retrospat: A Perception-Based System For Semi-Automatic Diffusion Of Acousmatic Music

Author: Mouba, J., Marchand, S., Boris Mansencal, Rivet, J. -M, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), Université Sciences et Technologies - Bordeaux 1, Martin Supper, Stefan Weinzierl, and Marchand, Sylvain
Subjects: [INFO.INFO-SD]Computer Science [cs]/Sound [cs.SD], [INFO.INFO-SD] Computer Science [cs]/Sound [cs.SD]
Abstract: International audience; We present the RetroSpat system for the semi-automatic diffusion of acousmatic music. This system is intended to be a spatializer with perceptive feedback. More precisely, RetroSpat can guess the positions of physical sound sources (e.g. loudspeakers) from binaural inputs, and can then output multichannel signals to the loudspeakers while controlling the spatial location of virtual sound sources. Together with a realistic binaural spatialization technique taking into account both the azimuth and the distance, we propose a precise localization method which estimates the azimuth from the interaural cues and the distance from the brightness. This localization can be used by the system to adapt to the room acoustics and to the loudspeaker conﬁguration. We propose a simpliﬁed sinusoidal model for the interaural cues, the model parameters being derived from the CIPIC HRTF database. We extend the binaural spatialization to a multi-source and multi-loudspeaker spatialization system based on a static adaptation matrix. The methods are currently implemented in a real-time free software. Musical experiments are conducted at the SCRIME, Bordeaux.
Published: 2008
Full Text: View/download PDF

39. Spécification de la synthèse sonore appliquéeà la pédagogie musicale

Author: Desainte-Catherine, Myriam, Kurtag, György, AFIM, Association, Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME), and Université Sciences et Technologies - Bordeaux 1
Subjects: [SHS.MUSIQ] Humanities and Social Sciences/Musicology and performing arts, [SHS.MUSIQ]Humanities and Social Sciences/Musicology and performing arts, [INFO]Computer Science [cs], [INFO] Computer Science [cs]
Abstract: International audience; Nous présentons un projet d'ordre pluridisciplinaire dont l'objectif est le développement d'outils pédagogiques de synthèse sonore pour l'éveil musical.
Published: 2003

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

Select search scope, currently: Articles Catalog books, media & more in Jio Institute collections Articles journal articles & other e-resources

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Journal

Database

Publisher

39 results on '"Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME)"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources