mgreenblog

posts by category about this blog

Program synthesis talk

On June 8th I gave a talk for Orna Grumberg's seminar in formal verification presenting Kupferman and Vardi's 1997 paper Synthesis with Incomplete Information. I've posted the slides.

The paper is interesting. On the one hand, it's fairly light in terms of original contribution -- it's an extension of Pnueli and Rosner's 1989 paper On the Synthesis of a Reactive Module. On the other hand, the journal format makes the K&V paper much clearer than P&R. I know this chiefly because I was supposed to present the latter, but got bogged down and switched.

The paper contributes two things. First, they extend P&R's 2-EXPTIME algorithm for LTL synthesis to a similarly complex algorithm for CTL*. Second, they add the concept of "incomplete information". During synthesis with incomplete information, input signals (propositions in the specification ψ) are split into two sets: I, "input" -- the known or "readable" signals, and E, "environment" -- the unknown or "unreadable" signals. They aim to generate a program that is correct in terms of ψ, even though the program sees signals only in I and not in E.

For example, ψ = G((m ∧ ¬b) ⇒ Xr) ∧ (¬m ∨ b) ⇒ X¬r), where m represents a message, r a response, and b whether or not a message is "bogus". The system should respond only to nonbogus messages. Given m, b ∈ I and r ∈ O ("output"), the specification is realizable. But if b ∈ E, ψ is unrealizable.

Someone asked a very astute question during the talk: when is a specification with E ≠ ∅ realizable? Only when all propositions in E form a tautology. So why is E useful/meaningful at all? I came up with two cases: iterative checks to determine what signals are necessary; and the synthesis of systems of modules with some shared signals.

No matter how interesting the paper is, my presentation was terrible. Too formal, bad examples. It didn't help that I was speaking English to a Hebrew-speaking audience, but even Orna mentioned that my examples were bad. The problems with my examples include:

  1. Hand-drawn on the board. This meant that I spoke into the board half the time.
  2. Minimal. I drew the smallest trees possible, sticking to the binary domain and the self-product of the binary domain. This of course ties into problem number 1.
  3. Unmotivated. The tree examples all came before any mention of the need for them. The paper presents the tree preliminaries first, but perhaps a "woven" presentation would be better.
  4. Too formal. After about five minutes of explaining hide, someone said "Wait, so it's just a projection?" I was stuck in the notation, not giving a clear picture.

We'll see if I can improve, perhaps giving the talk again back at Brown. Then again, the audience at Brown is much less versed in verification in general -- increasing the need for good, clear examples. I'll certainly drop the emptiness check material in the slides (slides 32 to 39), as I ended up skipping it here in Israel.

My mediocre presentation skills aside, the paper is both very good and very frustrating. It presents difficult material clearly, making the technique completely understandable. But every step of the work -- automata generation, processing, emptiness checks -- is theoretical. So far as I can tell, there isn't a single implementation for a single step of their algorithm -- after nearly a decade. I couldn't even find a tool to translate from CTL* to μ-calculus! Without the CTL construction in section 4.4, it would have been much harder to present a nontrivial example.

But new in the synthesis world is a 2006 paper by Kupferman, Vardi, and Nir Peterman, Safraless Compositional Synthesis. It proposes an EXPTIME algorithm for LTL synthesis (as opposed to P&R's 2-EXPTIME algorithm); even better, the algorithm is incremental with regard to conjunction! Best still, they claim that it's amenable to symbolic implementation, since it doesn't use Safra's determinization technique (from the 1988 paper On the Complexity of ω-Automata). I still need to give the 2006 paper a full reading; real implementability would be very exciting. After I finish it and a few others, I'll write up and post a bibliographic review.

Roderick Bloem (roderick.bloem@ist.tu-graz.ac.at)

 Kupferman & Vardi's paper gives a 2EXPTIME algorithm. Unfortunately, this is a lower bound as was proven in Rosner's PhD thesis (presumably, that is, I have never read it).

One important contribution of this paper is the extension to generalized Buechi automata as inputs while avoiding the counting construction. This improves the complexity.

You can argue about the usefulness of the compositional approach. Who has ever seen a specification in the form f1 /\ ... /\ fn?

Michael Greenberg (mike@weaselhat.com)

 So it is; my mistake. I still haven't gotten around to reading it! There's never enough time.

I like the compositional approach, particularly considering that a lot of the non-reactive correct-by-construction stuff supports some sort of modularity. Many of the more practical heuristics for model checking take advantage of an iterative approach that seems something like the dual of compositional program synthesis.

But to answer your question more directly, I haven't seen any (real) specifications at all, much less specifications of that form.