Concept

Pushdown automaton

Related publications (17)

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.

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

Completeness and Nondeterminism in Model Checking Transactional Memories

Rachid Guerraoui, Vasu Singh

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

2008

Completeness and Nondeterminism in Model Checking Transactional Memories

Rachid Guerraoui, Vasu Singh

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

Expressiveness and Closure Properties for Quantitative Languages

Laurent Doyen

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

2008

From Nondeterministic Buchi and Streett Automata to Deterministic Parity Automata

Determinisation and complementation are foundational notions in computer science. When considering finite automata on finite words nondeterminisation and complementation are one and the same. Given a nondeterministic finite automaton there exists an expone ...

2005

Minimizing Generalized Buchi Automata

Sudeep Juvekar

We consider the problem of minimization of generalized Buchi automata. We show how to extend fair simulation and delayed simulation to the case where the Buchi automaton has multiple acceptance conditions. For fair simulation, we show how to efficiently co ...

2005

Dynamic load balancing of parallel cellular automata

Roger Hersch, Marc Mazzariol

We are interested in running in parallel cellular automata. We present an algorithm which explores the dynamic remapping of cells in order to balance the load between processing nodes. The parallel application runs on a cluster of PCs connected by Fast-Eth ...

SPIE-Int. Soc. Opt. Eng2000