Author: "Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME)" - 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 73 results

Start Over Author "Studio de Création et de Recherche en Informatique et Musique Électroacoustique (SCRIME)"

73 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. i-Berlioz : Interactive Computer-Aided Orchestration with Temporal Control

Author: Miranda, Eduardo, Antoine, Aurélien, Celerier, Jean-Michaël, Desainte-Catherine, Myriam, Plymouth University, McGill University = Université McGill [Montréal, Canada], 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: [INFO.INFO-SD]Computer Science [cs]/Sound [cs.SD], ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2018

3. Generating Orchestral Sequences with Timbral Descriptors

Author: Antoine, Aurélien, Miranda, Eduardo, Celerier, Jean-Michaël, Desainte-Catherine, Myriam, McGill University = Université McGill [Montréal, Canada], Plymouth University, 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)-É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-SD]Computer Science [cs]/Sound [cs.SD], ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2018

4. 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

5. Calculer le temps musical

Author: Desainte-Catherine, Myriam, 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), IRCAM, 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: [INFO.INFO-SD]Computer Science [cs]/Sound [cs.SD], ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2017

6. Exécution répartie de scénarios interactifs

Author: Celerier, Jean-Michaël, Desainte-Catherine, Myriam, Couturier, Jean-Michel, 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), Blue Yeti [St Georges de Didonne], 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-SD]Computer Science [cs]/Sound [cs.SD], ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2017

7. 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

8. Timed Denotational Semantics for Causal Functions over Timed Streams

Author: Janin, David, Serpette, Bernard Paul, 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), 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), LaBRI - Laboratoire Bordelais de Recherche en Informatique, 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-PL]Computer Science [cs]/Programming Languages [cs.PL], [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM]
Abstract: We consider timed system behaviors seen as functions acting over streams of timed events (timed streams) that satisfy a temporal causality property: at every instant, current outputs only depends on inputs that have already been received. We aim at defining a timed model for describing their denotational semantics in the style of Strachey’s and Scott’s domain approach. For such a purpose, we extend timed streams with a notion of partial timed streams that form together a directed complete partial order (DCPO). Continuous functions over these DCPOs are then natural candidates for modeling timed denotational semantics of causal functions. Indeed, restricting to some notion of pre-synchronous continuous functions, we show that every causal function admits a non empty lattice of possible semantics which least element corresponds to a latest or laziest semantics and which greatest element corresponds a earliest or eagerest semantics. These operational aspects are then made explicit by defining a operational semantics model for causal functions that is inspired by timed-IO automata theory.
Published: 2016

9. 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

10. 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

11. 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

12. A robust algebraic framework for high-level music writing and programming

Author: 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), Janin, 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)-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: [INFO.INFO-MM] Computer Science [cs]/Multimedia [cs.MM], [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], Computer Science::Sound, [INFO.INFO-SD]Computer Science [cs]/Sound [cs.SD], [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM], Computer Science::Programming Languages, [INFO.INFO-SD] Computer Science [cs]/Sound [cs.SD], [INFO.INFO-PL] Computer Science [cs]/Programming Languages [cs.PL]
Abstract: International audience; In this paper, we present a new algebraic model for music programming : tiled musical graphs. It is based on the idea that the definition of musical objects : what they are, and the synchronization of these objects : when they should be played, are two orthogonal aspects of music programming that should be kept separate although handled in a combined way. This leads to the definition of an algebra of music objects : tiled music graphs, which can be combined by a single operator : the tiled product, that is neither sequential nor parallel but both. From a mathematical point of view, this algebra is known to be especially robust since it is an inverse monoid. Various operators such as the reset and the coreset projections derive from these algebra and turned out to be fairly useful for music modeling. From a programming point of view, it provide a high level domain specific language (DSL) that is both hierarchical and modular. This language is currently under implementation in the functional programming language Haskell. From an applicative point of view, various music modeling examples are provided to show how notes, chords, melodies, musical meters and various kind of interpretation aspects can easily and robustly be encoded in this formalism.
Published: 2016

13. Vers une programmation réactive structurée

