5 results
Benedikt Bollig ; Karin Quaas ; Arnaud Sangnier.
We consider the model-checking problem for freeze LTL on one-counter automata (OCA). Freeze LTL extends LTL with the freeze quantifier, which allows one to store different counter values of a run in registers so that they can be compared with one another. As the model-checking problem is undecidable […]
Published on September 30, 2019
Lina Ye ; Igor Khmelnitsky ; Serge Haddad ; Benoît Barbot ; Benedikt Bollig ; Martin Leucker ; Daniel Neider ; Rajarshi Roy.
Angluin's L$^*$ algorithm learns the minimal deterministic finite automaton (DFA) of a regular language using membership and equivalence queries. Its probabilistic approximatively correct (PAC) version substitutes an equivalence query by numerous random membership queries to get a high level […]
Published on March 20, 2024
Benedikt Bollig ; Alain Finkel ; Amrita Suresh.
We propose a relaxation to the definition of well-structured transition systems (\WSTS) while retaining the decidability of boundedness and non-termination. In this class, the well-quasi-ordered (wqo) condition is relaxed such that it is applicable only between states that are reachable one from […]
Published on June 12, 2024
Benedikt Bollig ; Arnaud Sangnier ; Olivier Stietel.
We study first-order logic over unordered structures whose elements carry a finite number of data values from an infinite domain. Data values can be compared wrt.\ equality. As the satisfiability problem for this logic is undecidable in general, we introduce a family of local fragments. They […]
Published on July 2, 2024
Benedikt Bollig ; Dietrich Kuske ; Ingmar Meinecke.
We examine a bidirectional propositional dynamic logic (PDL) for finite and infinite message sequence charts (MSCs) extending LTL and TLC-. By this kind of multi-modal logic we can express properties both in the entire future and in the past of an event. Path expressions strengthen the classical […]
Published on September 4, 2010