TAVer November 2023

taver@software.imdea.org

2 participants
2 discussions

3rd meeting: The Covering and Boundedness Problems for Vector Addition Systems
by Chana Weil-Kennedy 14 Nov '23

14 Nov '23

Hi all, For our third meeting, we will discuss the attached paper and I'll host the discussion. The meeting will take place in Room 349 on Monday, November 27th at noon. Mini-intro: This is a classic paper of Petri net theory. Petri nets — or the equivalent model of VASS — are a popular model of concurrency with a number of applications in database theory, business processes, and more (see e.g. surveys below). One of the central decision problems for Petri nets is the coverability problem, that asks whether there is a run from a given initial configuration to some configuration with at least the counter values of a given target configuration. Coverability is useful in the verification of safety conditions. The paper I will present is Rackoff’s 1978 result that coverability is in EXPSPACE, proved by showing that if coverability holds then there exists a run of double-exponential length. Petri net surveys: https://dl.acm.org/doi/10.1145/2893582.2893585 <https://dl.acm.org/doi/10.1145/2893582.2893585> https://link.springer.com/content/pdf/10.1007/3-540-65306-6_20.pdf <https://link.springer.com/content/pdf/10.1007/3-540-65306-6_20.pdf> See you, Chana

1 0

2nd meeting: Learning regular sets from queries and counterexamples
by Pierre Ganty 05 Nov '23

05 Nov '23

Hi all, For our second meeting, we will discuss the attached paper and I'll host the discussion. The meeting will take place in Room 349 on Monday, November 13th at noon. The problem of identifying an unknown regular set from examples of its members and nonmembers is addressed. It is assumed that the regular set is presented by a minimally adequate Teacher, which can answer membership queries about the set and can also test a conjecture and indicate whether it is equal to the unknown set and provide a counterexample if not. (A counterexample is a string in the symmetric difference of the correct set and the conjectured set.) A learning algorithm L^* is described that correctly learns any regular set from any minimally adequate Teacher in time polynomial in the number of states of the minimum DFA for the set and the maximum length of any counterexample provided by the Teacher. It is shown that in a stochastic setting the ability of the Teacher to test conjectures may be replaced by a random sampling oracle, EX( ). A polynomial-time learning algorithm is shown for a particular problem of context-free language identification. See you, Pierre.

1 0

2025

2024

2023

TAVer November 2023