-
A Declarative Specification for Authoring Metrics Dashboards
Authors:
Will Epperson,
Kanit Wongsuphasawat,
Allison Whilden,
Fan Du,
Justin Talbot
Abstract:
Despite their ubiquity, authoring dashboards for metrics reporting in modern data analysis tools remains a manual, time-consuming process. Rather than focusing on interesting combinations of their data, users have to spend time creating each chart in a dashboard one by one. This makes dashboard creation slow and tedious. We conducted a review of production metrics dashboards and found that many da…
▽ More
Despite their ubiquity, authoring dashboards for metrics reporting in modern data analysis tools remains a manual, time-consuming process. Rather than focusing on interesting combinations of their data, users have to spend time creating each chart in a dashboard one by one. This makes dashboard creation slow and tedious. We conducted a review of production metrics dashboards and found that many dashboards contain a common structure: breaking down one or more metrics by different dimensions. In response, we developed a high-level specification for describing dashboards as sections of metrics repeated across the same dimensions and a graphical interface, Quick Dashboard, for authoring dashboards based on this specification. We present several usage examples that demonstrate the flexibility of this specification to create various kinds of dashboards and support a data-first approach to dashboard authoring.
△ Less
Submitted 23 September, 2023;
originally announced September 2023.
-
Weighted Automata and Expressions over Pre-Rational Monoids
Authors:
Nicolas Baudru,
Louis-Marie Dando,
Nathan Lhote,
Benjamin Monmege,
Pierre-Alain Reynier,
Jean-Marc Talbot
Abstract:
The Kleene theorem establishes a fundamental link between automata and expressions over the free monoid. Numerous generalisations of this result exist in the literature. Lifting this result to a weighted setting has been widely studied. Moreover, different monoids can be considered: for instance, two-way automata, and even tree-walking automata, can be described by expressions using the free inver…
▽ More
The Kleene theorem establishes a fundamental link between automata and expressions over the free monoid. Numerous generalisations of this result exist in the literature. Lifting this result to a weighted setting has been widely studied. Moreover, different monoids can be considered: for instance, two-way automata, and even tree-walking automata, can be described by expressions using the free inverse monoid. In the present work, we aim at combining both research directions and consider weighted extensions of automata and expressions over a class of monoids that we call pre-rational, generalising both the free inverse monoid and graded monoids. The presence of idempotent elements in these pre-rational monoids leads in the weighted setting to consider infinite sums. To handle such sums, we will have to restrict ourselves to rationally additive semirings. Our main result is thus a generalisation of the Kleene theorem for pre-rational monoids and rationally additive semirings. As a corollary, we obtain a class of expressions equivalent to weighted two-way automata, as well as one for tree-walking automata.
△ Less
Submitted 24 October, 2021;
originally announced October 2021.
-
On Infusing Reachability-Based Safety Assurance within Planning Frameworks for Human-Robot Vehicle Interactions
Authors:
Karen Leung,
Edward Schmerling,
Mengxuan Zhang,
Mo Chen,
John Talbot,
J. Christian Gerdes,
Marco Pavone
Abstract:
Action anticipation, intent prediction, and proactive behavior are all desirable characteristics for autonomous driving policies in interactive scenarios. Paramount, however, is ensuring safety on the road -- a key challenge in doing so is accounting for uncertainty in human driver actions without unduly impacting planner performance. This paper introduces a minimally-interventional safety control…
▽ More
Action anticipation, intent prediction, and proactive behavior are all desirable characteristics for autonomous driving policies in interactive scenarios. Paramount, however, is ensuring safety on the road -- a key challenge in doing so is accounting for uncertainty in human driver actions without unduly impacting planner performance. This paper introduces a minimally-interventional safety controller operating within an autonomous vehicle control stack with the role of ensuring collision-free interaction with an externally controlled (e.g., human-driven) counterpart while respecting static obstacles such as a road boundary wall. We leverage reachability analysis to construct a real-time (100Hz) controller that serves the dual role of (i) tracking an input trajectory from a higher-level planning algorithm using model predictive control, and (ii) assuring safety by maintaining the availability of a collision-free escape maneuver as a persistent constraint regardless of whatever future actions the other car takes. A full-scale steer-by-wire platform is used to conduct traffic weaving experiments wherein two cars, initially side-by-side, must swap lanes in a limited amount of time and distance, emulating cars merging onto/off of a highway. We demonstrate that, with our control stack, the autonomous vehicle is able to avoid collision even when the other car defies the planner's expectations and takes dangerous actions, either carelessly or with the intent to collide, and otherwise deviates minimally from the planned trajectory to the extent required to maintain safety.
△ Less
Submitted 6 December, 2020;
originally announced December 2020.
-
A Security Perspective on Unikernels
Authors:
Joshua Talbot,
Przemek Pikula,
Craig Sweetmore,
Samuel Rowe,
Hanan Hindy,
Christos Tachtatzis,
Robert Atkinson,
Xavier Bellekens
Abstract:
Cloud-based infrastructures have grown in popularity over the last decade leveraging virtualisation, server, storage, compute power and network components to develop flexible applications. The requirements for instantaneous deployment and reduced costs have led the shift from virtual machine deployment to containerisation, increasing the overall flexibility of applications and increasing performan…
▽ More
Cloud-based infrastructures have grown in popularity over the last decade leveraging virtualisation, server, storage, compute power and network components to develop flexible applications. The requirements for instantaneous deployment and reduced costs have led the shift from virtual machine deployment to containerisation, increasing the overall flexibility of applications and increasing performances. However, containers require a fully fleshed operating system to execute, increasing the attack surface of an application. Unikernels, on the other hand, provide a lightweight memory footprint, ease of application packaging and reduced start-up times. Moreover, Unikernels reduce the attack surface due to the self-contained environment only enabling low-level features. In this work, we provide an exhaustive description of the unikernel ecosystem; we demonstrate unikernel vulnerabilities and further discuss the security implications of Unikernel-enabled environments through different use-cases.
△ Less
Submitted 14 November, 2019;
originally announced November 2019.
-
On Infusing Reachability-Based Safety Assurance within Probabilistic Planning Frameworks for Human-Robot Vehicle Interactions
Authors:
Karen Leung,
Edward Schmerling,
Mo Chen,
John Talbot,
J. Christian Gerdes,
Marco Pavone
Abstract:
Action anticipation, intent prediction, and proactive behavior are all desirable characteristics for autonomous driving policies in interactive scenarios. Paramount, however, is ensuring safety on the road --- a key challenge in doing so is accounting for uncertainty in human driver actions without unduly impacting planner performance. This paper introduces a minimally-interventional safety contro…
▽ More
Action anticipation, intent prediction, and proactive behavior are all desirable characteristics for autonomous driving policies in interactive scenarios. Paramount, however, is ensuring safety on the road --- a key challenge in doing so is accounting for uncertainty in human driver actions without unduly impacting planner performance. This paper introduces a minimally-interventional safety controller operating within an autonomous vehicle control stack with the role of ensuring collision-free interaction with an externally controlled (e.g., human-driven) counterpart. We leverage reachability analysis to construct a real-time (100Hz) controller that serves the dual role of (1) tracking an input trajectory from a higher-level planning algorithm using model predictive control, and (2) assuring safety through maintaining the availability of a collision-free escape maneuver as a persistent constraint regardless of whatever future actions the other car takes. A full-scale steer-by-wire platform is used to conduct traffic weaving experiments wherein the two cars, initially side-by-side, must swap lanes in a limited amount of time and distance, emulating cars merging onto/off of a highway. We demonstrate that, with our control stack, the autonomous vehicle is able to avoid collision even when the other car defies the planner's expectations and takes dangerous actions, either carelessly or with the intent to collide, and otherwise deviates minimally from the planned trajectory to the extent required to maintain safety.
△ Less
Submitted 29 December, 2018;
originally announced December 2018.
-
Two-Way Visibly Pushdown Automata and Transducers
Authors:
Luc Dartois,
Emmanuel Filiot,
Pierre-Alain Reynier,
Jean-Marc Talbot
Abstract:
Automata-logic connections are pillars of the theory of regular languages. Such connections are harder to obtain for transducers, but important results have been obtained recently for word-to-word transformations, showing that the three following models are equivalent: deterministic two-way transducers, monadic second-order (MSO) transducers, and deterministic one-way automata equipped with a fini…
▽ More
Automata-logic connections are pillars of the theory of regular languages. Such connections are harder to obtain for transducers, but important results have been obtained recently for word-to-word transformations, showing that the three following models are equivalent: deterministic two-way transducers, monadic second-order (MSO) transducers, and deterministic one-way automata equipped with a finite number of registers. Nested words are words with a nesting structure, allowing to model unranked trees as their depth-first-search linearisations. In this paper, we consider transformations from nested words to words, allowing in particular to produce unranked trees if output words have a nesting structure. The model of visibly pushdown transducers allows to describe such transformations, and we propose a simple deterministic extension of this model with two-way moves that has the following properties: i) it is a simple computational model, that naturally has a good evaluation complexity; ii) it is expressive: it subsumes nested word-to-word MSO transducers, and the exact expressiveness of MSO transducers is recovered using a simple syntactic restriction; iii) it has good algorithmic/closure properties: the model is closed under composition with a unambiguous one-way letter-to-letter transducer which gives closure under regular look-around, and has a decidable equivalence problem.
△ Less
Submitted 1 June, 2016;
originally announced June 2016.
-
Expressiveness of Visibly Pushdown Transducers
Authors:
Mathieu Caralp,
Emmanuel Filiot,
Pierre-Alain Reynier,
Frédéric Servais,
Jean-Marc Talbot
Abstract:
Visibly pushdown transducers (VPTs) are visibly pushdown automata extended with outputs. They have been introduced to model transformations of nested words, i.e. words with a call/return structure. As trees and more generally hedges can be linearized into (well) nested words, VPTs are a natural formalism to express tree transformations evaluated in streaming. This paper aims at characterizing prec…
▽ More
Visibly pushdown transducers (VPTs) are visibly pushdown automata extended with outputs. They have been introduced to model transformations of nested words, i.e. words with a call/return structure. As trees and more generally hedges can be linearized into (well) nested words, VPTs are a natural formalism to express tree transformations evaluated in streaming. This paper aims at characterizing precisely the expressive power of VPTs with respect to other tree transducer models.
△ Less
Submitted 21 November, 2013;
originally announced November 2013.
-
On Functionality of Visibly Pushdown Transducers
Authors:
Emmanuel Filiot,
Jean-François Raskin,
Pierre-Alain Reynier,
Frédéric Servais,
Jean-Marc Talbot
Abstract:
Visibly pushdown transducers form a subclass of pushdown transducers that (strictly) extends finite state transducers with a stack. Like visibly pushdown automata, the input symbols determine the stack operations. In this paper, we prove that functionality is decidable in PSpace for visibly pushdown transducers. The proof is done via a pumping argument: if a word with two outputs has a sufficien…
▽ More
Visibly pushdown transducers form a subclass of pushdown transducers that (strictly) extends finite state transducers with a stack. Like visibly pushdown automata, the input symbols determine the stack operations. In this paper, we prove that functionality is decidable in PSpace for visibly pushdown transducers. The proof is done via a pumping argument: if a word with two outputs has a sufficiently large nesting depth, there exists a nested word with two outputs whose nesting depth is strictly smaller. The proof uses technics of word combinatorics. As a consequence of decidability of functionality, we also show that equivalence of functional visibly pushdown transducers is Exptime-Complete.
△ Less
Submitted 7 February, 2010;
originally announced February 2010.
-
Bloom maps
Authors:
David Talbot,
John Talbot
Abstract:
We consider the problem of succinctly encoding a static map to support approximate queries. We derive upper and lower bounds on the space requirements in terms of the error rate and the entropy of the distribution of values over keys: our bounds differ by a factor log e. For the upper bound we introduce a novel data structure, the Bloom map, generalising the Bloom filter to this problem. The low…
▽ More
We consider the problem of succinctly encoding a static map to support approximate queries. We derive upper and lower bounds on the space requirements in terms of the error rate and the entropy of the distribution of values over keys: our bounds differ by a factor log e. For the upper bound we introduce a novel data structure, the Bloom map, generalising the Bloom filter to this problem. The lower bound follows from an information theoretic argument.
△ Less
Submitted 17 October, 2007;
originally announced October 2007.
