Chattering is a fundamental phenomenon that is unique to hybrid systems, due to the complex interaction between discrete dynamics (in the form of discrete transitions) and continuous dynamics (in the form of time). In practice, simulating chattering hybrid systems is challenging in that simulation effectively halts near the chattering time point, as an infinite number of discrete transitions would need to be simulated. In this paper, formal conditions are provided for when the simulated models of hybrid systems display chattering behavior, and methods are proposed for avoiding chattering “on the fly” in runtime. We utilize dynamical behavior analysis to derive conditions for detecting chattering without enumeration of modes. We also present a new iterative algorithm to allow for solutions to be carried past the chattering point, and we show by a prototypical implementation how to generate the equivalent chattering-free dynamics internally by the simulator in the main simulation loop. The concepts are illustrated with examples throughout the paper. © 2016 IEEE.
Domain-Specific Languages (DSLs) play an important role in both practice and education. But developing them is challenging, because a DSL must ultimately satisfy a large and complex set of user/customer requirements to fulfil its intended role, and neither requirements nor users are fully available at all times during the development process. Requirements can be elicited using agile methods but such methods assume the availability of the users. The situation is further complicated when the user base is primarily students and when enhanced learning is a key requirement. In this paper we propose developing DSLs, especially educational ones, as online applications. We analyze how this can help requirement elicitation and learning. Being online brings language development closer to the user, yielding new opportunities to improve and accelerate the language design process. It is also well-matched to agile methods, since web- based analytics provide an abundant source of data that integrates naturally into the development process. As an example, we consider applying the method to Acumen, a DSL designed to support teaching Cyber-Physical Systems.
Functional*Reactive Programming (FRP) is a declarative approach to modeling and building reactive systems. Priority-based FRP (P-FRP) is a formalism of FRP that guarantees real-time response. Unlike the classical preemptive model1 of real-time systems, preempted tasks in PFRP are aborted and have to restart when higher priority tasks have completed. Due to this abort-restart of nature of preemption, there is no single critical instant of release that leads to Worst-Case Response Time (WCRT) of lower priority P-FRP tasks. At this time, the only method for determining the WCRT is through an exhaustive enumeration of all release offsets of higher priority tasks between the release and deadline of the lower priority task. This makes the computational cost of WCRT dependent on the deadline of a task, and when such deadlines are large the computational costs of this technique make it infeasible even for small task sets. In this paper, we show that the release offsets of higher priority tasks have a lower and upper bound and present techniques to derive these bounds. By enumerating only those release offsets while lie within our derived bounds the number of release scenarios that have to be enumerated is significantly reduced. This leads to lower computational costs and makes determination of the WCRT in P-FRP a practically feasible proposition. © 2011 IEEE.
Kaiabachev, Taha, Zhu [1] have presented a declarative programming paradigm called Functional Reactive Programming, which is based on behaviors and events. An improved system called P-FRP uses fixed priority scheduling for tasks. The system allows for the currently executing lower priority tasks to be rolled back to restoring the original state and allowing a higher priority task to run. These aborted tasks will restart again when no tasks of higher priority are in the queue. Since P-FRP has many applications in the real time domain it is critical to understand the time bound in which the tasks which have been aborted are guaranteed to run, and if the task set is schedulable. In this paper we provide an analysis of the unique execution paradigm of the P-FRP system and study the timing bounds using different constraint variables.
1. R. Kaiabachev, W. Taha, A. Zhu, E-FRP with priorities, In the Proceedings of the 7th ACM & IEEE international conference on Embedded software, Pages: 221 - 230, 2007.
Multi-stage programming is a method for improving the performance of programs through the introduction of controlled program specialization. This paper makes a case for multi-stage programming with open code and closed values. We argue that a simple language exploiting interactions between two logical modalities is well suited for multi-stage programming, and report the results from our study of categorical models for multi-stage languages.
An important and resource-intensive class of computation codes consists of simulators for physical systems. Today, most simulation codes are written in general-purpose imperative languages such as C or FORTRAN. Unfortunately, such languages encourage the programmer to focus her attention on details of how the computation is performed, rather than on the system being modeled.
This paper reports the design and implementation of a novel notion of an object for a physical modeling language called Acumen. A key idea underlying the language's design is encouraging a programming style that enables a "globally parallel, locally imperative" view of the world. The language is also being designed to preserve deterministic execution even when the underlying computation is performed on a highly parallel platform. Our main observation with the initial study is that extensive and continual experimental evaluation is crucial for keeping the language design process informed about bottlenecks for parallel execution.
Smart buildings promise to revolutionize the way we live. Applications ranging from climate control to fire management can have significant impact on the quality and cost of these services. However, a smart building and any technology with direct effect on the safety of its occupants must undergo extensive testing. Virtual testing by means of computer simulation can significantly reduce the cost of testing and, as a result, accelerate the development of novel applications. Unfortunately, building physically-accurate simulation codes can be labor intensive. To address this problem, we propose a framework for rapid, physically-accurate virtual testing of smart building systems. The proposed framework supports analytical modeling and simulation of both a discrete distributed system as well as the physical environment that hosts it. © 2012 Springer-Verlag Berlin Heidelberg.
Smart buildings promise to revolutionize the way we live. Applications ranging from climate control to fire management can have significant impact on the quality and cost of these services. However, smart buildings and any technology with direct effect on human safety and life mustundergo extensive testing. Virtual testing by means of computer simulation can significantly reduce the cost of testing and, as a result, accelerate the development of novel applications. Unfortunately, building physically-accurate simulation codes can be labor intensive.To address this problem, we propose a framework for rapid, physically-accurate virtual testing. The proposed framework supports analytical modeling of both a discrete distributed system as well as the physical environment that hosts it. The discrete models supported are accurate enough to allow the automatic generation of a dedicated programming framework that will help the developer in the implementation of these systems. The physical environment models supported are equational specifications that are accurate enough to produce running simulation codes. Combined, these two frameworks enable simulating both active systems and physical environments. These simulations can be used to monitor the behavior and gather statistics about the performance of an application in the context of precise virtual experiments. To illustrate the approach, we present models of Heating, Ventilating and Air-Conditioning (HVAC) systems. Using these models, we construct virtual experiments that illustrate how the approach can be used to optimize energy and cost of climate control for a building. © 2012 IEEE.
Smart buildings promise to revolutionize the way we live. Applications ranging from climate control to fire management can have significant impact on the quality and cost of these services. However, a smart building and any technology with direct effect on the safety of its occupants must undergo extensive testing. Virtual testing by means of computer simulation can significantly reduce the cost of testing and, as a result, accelerate the development of novel applications. Unfortunately, building physically-accurate simulation codes can be labor intensive. To address this problem, we propose a framework for rapid, physically-accurate virtual testing of smart building systems. The proposed framework supports analytical modeling and simulation of both a discrete distributed system as well as the physical environment that hosts it.
Industrial cyber-physical system products interleave hardware, software, and communication components. System complexity is increasing simultaneously with increased demands on quality and shortened time-to-market. To effectively support the development of such systems, we present languages and tools for comprehensive integrated model-based development that cover major phases such as requirement analysis, design, implementation, and maintenance. The model-based approach raises the level of abstraction and allows to perform virtual prototyping by simulating and optimizing system models before building physical products. Moreover, open standards and open source implementations enable model portability, tool reuse and a broader deployment. In this paper we present a general overview of the available solutions with focus on Modelica/OpenModelica, Bloqqi, and Acumen. The paper presents contributions to these languages and environments, including symbolic-numeric modeling, requirement verification, code generation, model debugging, design optimization, graphical modeling, and variant handling with traceability, as well a general discussion and conclusions. © 2021 by the authors. Licensee MDPI, Basel, Switzerland
Safely adding computational effects to a multi-stage language has been an open problem. In previous work, a closed type constructor was used to provide a safe mechanism for executing dynamically generated code. This paper proposes a general notion of closed type as a simple approach to safely introducing computational effects into multi-stage languages. We demonstrate this approach formally in a core language called Mini-MLref BN. This core language combines safely multi-stage constructs and ML-style references. In addition to incorporating state, Mini-ML ref BN also embodies a number of technical improvements over previously proposed core languages for multi-stage programming.
Environment classifiers were proposed as a new approach to typing multi-stage languages. Safety was established in the simply-typed and let-polymorphic settings. While the motivation for classifiers was the feasibility of inference, this was in fact not established. This paper starts with the observation that inference for the full classifier-based system fails. We then identify a subset of the original system for which inference is possible. This subset, which uses implicit classifiers, retains significant expressivity (e.g. it can embed the calculi of Davies and Pfenning) and eliminates the need for classifier names in terms. Implicit classifiers were implemented in MetaOCaml, and no changes were needed to make an existing test suite acceptable by the new type checker. © Springer-Verlag 2004.
The paper addresses theoretical and practical aspects of implementing multi-stage languages using abstract syntax trees (ASTs), gensym, and reflection. We present an operational account of the correctness of this approach, and report on our experience with a bytecode compiler called MetaOCaml that is based on this strategy. Current performance measurements reveal interesting characteristics of the underlying OCaml compiler, and illustrate why this strategy can be particularly useful for implementing domain-specific languages in a typed, functional setting. © Springer-Verlag Berlin Heidelberg 2003.
This book constitutes the proceedings of the 8th International Workshop on Design, Modeling, and Evaluation of Cyber Physical Systems, CyPhy 2018 and 14th International Workshop on Embedded and Cyber-Physical Systems Education, WESE 2018, held in conjunction with ESWeek 2018, in Torino, Italy, in October 2018. The 13 full papers presented together with 1 short paper in this volume were carefully reviewed and selected from 18 submissions. The conference presents a wide range of domains including Modeling, simulation, verification, design, cyber-physical systems, embedded systems, real-time systems, safety, and reliability. © 2019 Springer Nature Switzerland AG. Part of Springer Nature.
Previous work on semantics-based multi-state programming language design focused on homogeneous and heterogeneous software designs. In homogenous software design, the source and the target software programming languages are the same. In heterogeneous software design, they are different software languages. This paper proposes a practical means to circuit design by providing specialized offshoring translations from subsets of the source software programming language to subsets of the target hardware description language (HDL). This approach avoids manually writing codes for specifying the circuit of the given algorithm. To illustrate the proposed approach, we design and implement a translation to a subset of Verilog suitable numerical and logical computation. Through the translator, programmers can specify abstract algorithms in high level languages and automatically convert them into circuit descriptions in low level languages.© 2010 Binary Information Press.
Hardware description languages use a low level of abstraction making the task of hardware designers error-prone and time consuming. The resulting descriptions tend to be lengthy and hard to reason about. This paper presents a minimal functional language for describing hardware circuits. Using multistage programming concepts, Fast Fourier Transform circuit descriptions can be generated in this language from a higher level generic description. It bridges the gap between the generated code and the required low-level hardware description by presenting the translator to automatically convert the generated code into Verilog, a streamline hardware description language.
A wide range of domain-specific languages (DSLs) has been implemented successfully by embedding them in general purpose languages. This paper reviews embedding, and summarizes how two alternative techniques - staged interpreters and templates - can be used to overcome the limitations of embedding. Both techniques involve a form of generative programming. The paper reviews and compares three programming languages that have special support for generative programming. Two of these languages (MetaOCaml and Template Haskell) are research languages, while the third (C++) is already in wide industrial use. The paper identifies several dimensions that can serve as a basis for comparing generative languages.
Presents the introductory welcome message from the conference proceedings. May include the conference officers' congratulations to all involved with the conference event and publication of the proceedings record.© 2014 IEEE
The development of Cyber-Physical Systems benefits from better methods and tools to support the simulation and verification of hybrid (continuous/discrete) models. Acumen is an open source testbed for exploring the design space of what rigorous-but-practical next-generation tools can deliver to developers. Central to Acumen is the notion of rigorous simulation. Like verification tools, rigorous simulation is intended to provide guarantees about the behavior of the system. Like traditional simulation tools, it is intended to be intuitive, practical, and scalable. Whether these two goals can be achieved simultaneously is an important, long-term challenge.
This paper proposes a design principle that can play an important role in meeting this challenge. The principle addresses the criticism that accumulating numerical errors is a serious impediment to practical rigorous simulation. It is inspired by a twofold insight: one relating to the nature of systems engineered in the real world, and the other relating to how numerical errors in the simulation of a model can be recast as errors in the state or parameters of the model in the simulation. We present a suite of small, concrete benchmarks that can be used to assess the extent to which a rigorous simulator upholds the proposed principle. We also report on which benchmarks Acumen's current rigorous simulator already succeeds and which ones remain challenging.
Rigorous simulation is a new technology that can play a key role in managing uncertainty in the design of safety-critical cyber-physical systems. One of its important applications is the analysis and evaluation of functional safety for road vehicles according to international standards such as ISO 26262. Previous work presented preliminary evidence to support the feasibility of using rigorous simulation for this purpose. Here we report on advances in our implementation of rigorous simulation and show how they enable the rigorous simulation of more refined and more complete models. A larger case study highlights the benefits of these advances and helps us identify new challenges that should be addressed by future work. © 2015 IEEE.
Hybrid systems are a powerful formalism for modeling cyber-physical systems. Reachability analysis is a general method for checking safety properties, especially in the presence of uncertainty and non-determinism. Rigorous simulation is a convenient tool for reachability analysis of hybrid systems. However, to serve as proof tool, a rigorous simulator must be correct w.r.t. a clearly defined notion of reachability, which captures what is intuitively reachable in finite time. As a step towards addressing this challenge, this paper presents a rigorous simulator in the form of an operational semantics and a specification in the form of a denotational semantics. We show that, under certain conditions about the representation of enclosures, the rigorous simulator is correct. We also show that finding a representation satisfying these assumptions is non-trivial. © 2018, Springer International Publishing AG, part of Springer Nature.
We propose an arithmetic of function intervals as a basis for convenient rigorous numerical computation. Function intervals can be used as mathematical objects in their own right or as enclosures of functions over the reals. We present two areas of application of function interval arithmetic and associated software that implements the arithmetic: (1) Validated ordinary differential equation solving using the AERN library and within the Acumen hybrid system modeling tool. (2) Numerical theorem proving using the PolyPaver prover. © 2014 Springer-Verlag.
Previous work on semantics-based multi-stage programming(MSP) language design focused on homogeneous designs, where the generating and the generated languages are the same. Homogeneous designssimply add a hygienic quasi-quotation and evaluation mechanism to abase language. An apparent disadvantage of this approach is that theprogrammer is bound to both the expressivity and performance characteristics of the base language. This paper proposes a practical means toavoid this by providing specialized translations from subsets of the baselanguage to different target languages. This approach preserves the homogeneous “look” of multi-stage programs, and, more importantly, thestatic guarantees about the generated code. In addition, compared to anexplicitly heterogeneous approach, it promotes reuse of generator sourcecode and systematic exploration of the performance characteristics of thetarget languages.To illustrate the proposed approach, we design and implement a translation to a subset of C suitable for numerical computation, and show thatit preserves static typing. The translation is implemented, and evaluatedwith several benchmarks. The implementation is available in the onlinedistribution of MetaOCaml.
Previous work on semantics-based multi-stage programming (MSP) language design focused on homogeneous designs, where the generating and the generated languages are the same. Homogeneous designs simply add a hygienic quasi-quotation and evaluation mechanism to a base language. An apparent disadvantage of this approach is that the programmer is bound to both the expressivity and performance characteristics of the base language. This paper proposes a practical means to avoid this by providing specialized translations from subsets of the base language to different target languages. This approach preserves the homogeneous “look” of multi-stage programs, and, more importantly, the static guarantees about the generated code. In addition, compared to an explicitly heterogeneous approach, it promotes reuse of generator source code and systematic exploration of the performance characteristics of the target languages.
To illustrate the proposed approach, we design and implement a translation to a subset of C suitable for numerical computation, and show that it preserves static typing. The translation is implemented, and evaluated with several benchmarks. The implementation is available in the online distribution of MetaOCaml.
Visual notations are pervasive in circuit design, control systems, and increasingly in mainstream programming environments. Yet many of the foundational advances in programming language theory are taking place in the context of textual notations. In order to map such advances to the graphical world, and to take the concerns of the graphical world into account when working with textual formalisms, there is a need for rigorous connections between textual and graphical expressions of computation. To this end, this paper presents a graphical calculus called Uccello. Our key insight is that Ariola and Blom's work on sharing in the cyclic lambda calculus provides an excellent foundation for formalizing the semantics of graphical languages. As an example of what can be done with this foundation, we use it to extend a graphical language with staging constructs. In doing so, we provide the first formal account of sharing in a multi-stage calculus. Copyright © 2007 ACM.
Almost twenty years after the pioneering efforts of Cardelli, the programming languages community is vigorously pursuing ways to incorporate Fω-style indexed types into programming languages. This paper advocates Concoqtion, a practical approach to adding such highly expressive types to full-fledged programming languages. The approach is applied to MetaOCaml using the Coq proof checker to conservatively extend Hindley-Milner type inference. The implementation of MetaOCaml Concoqtion requires minimal modifications to the syntax, the type checker, and the compiler; and yields a language comparable in notation to the leading proposals. The resulting language provides unlimited expressiveness in the type system while maintaining decidability. Furthermore, programmers can take advantage of a wide range of libraries not only for the programming language but also for the indexed types. Programming in MetaOCaml Concoqtion is illustrated with small examples and a case study implementing a statically-typed domain-specific language.
With few exceptions, macros have traditionally been viewed as operations on syntax trees or even on plain strings. This view makes macros seem ad hoc, and is at odds with two desirable features of contemporary typed functional languages: static typing and static scoping. At a deeper level, there is a need for a simple, usable semantics for macros. This paper argues that these problems can be addressed by formally viewing macros as multi-stage computations. This view eliminates the need for freshness conditions and tests on variable names, and provides a compositional interpretation that can serve as a basis for designing a sound type system for languages supporting macros, or even for compilation. To illustrate our approach, we develop and present MacroML, an extension of ML that supports inlining, recursive macros, and the definition of new binding constructs. The latter is subtle, and is the most novel addition in a statically typed setting. The semantics of a core subset of MacroML is given by an interpretation into MetaML, a statically-typed multi-stage programming language. It is then easy to show that MacroML is stage- and type-safe: macro expansion does not depend on runtime evaluation, and both stages do not "go wrong.
Modern hardware description languages support code-generation constructs like generate/endgenerate in Verilog. These constructs are intended to describe regular or parameterized hardware designs and, when used effectively, can make hardware descriptions shorter, more understandable, and more reusable. In practice, however, designers avoid these constructs because it is difficult to understand and predict the properties of the generated code. Is the generated code even type safe? Is it synthesizable? What physical resources (e.g. combinatorial gates and flip-flops) does it require? It is often impossible to answer these questions without first generating the fully-expanded code. In the Verilog and VHDL communities, this generation process is referred to as elaboration.
This paper proposes a disciplined approach to elaboration in Verilog. By viewing Verilog as a statically typed two-level language, we are able to reflect the distinction between values that are known at elaboration time and values that are part of the circuit computation. This distinction is crucial for determining whether abstractions such as iteration and module parameters are used in a synthesizable manner. To illustrate this idea, we develop a core calculus for Verilog that we call Featherweight Verilog (FV) and an associated static type system. We formally define a preprocessing step analogous to the elaboration phase of Verilog, and the kinds of errors that can occur during this phase. Finally, we show that a well-typed design cannot cause preprocessing errors, and that the result of its expansion is always a synthesizable circuit.
Modern hardware description languages support code generation constructs like generate/endgenerate in Verilog. These constructs are used to describe regular or parameterized hardware designsand, when used effectively, can make hardware descriptions shorter, moreunderstandable, and more reusable. In practice, however, designers avoidthese abstractions because it is difficult to understand and predict theproperties of the generated code. Is the generated code even type safe?Is it synthesizable? What physical resources (e.g. combinatorial gatesand flip-flops) does it require? It is often impossible to answer thesequestions without first generating the fully-expanded code. In the Verilog and VHDL communities, this generation process is referred to as elaboration.This paper proposes a disciplined approach to elaboration in Verilog.∗1 By viewing Verilog as a statically typed two-level language, we are able to reflect the distinction between values that are known at elaborationtime and values that are part of the circuit computation. This distinctionis crucial for determining whether generative constructs, such as iterationand module parameters, are used in a synthesizable manner. This allowsus to develop a static type system that guarantees synthesizability. Thetype system achieves safety by performing additional checking on generative constructs and array indices. To illustrate this approach, we developa core calculus for Verilog that we call Featherweight Verilog (FV) andan associated static type system. We formally define a preprocessing stepanalogous to the elaboration phase of Verilog, and the kinds of errors thatcan occur during this phase. Finally, we show that a well-typed designcannot cause preprocessing errors, and that the result of its elaborationis always a synthesizable circuit.
We settle three basic questions that naturally arise when verifying code generators written in multi-stage functional programming languages. First, does adding staging to a language compromise any equalities that hold in the base language? Unfortunately it does, and more care is needed to reason about terms with free variables. Second, staging annotations, as the name "annotations" suggests, are often thought to be orthogonal to the behavior of a program, but when is this formally guaranteed to be true? We give termination conditions that characterize when this guarantee holds. Finally, do multi-stage languages satisfy useful, standard extensional properties, for example, that functions agreeing on all arguments are equivalent? We provide a sound and complete notion of applicative bisimulation, which establishes such properties or, in principle, any valid program equivalence. These results yield important insights into staging and allow us to prove the correctness of quite complicated multi-stage programs. © Cambridge University Press 2016.
We settle three basic questions that naturally arise when verifying multi-stage functional programs. Firstly, does adding staging to a language compromise any equalities that hold in the base language? Unfortunately it does, and more care is needed to reason about terms with free variables. Secondly, staging annotations, as the name “annotations” suggests, are often thought to be orthogonal to the behavior of a program, but when is this formally guaranteed to be true? We give termination conditions that characterize when this guarantee holds. Finally, do multi-stage languages satisfy useful, standard extensional facts—for example, that functions agreeing on all arguments are equivalent? We provide a sound and complete notion of applicative bisimulation, which establishes such facts or, in principle, any valid program equivalence. These results greatly improve our understanding of staging, and allow us to prove the correctness of quite complicated multi-stage programs. © 2012 Springer-Verlag.
E-FRP is declarative language for programming resourcebounded,event-driven systems. The original high-level semanticsof E-FRP requires that each event handler executeatomically. This requirement facilitates reasoning about EFRPprograms, and therefore it is a desirable feature of thelanguage. But the original compilation strategy requiresthat each handler complete execution before another eventcan occur. This implementation choice treats all eventsequally, in that it forces the upper bound on the time neededto respond to any event to be the same. While this is acceptablefor many applications, it is often the case that someevents are more urgent than others.In this paper, we show that we can improve the compilationstrategy without altering the high-level semantics.With this new compilation strategy, we give the programmermore control over responsiveness without taking awaythe ability to reason about programs at a high level. Theprogrammer controls responsiveness by declaring prioritiesfor events, and the compilation strategy produces code thatuses preemption to enforce these priorities. We show thatthe compilation strategy enjoys the same properties as theoriginal strategy, with the only change being that the programmerreasons modulo permutations on the order of eventarrivals.
High-level programming languages offer significant expressivity but provide little or no guarantees about resource use. Resource-bounded languages --- such as hardware-description languages --- provide strong guarantees about the runtime behavior of computations but often lack mechanisms that allow programmers to write more structured, modular, and reusable programs. To overcome this basic tension in language design, recent work advocated the use of Resource-aware Programming (RAP) languages, which take into account the natural distinction between the development platform and the deployment platform for resource-constrained software.This paper investigates the use of RAP languages for the generation of combinatorial circuits. The key challenge that we encounter is that the RAP approach does not safely admit a mechanism to express a posteriori (post-generation) optimizations. The paper proposes and studies the use of abstract interpretation to overcome this problem. The approach is illustrated using an in-depth analysis of the Fast Fourier Transform (FFT). The generated computations are comparable to those generated by FFTW.
Recent work showed that staging and abstract interpretation can be used to derive correct families of combinatorial circuits, and illustrated this technique with an in-depth analysis of the Fast Fourier Transform (FFT) for sizes 2n. While the quality of the generated code was promising, it used more floating-point operations than the well-known FFTW codelets and split-radix algorithm. This paper shows that staging and abstract interpretation can in fact be used to produce circuits with the same number of floating-point operations as each of split-radix and FFTW. In addition, choosing between two standard implementations of complex multiplication produces results that match each of the two algorithms. Thus, we provide a constructive method for deriving the two distinct algorithms. © Springer-Verlag Berlin Heidelberg 2005.
Even simple hybrid automata like the classic bouncing ball can exhibit Zeno behavior. The existence of this type of behavior has so far forced a large class of simulators to either ignore some events or risk looping indefinitely. This in turn forces modelers to either insert ad-hoc restrictions to circumvent Zeno behavior or to abandon hybrid automata. To address this problem, we take a fresh look at event detection and localization. A key insight that emerges from this investigation is that an enclosure for a given time interval can be valid independent of the occurrence of a given event. Such an event can then even occur an unbounded number of times. This insight makes it possible to handle some types of Zeno behavior. If the post-Zeno state is defined explicitly in the given model of the hybrid automaton, the computed enclosure covers the corresponding trajectory that starts from the Zeno point through a restarted evolution. ©2015 The Authors. Published by Elsevier Ltd.
Even simple hybrid systems like the classic bouncing ball can exhibit Zeno behaviors. The existence of this type ofbehavior has so far forced simulators to either ignore some events or risk looping indefinitely. This in turn forces modelers to either insert ad hoc restrictions to circumvent Zeno behavior or to abandon hybrid modeling. To address this problem, we take a fresh look at event detection and localization. A key insight that emerges from this investigation is that an enclosure for a given time interval can be valid independently of the occurrence of agiven event. Such an event can then even occur an unbounded number of times, thus making it possible to handle certain types of Zeno behavior. © 2013 IEEE.
Advances in Intelligent Transport Systems (ITS), intelligent vehicles and cooperative systems are enabling traffic and transport solutions that are both safer and more environmentally acceptable. While it is well known that high dependability is a desirable feature it has a price, and the level of dependability needed varies from application to application. Typical examples are cooperative safety applications, in particular traffic situation aware vehicle driver warning and assisting systems, enabled by vehicle-to-vehicle and vehicle-to-infrastructure wireless communication in combination with the use of geographical map information, Differential Global Positioning System (DGPS) and vehicle-carried sensors. This kind of applications depend on the reception of satellite data (combined with on-board sensor data from, e.g. odometer and accelerometer) for positioning of the own vehicle and on periodic broadcasting of this information to all neighbors in range. Both the wireless communication with satellites and the one between vehicles can have severe difficulties, for example due to hills or high buildings directly hindering both kinds of radio transmission. There are techniques to make the solutions more robust, e.g. by information fusion for temporary or local communication outage compensation. However, further development is needed and since coverage problems can be made known in advance and related to geographical areas, such information can also be explored.
The proceedings contain 14 papers. The special focus in this conference is on Practical Aspects of Declarative Languages. The topics include: Eliminating irrelevant non determinism in functional logic programs; canonicalizing high-level constructs in picat; integrating answer set programming with object-oriented languages; extending answer set programs with interpreted functions as first-class citizens; lowering the learning curve for declarative programming; overlapping patterns for property-based testing; Boltzmann samplers for closed simply-typed lambda terms; selection equilibria of higher-order games; principles and prototype implementation; declarative programming of full-fledged musical applications; a domain-specific language for software-defined radio; a declarative DSL for customizing ASCII art and using iterative deepening for probabilistic logic inference. © Copyright 2017 Elsevier B.V., All rights reserved
Intelligent Transportation Systems (ITS) are an excellent illustration of the types of challenges that future technologists must address. In previous work we presented a course designed to engage students with theoretical aspects of embedded and cyber-physical systems. In this paper we present MicroITS, a platform addressing applied aspects. We articulate the design goals that we believe are needed to achieve engagement in an educational setting, and describe the platform and its baseline functionality. We briefly describe example projects that can be realized using MicroITS. Our hope is that this report will encourage the development of a community of educators and students interested in the use and the continued development of the platform. © Springer Nature Switzerland AG 2019.
Simulation traditionally computes individual trajectories, which severely limits the assessment of overall system behaviour. To address this fundamental shortcoming, we rely on computing enclosures to determine bounds on system behaviour instead of individual traces. In the present case study, we investigate the enclosures of a generic Automatic Emergency Braking (AEB) system and demonstrate how this creates a direct link between requirement specification and standardized safety criteria as put forward by ISO 26262. The case study strongly supports that a methodology based on enclosures can provide a missing link across the engineering process, from design to compliance testing. This result is highly relevant for ongoing efforts to virtualize testing and create a unified tool-chain for the development of next generation Advanced Driver Assistance Systems. © 2014, FISITA. All rights reserved.
Hybrid systems—more precisely, their mathematical models—can exhibit behaviors, like Zeno behaviors, that are absent in purely discrete or purely continuous systems. First, we observe that, in this context, the usual definition of reachability—namely, the reflexive and transitive closure of a transition relation—can be unsafe, i.e., it may compute a proper subset of the set of states reachable in finite time from a set of initial states. Therefore, we propose safe reachability, which always computes a superset of the set of reachable states. Second, in safety analysis of hybrid and continuous systems, it is important to ensure that a reachability analysis is also robust w.r.t. small perturbations to the set of initial states and to the system itself, since discrepancies between a system and its mathematical models are unavoidable. We show that, under certain conditions, the best Scott continuous approximation of an analysis A is also its best robust approximation. Finally, we exemplify the gap between the set of reachable states and the supersets computed by safe reachability and its best robust approximation. © 2018 The Authors
Software is increasingly embedded in a variety of physical contexts. This imposes new requirements on tools that support the design and analysis of systems. For instance, modeling embedded and cyberphysical systems needs to blend discrete mathematics, which is suitable for modeling digital components, with continuous mathematics, used for modeling physical components. This blending of continuous and discrete creates challenges that are absent when the discrete or the continuous setting are considered in isolation. We consider robustness, that is, the ability of an analysis of a model to cope with small amounts of imprecision in the model. Formally, we identify analyses with monotonic maps between complete lattices (a mathematical framework used for abstract interpretation and static analysis) and define robustness for monotonic maps between complete lattices of closed subsets of a metric space. Copyright © 2019 for this paper by its authors.
Safety analysis of high confidence systems requires guaranteed bounds on the probabilities of events of interest. Establishing the correctness of algorithms that aim to compute such bounds is challenging. We address this problem in three steps. First, we use monadic transition systems (MTS) in the category of sets as a framework for modeling discrete time systems. MTS can capture different types of system behaviors, but we focus on a combination of non-deterministic and probabilistic behaviors that often arises when modeling complex systems. Second, we use the category of posets and monotonic maps as a setting to define and compare approximations. In particular, for the MTS of interest, we consider approximations of their configurations based on complete lattices. Third, by restricting to finite lattices, we obtain algorithms that compute over-approximations, i.e., bounds from above within some partial order of approximants, of the system configuration after n steps. Interestingly, finite lattices of “interval probabilities” may fail to accurately approximate configurations that are both non-deterministic and probabilistic, even for deterministic (and continuous) system dynamics. However, better choices of finite lattices are available. © 2020 University of Szeged, Institute of Informatics. All rights reserved.
Software is increasingly embedded in a variety of physical contexts. This imposes new requirements on tools that support the design and analysis of systems. For instance, modeling embedded and cyber-physical systems needs to blend discrete mathematics, which is suitable for modeling digital components, with continuous mathematics, used for modeling physical components. This blending of continuous and discrete creates challenges that are absent when the discrete or the continuous setting are considered in isolation. We consider robustness, that is, the ability of an analysis of a model to cope with small amounts of imprecision in the model. Formally, we identify analyses with monotonic maps between complete lattices (a mathematical framework used for abstract interpretation and static analysis) and define robustness for monotonic maps between complete lattices of closed subsets of a metric space. © Springer Nature Switzerland AG 2019
MetaML is a multi-stage functional programming language featuring three constructs that can be viewed as statically-typed refinements of the back-quote, comma, and eval of Scheme. Thus it provides special support for writing code generators and serves as a semanticallysound basis for systems involving multiple interdependent computational stages. In previous work, we reported on an implementation of MetaML, and on a reduction semantics and type-system for MetaML. In this paper, we present An Idealized MetaML (AIM) that is the result of our study of a categorical model for MetaML. An important outstanding problem is finding a type system that provides the user with a means for manipulating both open and closed code. This problem has eluded efforts by us and other researchers for over three years. AIM solves the issue by providing two type constructors, one classifies closed code and the other open code, and exploiting the way they interact. We point out that AIM can be verbose, and outline a possible remedy relating to the strictness of the closed code type. © Springer International Publishing AG, Part of Springer Science+Business Media 1999
For systematic and automatic testing of cyber-physical systems, in which a set of test cases is generated based on a formal specification, a number of notions of conformance testing have been proposed. In this paper, we review two existing theories of conformance testing for cyber-physical systems and compare them. We point out their fundamental differences, and prove under which assumptions they coincide. © Automated Verification of Critical Systems 2014.