Author: Archipoff, Simon, Janin, David, 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: [MATH.MATH-LO]Mathematics [math]/Logic [math.LO], [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], [INFO.INFO-SD]Computer Science [cs]/Sound [cs.SD], [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM]
Abstract: National audience; Dans cet article, nous traitons de la programmation de systèmes musicaux interactifs lorsqu'ils sont soumis à des stimulations structurées telles que celles provenant d'un clavier maître. Un nouveau langage, dédié à la programmation musicale réactive, est proposé. Plus abstrait que les langages de programmation événementielle classiques, il reste cependant beaucoup plus simple d'utilisation. Mathématiquement bien structuré, il permet aussi une analyse automatique de la cohérence temporelle des programmes réactifs qu'on peut écrire.
Published: 2016

14. Outils d'écriture spatiale pour les partitions interactives

Author: Celerier, Jean-Michaël, Desainte-Catherine, Myriam, Couturier, Jean-Michel, 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), Blue Yeti [St Georges de Didonne], Projet ANR ANR-12-CORD-0024 Thèse CIFRE N° 1181/2014, 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: espace, [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM], i-score, partitions interactives, interactive scores
Abstract: National audience; L'écriture de partitions interactives évolue pour inclure du contenu spatial. En effet, dans de nombreuses pratiques de création, musicales ou scénographiques, un travail sur des paramètres à plusieurs dimensions apparaît nécessaire. Cela peut être dû à de la spatialisation du son ou à la nécessité de répondre à des contraintes physiques sur une scène. Il est possible de définir des sous-espaces utiles pour la définition de ces paramètres en tant que zones d'espace : les courbes de trajectoires paramétriques en sont un exemple. Nous présentons les modèles possibles pour l'écriture de contenu spatial. Un modèle mixte est choisi pour l'implémentation dans le séquenceur i-score. Il offre des moyens d'écriture très généraux ainsi que la possibilité de spécialiser et d'optimiser certains cas lorsque cela s'avère nécessaire. Cette implémentation comporte des outils d'édition, de visualisation, ainsi que deux possibles sémantiques d'exécution offrant une forte interopérabilité avec les scénarios interactifs.
Published: 2016

15. 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

16. 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

17. 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

18. 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

19. 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

20. Lambda-calculus and formal language theory

Author: Salvati, Sylvain, 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), Université de Bordeaux, Courcelle Bruno, 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: formal language theory, mathématiques du langage, mathematics of language, sémantique dénotationelle, Computer Science::Programming Languages, Lambda-calculus, lambda-calcul, [INFO]Computer Science [cs], vérification, model checking, théorie des langages formels, denotational semantics
Abstract: Formal and symbolic approaches have offered computer science many application fields. The rich and fruitful connection between logic, automata and algebra is one such approach. It has been used to model natural languages as well as in program verification. In the mathematics of language it is able to model phenomena ranging from syntax to phonology while in verification it gives model checking algorithms to a wide family of programs. This thesis extends this approach to simply typed lambda-calculus by providing a natural extension of recognizability to programs that are representable by simply typed terms. This notion is then applied to both the mathematics of language and program verification. In the case of the mathematics of language, it is used to generalize parsing algorithms and to propose high-level methods to describe languages. Concerning program verification, it is used to describe methods for verifying the behavioral properties of higher-order programs. In both cases, the link that is drawn between finite state methods and denotational semantics provide the means to mix powerful tools coming from the two worlds.
Published: 2015

21. A model for behavioural properties of higher-order programs

Author: Salvati, Sylvain, Walukiewicz, Igor, 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)-É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-PF]Computer Science [cs]/Performance [cs.PF], 000 Computer science, knowledge, general works, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS, Computer Science::Logic in Computer Science, Computer Science, Computer Science::Programming Languages, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], [INFO]Computer Science [cs]
Abstract: International audience; We consider simply typed lambda-calculus with fixpoints as a non-interpreted functional programming language: the result of the execution of a program is its normal form that can be seen as a potentially infinite tree of calls to built-in operations. Properties of such trees are properties of executions of programs and monadic second-order logic (MSOL) is well suited to express them. For a given MSOL property we show how to construct a finitary model recognizing it. In other words, the value of a lambda-term in the model determines if the tree that is the result of the execution of the term satisfies the property. The finiteness of the construction has as consequences many known results about the verification of higher-order programs in this framework.
Published: 2015
Full Text: View/download PDF

22. 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

23. Free inverse monoids up to rewriting

