Concept

Automate fini déterministe bidirectionnel

Publications associées (15)

Anomalous dissipation and other non-smooth phenomena in fluids

The thesis is dedicated to the study of two main partial differential equations (PDEs) in fluid dynamics: the Navier-Stokes equations, which describe the motion of incompressible fluids, and the transport equation with divergence-free velocity fields, whic ...

EPFL2024

Lower Bounds for Unambiguous Automata via Communication Complexity

Mika Tapani Göös, Weiqiang Yuan

We use results from communication complexity, both new and old ones, to prove lower bounds for unambiguous finite automata (UFAs). We show three results. 1) Complement: There is a language L recognised by an n-state UFA such that the complement language ̅L ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2022

Finite Littlestone Dimension Implies Finite Information Complexity

Michael Christoph Gastpar, Aditya Pradeep, Ido Nachum

We prove that every online learnable class of functions of Littlestone dimension d admits a learning algorithm with finite information complexity. Towards this end, we use the notion of a globally stable algorithm. Generally, the information complexity of ...

2022

On quadratic matrix equations with infinite size coefficients encountered in QBD stochastic processes

Stefano Massei

Matrix equations of the kind A(1)X(2)+A(0)X+A(-1)=X, where both the matrix coefficients and the unknown are semi-infinite matrices belonging to a Banach algebra, are considered. These equations, where coefficients are quasi-Toeplitz matrices, are encounter ...

WILEY2018

Patching And Weak Approximation In Isometry Groups

Eva Bayer Fluckiger

Let R be a semilocal principal ideal domain. Two algebraic objects over R in which scalar extension makes sense (e.g. quadratic spaces) are said to be of the same genus if they become isomorphic after extending scalars to all completions of R and its fract ...

Amer Mathematical Soc2017

Locally differentially-private distribution estimation

Michael Christoph Gastpar, Adriano Pastore

We consider a setup in which confidential i.i.d. samples X1, ..., Xn from an unknown discrete distribution PX are passed through a discrete memoryless privatization channel (a.k.a. mechanism) which guarantees an epsilon-level of local differential privacy. ...

Ieee2016

Symbolic execution of Reo circuits using constraint automata

Hossein Hojjat

Reo is a coordination language that can be used to model different systems. We propose a technique for symbolic execution of Reo circuits using the symbolic representation of data constraints in Constraint Automata. This technique enables us to obtain the ...

2012

Instruction Set Extensions for Cryptographic Hash Functions on a Microcontroller Architecture

Andreas Peter Burg, Jeremy Hugues-Felix Constantin

In this paper, we investigate the benefits of instruction set extensions (ISEs) on a 16-bit microcontroller architecture for software implementations of cryptographic hash functions, using the example of the five SHA-3 final round candidates. We identify t ...

Ieee2012

The Sampling Rate-Distortion Tradeoff for Sparsity Pattern Recovery in Compressed Sensing

Michael Christoph Gastpar

Recovery of the sparsity pattern (or support) of an unknown sparse vector from a limited number of noisy linear measurements is an important problem in compressed sensing. In the high-dimensional setting, it is known that recovery with a vanishing fraction ...

Institute of Electrical and Electronics Engineers2012

Quantitative Languages

Laurent Doyen

Quantitative generalizations of classical languages, which assign to each word a real number instead of a Boolean value, have applications in modeling resource-constrained computation. We use weighted automata (finite automata with transition weights) to d ...

2010