Concept

Unambiguous finite automaton

Related publications (21)

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

Light refocusing with up-scalable resonant waveguide gratings in confocal prolate spheroid arrangements

Olivier Martin, Benjamin Gallinet, Giorgio Quaranta, Zdenek Benes

Resonant waveguide gratings (RWGs) are thin-film structures, where coupled modesinterfere with the diffracted incoming wave and produce strong angular and spectral filtering. The combination of two finite-length and impedance matched RWGs allows the creati ...

2018

Measuring and Synthesizing Systems in Probabilistic Environments

Barbara Jobstmann

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

On the Dispersions of the Gel'fand-Pinsker Channel and Dirty Paper Coding

Jonathan Mark Scarlett

This paper studies the second-order coding rates for memoryless channels with a state sequence known non-causally at the encoder. In the case of finite alphabets, an achievability result is obtained using constant-composition random coding, and by using a ...

Institute of Electrical and Electronics Engineers2015

High-Frequency Electromagnetic Coupling to Multiconductor Transmission Lines of Finite Length

Farhad Rachidi-Haeri, Marcos Rubinstein, Sidi-Rachid Cherkaoui, Gaspard Lugrin

This paper presents a theory and an efficient solution approach for the problem of electromagnetic field coupling to a long multiconductor line with arbitrary terminations. The theory is applicable for a high-frequency plane wave electromagnetic field exci ...

Ieee-Inst Electrical Electronics Engineers Inc2015

Asymptotically Optimal Matching of Multiple Sequences to Source Distributions and Training Sequences

Jayakrishnan Unnikrishnan

Consider a finite set of sources, each producing independent identically distributed observations that follow a unique probability distribution on a finite alphabet. We study the problem of matching a finite set of observed sequences to the set of sources ...

Institute of Electrical and Electronics Engineers2015

Stochastic interpretation of the advection diffusion equation and its relevance to bed load transport

Christophe Ancey, Joris Heyman

The advection diffusion equation is one of the most widespread equations in physics. It arises quite often in the context of sediment transport, e.g., for describing time and space variations in the particle activity (the solid volume of particles in motio ...

American Geophysical Union2015

Bilinear Generalized Approximate Message Passing—Part I: Derivation

Volkan Cevher

In this paper, we extend the generalized approximate message passing (G-AMP) approach, originally proposed for high-dimensional generalized-linear regression in the context of compressive sensing, to the generalized-bilinear case, which enables its applica ...

Institute of Electrical and Electronics Engineers2014

Bilinear Generalized Approximate Message Passing—Part II: Applications

Volkan Cevher

Ieee-Inst Electrical Electronics Engineers Inc2014

Windowed Decoding of Spatially Coupled Codes

Rüdiger Urbanke

Spatially coupled codes have been of interest recently owing to their superior performance over memoryless binary-input channels. The performance is good both asymptotically, since the belief propagation thresholds approach the Shannon limit, as well as fo ...

Ieee-Inst Electrical Electronics Engineers Inc2013

On Optimal Two Sample Homogeneity Tests for Finite Alphabets

Jayakrishnan Unnikrishnan

Suppose we are given two independent strings of data from a known finite alphabet. We are interested in testing the null hypothesis that both the strings were drawn from the same distribution, assuming that the samples within each string are mutually indep ...

Ieee2012

Irregular Product Codes

Mohammad Amin Shokrollahi, Ghid Maatouk, Masoud Alipour Babaei, Seyed Omid Etesami

We introduce irregular product codes, a class of codes where each codeword is represented by a matrix and the entries in each row (column) of the matrix come from a component row (column) code. As opposed to standard product codes, we do not require that a ...

Ieee2012

An Effective Approach for High-Frequency Electromagnetic Field-to-Line Coupling Analysis Based on Regularization Techniques

Farhad Rachidi-Haeri

An effective method based on the regularization technique to solve the problem of the high-frequency electromagnetic field coupling to an overhead transmission line is presented. The integral-differential equation describing the field-induced current into ...

Ieee-Inst Electrical Electronics Engineers Inc2012

Rank-Deficient Quadratic-Form Maximization Over M-Phase Alphabet: Polynomial-Complexity Solvability And Algorithmic Developments

Anastasios Kyrillidis

The maximization of a positive (semi) definite complex quadratic form over a finite alphabet is NP-hard and achieved through exhaustive search when the form has full rank. However, if the form is rank-deficient, the optimal solution can be computed with on ...

IEEE2011

Quantitative Languages

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

Model checking transactional memories

Rachid Guerraoui

Model checking transactional memories (TMs) is difficult because of the unbounded number, length, and delay of concurrent transactions, as well as the unbounded size of the memory. We show that, under certain conditions satisfied by most TMs we know of, th ...

Springer Verlag2010

Generalized from of Telegrapher’s Equations for the Electromagnetic Field Coupling to Buried Wires of Finite Length

Farhad Rachidi-Haeri

In this paper, a generalized form of telegrapher's equations for electromagnetic field coupling to buried wires is derived. The presented approach is based on thin-wire antenna theory. The effect of a dissipative half-space is taken into account via the re ...

2009

Electrofragmentation modeling of conductive coatings on polymer substrates

Jan-Anders Edvin Maansson, Yves Leterrier, Luc Rougier, Judith Helen Waller

Damage occurring under tensile loading and the resulting increase of electrical resistance of indium-doped tin oxide and amorphous graphite coatings on various polymer substrates are investigated, using an electro-fragmentation method in situ in an optical ...

American Institute of Physics2009

Source and channel coding using Fountain codes

The invention of Fountain codes is a major advance in the field of error correcting codes. The goal of this work is to study and develop algorithms for source and channel coding using a family of Fountain codes known as Raptor codes. From an asymptotic poi ...

EPFL2009

An axisymmetric stress analysis in a single fibre composite of finite length under a thermal expansion mismatch

John Botsis, Laurent Humbert, Fabiano Colpo

In this paper, an exact solution is derived for the characterization of thermal stresses in a single-fibre composite of finite length. All the required boundary and interfacial conditions of the thermo-elastic problem are thus satisfied exactly. The propos ...

2009