Author: Janin, David, 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), LaBRI - Laboratoire Bordelais de Recherche en Informatique, 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: [MATH.MATH-LO]Mathematics [math]/Logic [math.LO], [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Mathematics::Category Theory, [INFO.INFO-SD]Computer Science [cs]/Sound [cs.SD], [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM]
Abstract: In this paper, generalizing the study of free partially commutative inverse monoids [5], for any rewriting system T over an alphabet A, we define the notion of T-compatible inverse A-generated monoids, we show there is a free T-compatible monoid FIM(A,T) generated by A and we provide an explicit construction of this monoid. Then, as examples, free partially commutative inverse monoid and free partially semi-commutative inverse monoids are studied and shown to have effective representations.
Published: 2015

24. 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

25. A model for divergence insensitive properties of lambdaY-terms

Author: Salvati, Sylvain, Walukiewicz, Igor, 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: MSOL properties of Bohm trees, lambda Y-calculus, [INFO.INFO-IR]Computer Science [cs]/Information Retrieval [cs.IR], [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO]
Abstract: A term of a simply typed λ-calculus with fixpoints can be considered as an abstraction of a higher-order functional program. The result of the computation of a term is its Böhm tree. Given a tree automaton describing a property of Böhm trees, we are interested in constructing a model recognizing the property, in a sense that the value of a term determines if its Böhm tree satisfies the property. We show how to construct models recognizing properties expressed by parity automata that cannot detect divergence. We call them Ω-blind parity automata, as the symbol Ω is used in Böhm trees to represent divergence; an automaton is Ω-blind when it has to accept Ω from every state. The models we construct resemble standard Scott models of latices of monotone functions, but application needs to be modified and the the fixpoint operator should be interpreted as a particular non-extremal fixpoint in a lattice.
Published: 2015

26. 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

27. Des signaux aux symphonies : pour une modélisation homogène des objets sonores

Author: Janin, David, Desainte-Catherine, Myriam, 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: [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], [INFO.INFO-SD]Computer Science [cs]/Sound [cs.SD], [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM]
Abstract: International audience; Peut-on synchroniser, mixer, combiner des objets so-nores de natures diverses tels que des sons, des notes, des accords, des mélodies, tout en faisant abstraction de leur nature ? Il faut pour cela un modèle qui permet de décrire de façon uniforme les agencements temporels qu'on peut souhaiter obtenir en combinant ces objets. Du signal à la symphonie, les tuiles media temporisées polymorphes permettent cela.
Published: 2015

28. Exploiting Parallelism in FPGAs for the Real-Time Interpretation of Interactive Multimedia Scores

Author: Jaime Arias, Myriam Desainte-Catherine, Camilo Rueda, 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: [INFO.INFO-AR]Computer Science [cs]/Hardware Architecture [cs.AR], Interactive Scores, [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM], FPGA Implementation, [INFO.INFO-ES]Computer Science [cs]/Embedded Systems, Synchronous Programming, Real-Time System, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation
Abstract: International audience; Real-time performance is essential for interactive multi- media applications. However, most of these applications are sequential or they are executed on architectures and operat- ing systems that do not provide a low-latency real-time per- formance. In this paper, we present a solution to this prob- lem, specifically in the interpretation of interactive multime- dia scores. For that, we present a novel parallel implementa- tion of interactive scores on a reconfigurable hardware. We take advantage of the parallelism and reliability provided by Field Programmable Gate Arrays (FPGAS) to perform in real-time the hardware representation of scores. The results of the simulations show that our approach allows the system to react instantaneously to user interactions. Moreover, the real-time constraints of the score are satisfied.
Published: 2015

29. From out-of-time design to in-time production of temporal media

Author: Hudak, Paul, Janin, David, Department of Computer Science (YALE), Yale University [New Haven], 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), LaBRI - Laboratoire Bordelais de Recherche en Informatique, 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: [MATH.MATH-LO]Mathematics [math]/Logic [math.LO], [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], [INFO.INFO-SD]Computer Science [cs]/Sound [cs.SD], [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM]
Abstract: The design a temporal media, a sequence of temporal media values such as notes, sounds, images, etc., is an out-of-time task. Fairly general out-of-time program constructs are available for such a purpose. For example , when writing a musical piece, a composer can traverse back and forth his creation. On the contrary, rendering a temporal media is an in-time task. The production of notes in a musical performance is bound to be coherent with the unceasing onward flow of time. It follows that some of the out-of-time programming constructs used for the creation of that pieces must have been reordered in order to produce the right media events in the right order and at the right time. In this paper, we propose a formal study of the interplay between these in-time and these out-of-time programing constructs. With an explicitly out-of-time design approach, we eventually show that simpler and more abstract declarative programming features become available, leaving to computers the tedious task of synchronizing and scheduling the media events to be produced in-time, upon demand.
Published: 2015

