Publications associées à Langage rationnel

Lower Bounds for Unambiguous Automata via Communication Complexity

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

An unrefinement algorithm for planar THB-spline parameterizations

Annalisa Buffa

Unrefinement is a tool that allows to perform faster numerical simulations by controlling the level of precision in the specified area. We introduce an algorithm that creates a coarser geometry from an initial regular geometry, which is represented with re ...

ELSEVIER2022

A PCP Theorem for Interactive Proofs and Applications

Alessandro Chiesa

The celebrated PCP Theorem states that any language in NP can be decided via a verifier that reads O(1) bits from a polynomially long proof. Interactive oracle proofs (IOP), a generalization of PCPs, allow the verifier to interact with the prover for multi ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

Free Boundary Regularity for Almost Every Solution to the Signorini Problem

Xavier Fernandez-Real Girona

We investigate the regularity of the free boundary for the Signorini problem in Rn+1. It is known that regular points are (n−1)-dimensional and C∞. However, even for C∞ obstacles φ, the set of non-regular (or degenerate) points could be very large—e.g. wit ...

2021

Capture zone models of a multi-well system in aquifers bounded with regular and irregular inflow boundaries

David Andrew Barry, Setareh Nagheli

Being bounded by hydrological (inflow and barrier) boundaries, natural aquifers have regular/irregular shapes. Here, we consider aquifers bounded by segmental inflow (variable head) boundaries in which water is extracted/injected by a multi-well system. St ...

2020

Particle size selection in capillary instability of locally heated coaxial fiber

François Gallaire, Pierre-Thomas Paul Brun, Saviz Mowlavi, Isha Shukla

Harnessing fluidic instabilities to produce structures with robust and regular properties has recently emerged as a new fabrication paradigm. This approach is exemplified in the work of Gumennik et al. [Nat. Commun. 4, 2216 (2103)], in which the authors fa ...

AMER PHYSICAL SOC2019

Deductive Synthesis and Repair

Etienne Kneuss

In this thesis, we explore techniques for the development of recursive functional programs over unbounded domains that are proved correct according to their high-level specifications. We present algorithms for automatically synthesizing executable code, st ...

EPFL2016

A Decision Procedure for Regular Membership and Length Constraints over Unbounded Strings

Andrew Joseph Reynolds

We prove that the quantifier-free fragment of the theory of character strings with regular language membership constraints and linear integer constraints over string lengths is decidable. We do that by describing a sound, complete and terminating tableaux ...

Springer-Verlag Berlin2015

Measuring and Synthesizing Systems in Probabilistic Environments

Barbara Jobstmann, Rishabh Singh

The traditional synthesis question given a specification asks for the automatic construction of a system that satisfies the specification, whereas often there exists a preference order among the different systems that satisfy the given specification. Under ...

Assoc Computing Machinery2015

Finite-Length Scaling for Polar Codes

Rüdiger Urbanke, Seyed Hamed Hassani

Consider a binary-input memoryless output-symmetric channel W. Such a channel has a capacity, call it I (W), and for any R < I (W) and strictly positive constant P-e we know that we can construct a coding scheme that allows transmission at rate R with an e ...

Ieee-Inst Electrical Electronics Engineers Inc2014