Abstrakt. Vi anser att problemet med att syntetisera digitala mönster från deras LTL specifikation. Trots den teoretiska dubbla exponentiellt lägre gränsen för det allmänna fallet, visar vi att för många expressiva specifikationer av hårdvara konstruktioner problemet kan lösas i tid N 3. Vi beskriver bakgrunden till problemet, som en del av det europeiska projektet Prosyd som syftar till att tillhandahålla ett fastighetsbaserat utvecklingsflöde för maskinvarudesign. Inom detta projekt spelar syntesen en viktig roll, först för att kontrollera om en given specifikation är genomförbar, och sedan för att syntetisera en del av det utvecklade systemet. Klassen av LTL-formler beaktas är den av Generalized Reactivity(1) (generalized Streett(1)) formler, dvs formler av formen: där varje pi, Qi är en booleansk kombination av atomiska förslag. Vi anser också att det mer allmänna fallet där varje pi, qi är en godtycklig tidigare LTL formel över atomiska förslag. För denna klass av formler, presenterar vi en N 3 - time algoritm som kontrollerar om en sådan formel är realizable, dvs. det finns en krets som uppfyller formeln under någon uppsättning av ingångar som tillhandahålls av miljön. Om specifikationen är realizable, algoritmen fortsätter att konstruera en automaton som representerar en av de möjliga genomförande kretsar. Autotonen beräknas och presenteras symboliskt.
Piterman m.fl. REF visar att realiserings- och syntesproblemen i GR(1)-specifikationerna kan lösas effektivt på polynomtid.
Synthesis of reactive(1) designs
{'venue': 'In Proc. Verification, Model Checking, and Abstract Interpretation (VMCAI’06', 'journal': None, 'mag_field_of_study': ['Computer Science']}