30. 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

31. 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

32. 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

33. 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

34. 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

35. 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

36. 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

37. Multilabel Classification of Non-Verbal Communication of Emotions

Author: Pauline Mouawad, Myriam Desainte-Catherine, Jean-Luc ROUAS, Laboratoire Bordelais de Recherche en Informatique (LaBRI), 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, 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), 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, 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), 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 Rouas, Jean-Luc
Subjects: [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, [INFO.INFO-TS] Computer Science [cs]/Signal and Image Processing, ComputingMilieux_MISCELLANEOUS
Abstract: International audience; no abstract
Published: 2015

38. Schemographe: application for a new representation technique and methodology of analysis in tonal harmonyin tonal harmony. In: Evolutionary and Biologically Inspired Music, Sound, Art and Design

Author: SCHVETS, Anna, Desainte-Catherine, Myriam, University Marii Curie-Sklodowskiej [Lublin], 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), 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, Desainte-Catherine, Myriam, Uniwersytet Marii Curie-Sklodowskiej = University Marii Curie-Sklodowskiej [Lublin] (UMCS), 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), 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-SD]Computer Science [cs]/Sound [cs.SD], [INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC], [INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC], [INFO.INFO-SD] Computer Science [cs]/Sound [cs.SD], ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2015

39. 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

40. 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

41. 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

42. 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

43. 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

44. 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

45. 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

46. Executing Hierarchical Interactive Scores in ReactiveML

Author: Jaime Arias, Myriam Desainte-Catherine, Sylvain Salvati, Camilo Rueda, 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: Interactive Scores, Modelling and simulation, [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM], [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, Reactive Synchronous Programming
Abstract: National audience; Interactive scores proposes a model to write and execute interactive multimedia scores. The software i-score implements the above model using Hierarchical Time Stream Petri Nets (HTSPN). However, this model is very static and modelling new features would require a complete redesign of the network or sometimes they cannot be expressed. Another problem of i-score is that it does not provide a good visual feedback of the execution of the scenario. In this work, we define and implement an interpreter of interactive scores using the synchronous programming language ReactiveML. Our work takes advantage of the expressiveness of the reactive model and the power of functional programming to develop an interpreter more dynamic and simple. Contrary to the Petri Net model, our approach allows to model precisely the hierarchical behaviour, and permits the easy prototyping of new features. We also propose a visualization system using the environment INScore that provides a real-time visualization of the execution of the score.
Published: 2014

47. 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

48. 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

49. Programmer avec des tuiles musicales: le T-calcul en Euterpea

Author: Hudak, Paul, Janin, David, 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: [MATH.MATH-LO]Mathematics [math]/Logic [math.LO], [INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL], programmation fonctionnelle, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], tuilage, [MATH.MATH-OA]Mathematics [math]/Operator Algebras [math.OA], [INFO.INFO-SD]Computer Science [cs]/Sound [cs.SD], [INFO.INFO-MM]Computer Science [cs]/Multimedia [cs.MM], modélisation musicale, informatique musicale, monoïde inversif
Abstract: International audience; Euterpea est un langage de programmation dédié à la création et à la manipulation de contenus media temporisés - son, musique, animations, vidéo, etc... Il est enchassé dans un langage de programmation fonctionnelle avec typage polymorphe: Haskell. Il hérite ainsi de toute la souplesse et la robustesse d'un langage de programmation moderne. Le T-calcul est une proposition abstraite de modélisation temporelle qui, à travers une seule opération de composition: le produit tuilé, permet tout à la fois la composition séquentielle et la composition parallèle de contenus temporisés. En présentant ici une intégration du T-calcul dans le language Euterpea, nous réalisons un outil qui devrait permettre d'évaluer la puissance métaphorique du tuilage temporel combinée avec la puissance programmatique du langage Euterpea.
Published: 2014

50. 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

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

73 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