Author name cluster

Oded Maler

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

2 author rows

TCS Journal 2011 Journal Article

Computing reachable states for nonlinear biological models

Thao Dang
Colas Le Guernic
Oded Maler

In this paper, we describe reachability computation for continuous and hybrid systems and its potential contribution to the process of building and debugging biological models. We summarize the state-of-the-art for linear systems and then develop a novel algorithm for computing reachable states for nonlinear systems. We report experimental results obtained using a prototype implementation applied to several biological models. We believe these results constitute a promising contribution to the analysis of complex models of biological systems.

Details DOI

SAT Conference 2006 Conference Paper

Fast and Flexible Difference Constraint Propagation for DPLL(T)

Scott Cotton
Oded Maler

Abstract In the context of DPLL(T), theory propagation is the process of dynamically selecting consequences of a conjunction of constraints from a given set of candidate constraints. We present improvements to a fast theory propagation procedure for difference constraints of the form x – y ≤ c. These improvements are demonstrated experimentally.

Details

TCS Journal 2006 Journal Article

Scheduling with timed automata

Yasmina Abdeddaı¨m
Eugene Asarin
Oded Maler

In this work, we present timed automata as a natural tool for posing and solving scheduling problems. We show how efficient shortest path algorithms for timed automata can find optimal schedules for the classical job-shop problem. We then extend these results to synthesize adaptive scheduling strategies for problems with uncertainty in task durations.

Details DOI

TCS Journal 1997 Journal Article

On syntactic congruences for ω-languages

Oded Maler
Ludwig Staiger

In this paper we investigate several questions related to syntactic congruences and to minimal automata associated with ω-languages. In particular we investigate relationships between the so-called simple (because it is a simple translation from the usual definition in the case of finitary languages) syntactic congruence and its infinitary refinement (the iteration congruence) investigated by Arnold (Theoret. Comput. Sci. 39 (1985) 333–335). We show that in both cases not every ω-language having a finite syntactic monoid is regular and we give a characterization of those ω-languages having finite syntactic monoids. Among the main results we derive a condition which guarantees that the simple syntactic congruence and Arnold's syntactic congruence coincide and show that all (including infinitestate) ω-languages in the Borel class Fσ∩G δ satisfy this condition. We also show that all ω-languages in this class are accepted by their minimal-state automaton — provided they are accepted by any Muller automaton. Finally we develop an alternative theory of recognizability of ω-languages by families of right-congruence relations, and define a canonical object (much smaller then Arnold's monoid) associated with every ω-language. Using this notion of recognizability we give a necessary and sufficient condition for a regular ω-language to be accepted by its minimal-state automaton.

Details DOI

TCS Journal 1995 Journal Article

A decomposition theorem for probabilistic transition systems

Oded Maler

In this note we prove that every finite Markov chain can be decomposed into a cascade product of a Bernoulli process and several simple permutation-reset deterministic automata. The original chain is a state-homomorphic image of the product. By doing so we give a positive answer to an open question stated in (Paz, 1971) concerning the decomposability of probabilistic systems. Our result is based on the observation that in probabilistic transition systems, “randomness” and “memory” can be separated so as to allow the non-random part to be treated using common deterministic automata-theoretic techniques. The same separation technique can be applied to other kinds of non-determinism as well.

Details DOI

TCS Journal 1995 Journal Article

Reachability analysis of dynamical systems having piecewise-constant derivatives

Eugene Asarin
Oded Maler
Amir Pnueli

In this paper we consider a class of hybrid systems, namely dynamical systems with piecewise-constant derivatives (PCD systems). Such systems consist of a partition of the Euclidean space into a finite set of polyhedral sets (regions). Within each region the dynamics is defined by a constant vector field, hence discrete transitions occur only on the boundaries between regions where the trajectories change their direction. With respect to such systems we investigate the reachability question: Given an effective description of the systems and of two polyhedral subsets P and Q of the state-space, is there a trajectory starting at some xϵP and reaching some point in Q? Our main results are a decision procedure for two-dimensional systems, and an undecidability result for three or more dimensions.

Details DOI

TCS Journal 1994 Journal Article

On the effects of noise and speed on computations

Bernard Delyon
Oded Maler

In this paper we propose a model that captures the influence of noise and speed on the correct behavior of a computing device situated in a dynamic environment. Within this model we analyze the relation between structural properties of automata and their immunity to noise. We prove upper and lower bounds on the effect of noise for various classes of finite automata. In addition, we show similar relationships between relative speeds of the automaton and the environment and the accuracy of computation. Our model, combining basic notions from algebraic automata theory and the theory of stochastic processes, can serve as a starting point for a rigorous theory of computational systems embedded in the real world.

Details DOI

FOCS Conference 1990 Conference Paper

Tight Bounds on the Complexity of Cascaded Decomposition of Automata

Oded Maler
Amir Pnueli

Exponential upper and lower bounds on the size of the cascaded (Krohn-Rhodes) decomposition of automata are given. These results are used to obtain elementary algorithms for various translations between automata and temporal logic, where the previously known translations were nonelementary. The relevance of the result is discussed. >

Details