History-Determinism vs. Fair-Simulation

19^th March 2024, 13:00 Ashton Lecture Theatre
Udi Boker
Reichman University, Israel

Abstract

An automaton is history-deterministic if its nondeterminism can be resolved on the fly, only using the prefix of the word read so far. An automaton A is guidable with respect to a class C of automata if it can fairly simulate every automaton B in C, whose language is contained in that of A. In other words, guidable automata are those for which inclusion and simulation coincide.

I will explore the connection between history determinism and other notions of limited nondeterminism, such as good for gameness, while focusing on the connection between history determinism and guidability.

Biography

Udi Boker is an Associate Professor of Computer Science at the Reichman University, Herzliya, Israel. He specializes in logic, formal verification, computational models, game theory, and automata theory. He received his PhD in computer science from the Tel-Aviv University, and did postdoctoral research at the Hebrew University and at the Institute of Science and Technology Austria (ISTA). Prior to joining the academy, he served as an R&D Director in the Hi-Tech company Mercury Interactive, initiating and leading the area of load-testing over the Internet.