Electronic Notes in Theoretical Computer Science · 2009 · 15 citations · 4 references
ComputingComputer EngineeringComputer ScienceFormal MethodsHardware Description LanguagesReal-time SystemsDeductive VerificationFinite State Machine ModelingModel CheckingReal-time Systems DesignSpecification LanguagesTemporal LogicReal-time Systems VerificationTemporal Logic SpecificationTemporal Logic Verification
An efficient and mathematically rigorous translation from Live Sequence Charts (LSCs) to temporal logic is essential to providing an end-to-end specification and verification method for System on Chip (SoC) protocols. Without mathematical rigor, no translation can be trusted to completely represent the LSC specification, while inefficiency renders even provably sound translations useless in verifying the correctness of industrial-strength protocols. Previous work shows that the LSC-to-temporal logic and LSC-to-automata translations can be automated and formalized for the LSC language. In the LSC-to-temporal logic translation, the extraordinary size of the resulting formula limits the scalability of the charts that can be translated and verified. Our work, on the other hand, leverages intuitive temporal logic reductions to generate a formula that is at most quadratic in the size of the chart and demonstrates the benefits of the improved translation on several examples.
4
LSCs: Breathing Life into Message Sequence Charts
Werner Damm, David Harel · Formal Methods in System Design · 2001 · 822 citations
Tutorial on Message Sequence Charts
Ekkart Rudolph, Peter Graubmann, Jens Grabowski · Computer Networks and ISDN Systems · 1996 · 156 citations