Publications 1994
T. Amagbegnon, L. Besnard, P. Le Guernic.
Arborescent Canonical Form of Boolean Expressions. Research report Inria, No2290, June 1994. (postscript)
Abstract : Signal is a synchronous language designed to program real-time systems. Because of its equational style, its compilation requires the statical resolution of a system of boolean equations ; the variables being clocks.This report discusses the arborescent representation of Signal clocks. We introduce a BDDs-based data structure called hierarchy. Through the factorization of boolean functions, we show that hierarchies are a canonical form of clocks. We also show that this canonical form optimizes the sequential code generated from a Signal program. We finally link hierarchies to the well known ordering problem of BDDs.
Keywords:
B. Dutertre, M. Le Borgne.
Control of Polynomial Dynamic Systems: an Example. Research report Inria, No2193, January 1994. (postscript)
Abstract : This paper presents the application of algebraic techniques to the control of a discrete event system. The system is described using Signal , a data-flow language. An equational model is then elaborated. Control objectives are expressed as invariance and reachability properties of the model. Control equations are synthesized using algebraic tools: ideals, varieties and principal generators.
Keywords: Discrete Event Systems, Control Polynomial Methods
M. Belhadj.
Conception d'architectures en utilisant Signal et VHDL. Phd thesis, Université de Rennes I, IFSIC, December 1994. (postscript)
Abstract : Ce document présente une approche pour la conception de circuits, se basant sur le langage flot de données synchrone SIGNAL et le langage de description de matériel VHDL. Deux aspects sont importants pour la conception d'architectures : la synthèse et la vérification formelle. La synthèse permet d'obtenir à partir d'une description abstraite une architecture matérielle par des transformations automatiques. La vérification formelle, quant à elle, permet d'établir qu'une abstraction et une mise en oeuvre sont conformes via-à-vis d'un certain critère. Une partie est consacrée à la synthèse de circuits à partir de SIGNAL, et ceci en s'appyant sur une traduction vers VHDL qui dispose de nombreux outils de synthèse. Une méthode pour la synthèse de circuits globalement asynchrones localement synchrones est définie. Ce type d'architecture permet d'allier les avantages des circuits synchrones et des circuits asynchrones. Dans la deuxième partie consacrée à la vérification formelle, une définition d'un sous-ensemble VHDL en SIGNAL est donnée en prélude à la vérification des programmes VHDL dans l'environnement SIGNAL. Un sous-ensemble synchrone de VHDL est utilisé pour la vérification formelle à l'aide de l'outil de preuve associé à SIGNAL.
Keywords:
A. Benveniste, B.C. Levy, E. Fabre, P. Le Guernic.
A calculus of stochastic systems for the specification, simulation, and hidden state estimation of hybrid stochastic/nonstochastic systems. Research report Irisa, No837, July 1994. (postscript)
Abstract : In this paper, we consider hybrid systems containing both stochastic and deterministic components. To compose such systems, we introduce a general combinator which allows the specification of an arbitrary hybrid system in terms of elementary components of only two types. Thus, systems are obtained hierarchically, by composing subsystems, where each subsystem can be viewed as an ``increment'' in the decomposition of the full system. The resulting hybrid stochastic system specifications are generally not ``executable'', since they do not necessarily permit the incremental simulation of the system variables. Such a simulation requires compiling the dependency relations existing between the system variables. Another issue involves finding the most likely internal states of a stochastic system from a set of observations. We provide a small set of primitives for transforming hybrid systems, which allows the solution of the two problems of incremental simulation and estimation of stochastic systems within a common framework. The complete model is called CSS ( a Calculus of Stochastic Systems), and is implemented by the Sig language, derived from the Signal synchronous language. Our results are applicable to pattern recognition problems formulated in terms of Markov random fields or hidden Markov models (HMMs), and to the automatic generation of diagnostic systems for industrial plants starting from their risk analysis.
Keywords:
E. Marchand, E. Rutten, F. Chaumette.
Applying the Synchronous Approach to Real Time Active Visual Reconstruction. Research report Inria, No2383, November 1994. (postscript)
Abstract : In this paper, we apply the synchronous approach to real time active visual reconstruction. It illustrates the adequateness of signal, a synchronous data flow programming language and environment, for the specification of a system dealing with various domains such as robot control, computer vision and programmation of hierarchical parallel automaton. More precisely, one application consists in the 3D structure estimation of a set of geometrical primitives using an active vision paradigm. At the level of camera motion control, the visual servoing approach (a closed loop with respect to vision data) is specified and implemented in \sc Signal as a function from sensor inputs to control outputs. Furthermore, the 3D reconstruction method is based on the ``structure from controlled motion'' approach (constraining camera motion for optimal estimation). Its specification is made in parallel to visual servoing, and involves the delay mechanism of \signal\ for the specification of filters. This reconstruction involves focusing on each object; we thus present a perception strategy for connecting up several estimations, using tasks hierarchies interruption and time intervals in \signal. The integration of these techniques is validated experimentally by their implementation on a robotic cell, from which we present experimental results.
Keywords: SYNCHRONOUS LANGUAGE,REAL-TIME,VISUAL SERVOING,STRUCTURE FROM CONTROLLED MOTION,PERCEPTION STRATEGY
T. Gautier, P. LeGuernic, O. Maffeis.
For a New Real-Time Methodology. Research report Inria, No2364, October 1994. (postscript)
Abstract : This paper motivates the use of a synchronous methodology to program, to verify and to implement real-time applications. The main features of the synchronous language \signal\ are presented and some methodological principles are proposed. \signal\ programming is illustrated through the development of a realistic application, a complex digital watch. Then, an overview of the software environment associated with \signal\ is presented. This environment encompasses formal verification as well as implementation tools to infer reliable real-time implementations on various architectures including distributed ones. All these tools are acting on a unique but polymorphic abstract program representation, namely Synchronous-Flow Dependence Graphs, which provides the \signal\ software design environment with a great homogeneity.
Keywords: REACTIVE AND REAL-TIME SYSTEMS,SYNCHRONOUS APPROACH OF TIME, THE SIGNAL LANGUAGE,SPECIFICATION/PROGRAMMING METHODOLOGY, SOFTWARE DESIGN ENVIRONMENT,SYNCHRONOUS-FLOW DEPENDENCE GRAPHS, COMPUTER-AIDED FORMAL VERIFICATION IMPLEMENTATION
H. Marchand, M. Le Borgne.
Typage des graphes de décisions ternaires. Research report Irisa, No797, March 1994. (postscript)
Abstract : Dans ce rapport, nous allons étudier le problème de la représentation des formes polynomiales sous forme de graphes de décisions ternaires typés : TDD typés. Après avoir présenté brièvement les travaux antérieurs sur les TDD (ternary decision diagram), nous allons montrer comment il est possible de typer ces TDD tout en s'attachant à conserver la canonicité de ceux ci. On proposera ensuite une étude comparative entre les deux modes de représentations. Cette étude permettra de montrer l'interêt du typage à l'aide de permutations pour les fonctions polynomiales de base. On verra par la suite différentes méthodes visant à améliorer la représentation en mémoire des TDD.
Keywords:
E. Rutten, P. Le Guernic.
Sequencing data flow tasks in SIGNAL. Proceedings of the ACM SIGPLAN Workshop on Language, Compiler and Tool Support for Real-Time Systems, Orlando, Florida (USA), June 1994. (postscript)
Abstract : Real-time applications involve the sequencing of different modes of continuous interaction with the environment. This suggests a hybrid language with data flow and sequencing constructs. To this purpose, we introduce the notion of time interval into the real-time declarative data flow language Signal, which is instant-based. Associating an execution interval with a data flow process specifies a task. Patterns for the sequencing of tasks using time intervals feature parallelism and preemption. They are described at the programming language level, as an extension to Signal.
Keywords:
E. Rutten, E. Marchand, F. Chaumette.
The sequencing of data flow tasks in Signal: application to active vision in robotics. Proceedings of the 6th Euromicro Workshop on Real Time Systems, IEEE Publ., pages 80-84, University of Maelardalen, Vasteraa s (Sweden), June 1994. (postscript)
Abstract : Many applications of real time systems feature a combination of ``continuous'' (possibly sampled) and discrete (sequencing and task control) behaviors, both reactive to the evolutions of the execution environment. In particular, robotics applications involve the programming of the control functions for each task, and the sequencing of such tasks at a higher level. In the framework of the real time synchronized data-flow language Signal, we propose extensions based on time intervals, enabling the specification of tasks, and of their suspension or abortion for their sequencing in reaction to discrete events. This paper illustrates the application of these constructs to active vision in robotics, where successive phases have to be sequenced, each associated with a particular control law, in order to recognize a complex environment.
Keywords:
The documents contained in these directories are included by the contributing
authors as a means to ensure timely dissemination of scholarly and technical
work on a non-commercial basis. Copyright and all rights therein are maintained
by the authors and by other copyright holders, notwithstanding that they have
offered their works here electronically. It is understood that all persons
copying this information will adhere to the terms and constraints invoked by
each author's copyright. These works may not be reposted without the explicit
permission of the copyright holder.
|
