Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Concept

Automata theory

Related publications (17)

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

The Learnability of the Grammar of Jazz: Bayesian Inference of Hierarchical Structures in Harmony

Daniel Harasim

Musical grammar describes a set of principles that are used to understand and interpret the structure of a piece according to a musical style. The main topic of this study is grammar induction for harmony --- the process of learning structural principles f ...

EPFL2020

Proactive Synthesis of Recursive Tree-to-String Functions from Examples

Viktor Kuncak, Mikaël Mayer, Jad Hamza

Synthesis from examples enables non-expert users to generate programs by specifying examples of their behavior. A domain-specific form of such synthesis has been recently deployed in a widely used spreadsheet software product. In this paper we contribute t ...

2017

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

Representation of Medical Guidelines with a Computer Interpretable Model

Giovanni De Micheli, Alena Simalatsar, Wenqi You Dubout

Nowadays medical software is tightly coupled with medical devices that perform patient state monitoring and lately even some basic treatment procedures. Medical guidelines (GLs) can be seen as specification of a medical system which requires their computer ...

World Scientific Publ Co Pte Ltd2014

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

TAT-based Formal Representation of Medical Guidelines : Imatinib Case-study

Giovanni De Micheli, Alena Simalatsar

Computer-based interpretation of medical guide- lines (GLs) has drawn lots of attention in the past three decades. It is essential to use a formalism for GLs representation that would enable the validation of GLs structural properties, be able to map medic ...

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

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

Expressiveness And Closure Properties For Quantitative Languages

Weighted automata are nondeterministic automata with numerical weights on transitions. They can define quantitative languages L that assign to each word w a real number L(w). In the case of infinite words, the value of a run is naturally computed as the ma ...

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

Antichains For The Automata-Based Approach To Model-Checking

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

Equivalence of labeled Markov chains

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

Completeness and Nondeterminism in Model Checking Transactional Memories

Rachid Guerraoui

Software transactional memory (STM) offers a disciplined concurrent programming model for exploiting the parallelism of modern processor architectures. This paper presents the first deterministic specification automata for strict serializability and opacit ...

2008

Completeness and Nondeterminism in Model Checking Transactional Memories

Rachid Guerraoui

Software transactional memory (STM) offers a disciplined concurrent programming model for exploiting the parallelism of modern processor architectures. This paper presents the first \emph{deterministic} specification automata for strict serializability and ...

Springer2008

Robust safety of timed automata

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

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

Related publications (17)

Lower Bounds for Unambiguous Automata via Communication Complexity

Mika Tapani Göös, Weiqiang Yuan

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2022

The Learnability of the Grammar of Jazz: Bayesian Inference of Hierarchical Structures in Harmony

Daniel Harasim

EPFL2020

Proactive Synthesis of Recursive Tree-to-String Functions from Examples

Viktor Kuncak, Mikaël Mayer, Jad Hamza

2017

Measuring and Synthesizing Systems in Probabilistic Environments

Barbara Jobstmann

Assoc Computing Machinery2015

Representation of Medical Guidelines with a Computer Interpretable Model

Giovanni De Micheli, Alena Simalatsar, Wenqi You Dubout

World Scientific Publ Co Pte Ltd2014

Symbolic execution of Reo circuits using constraint automata

Hossein Hojjat

2012

TAT-based Formal Representation of Medical Guidelines : Imatinib Case-study

Giovanni De Micheli, Alena Simalatsar

Ieee2012

Polar Codes for the m-User Multiple Access Channel

Emre Telatar, Emmanuel Abbé

Institute of Electrical and Electronics Engineers2012

Quantitative Languages

2010

Expressiveness And Closure Properties For Quantitative Languages

2010

Model checking transactional memories

Rachid Guerraoui

Springer Verlag2010

Antichains For The Automata-Based Approach To Model-Checking

2009

Equivalence of labeled Markov chains

2008

Completeness and Nondeterminism in Model Checking Transactional Memories

Rachid Guerraoui

2008

Completeness and Nondeterminism in Model Checking Transactional Memories

Rachid Guerraoui

Software transactional memory (STM) offers a disciplined concurrent programming model for exploiting the parallelism of modern processor architectures. This paper presents the first \emph{deterministic} specification automata for strict serializability and ...

Springer2008

Robust safety of timed automata

Springer US2008

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

IEEE2007