Concept

Two-way finite automaton

Related publications (38)

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 ...

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

Digital Design with Implicit State Machines

Martin Odersky, Aleksandar Prokopec, Fengyun Liu

Claude Shannon, in his famous thesis (1938), revolutionized circuit design by showing that Boolean algebra subsumes all ad-hoc methods that are used in designing switching circuits, or combinational circuits as they are commonly known today. But what is ...

2020

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

Control synthesis for stochastic systems given automata specifications defined by stochastic sets

Maryam Kamgarpour, John Lygeros, Tony Alan Wood

The problem of control synthesis to maximize the probability of satisfying automata specifications for systems with uncertainty is addressed. Two types of uncertainty are considered; stochasticity in the dynamical system and in the sets defining the specif ...

2017

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

For Coordination, State Component Transitions

Simon Bliudze, Anastasia Mavridou, Radoslaw Szymanek, Alina Zolotukhina

Coordinating component behaviour and, in particular, concurrent access to resources is among the key difficulties of building large concurrent systems. To address this, developers must be able to manipulate high-level concepts, such as Finite State Machine ...

2013

Integration of BIP into Connectivity Factory: Implementation

Simon Bliudze, Anastasia Mavridou, Radoslaw Szymanek, Alina Zolotukhina

2013

Control design for specifications on stochastic hybrid systems

Maryam Kamgarpour

We synthesize controllers for discrete-time stochastic hybrid systems such that the probability of satisfying a given specification on the system is maximized. The specifications are defined with finite state automata. It is shown that automata satisfactio ...

2012

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

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.