Concept

Quantum finite automaton

Related publications (20)

Hidden Markov Modeling Over Graphs

Ali H. Sayed, Virginia Bordignon, Mert Kayaalp, Stefan Vlaski

This work proposes a multi-agent filtering algorithm over graphs for finite-state hidden Markov models (HMMs), which can be used for sequential state estimation or for tracking opinion formation over dynamic social networks. We show that the difference fro ...

IEEE2022

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

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

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

Formalization, Implementation, and Modeling of Institutional Controllers for Distributed Robotic Systems

Alcherio Martinoli, José Nuno Ferreira Maia Pereira

The work described is part of a long term program of introducing institutional robotics, a novel framework for the coordination of robot teams that stems from institutional economics concepts. Under the framework, institutions are cumulative sets of persis ...

2014

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

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

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

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

Irregular Product Codes

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

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

Polar Codes for the m-User Multiple Access Channel

Emre Telatar, Emmanuel Abbé

In this paper, polar codes for the m-user multiple access channel (MAC) with binary inputs are constructed. It is shown that Arikan's polarization technique applied individually to each user transforms independent uses of an m-user binary input MAC into su ...

Institute of Electrical and Electronics Engineers2012

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

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

Model checking transactional memories

Rachid Guerraoui, Vasu Singh

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

Antichains For The Automata-Based Approach To Model-Checking

Laurent Doyen

We propose and evaluate antichain algorithms to solve the universality and language inclusion problems for nondeterministic Buchi automata, and the emptiness problem for alternating Buchi automata. To obtain those algorithms, we establish the existence of ...

2009

Asymmetric information embedding

Mohammad Amin Shokrollahi

In the Information Embedding Problem one is given a piece of data which can be altered only conditionally, for example only at certain places. One is then asked to embed an arbitrary message into the data by only applying admissible changes to the data. Th ...

Springer-Verlag2008

Equivalence of labeled Markov chains

Laurent Doyen

We consider the equivalence problem for labeled Markov chains (LMCs), where each state is labeled with an observation. Two LMCs are equivalent if every finite sequence of observations has the same probability of occurrence in the two LMCs. We show that equ ...

2008

Robust safety of timed automata

Laurent Doyen

Timed automata are governed by an idealized semantics that assumes a perfectly precise behavior of the clocks. The traditional semantics is not robust because the slightest perturbation in the timing of actions may lead to completely different behaviors of ...

Springer US2008

Algorithms for Interface Synthesis

Vasu Singh, Dirk Thilo Beyer

A temporal interface for a software component is a ﬁnite automaton that speciﬁes the legal sequences of calls to functions that are provided by the component. We compare and evaluate three different algorithms for automatically extracting temporal interfac ...

Springer2007

Soundness and Equivalence of Petri Nets and Annotated Finite State Automate: A Comparison in the SOA Context

A lot of work exists on notions of equivalence and soundness relations of different workflow models, which are used in different domains like e.g. Business Process Modeling, Software and Service Engineering. These definitions are based on different models, ...

IEEE2007