A Parametric Abstract Domain for Lattice-Valued Regular Expressions

Jan Midtgaard, Flemming Nielson, Hanne Riis Nielson

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

527 Downloads (Pure)

Abstract

We present a lattice-valued generalization of regular expressions as an abstract domain for static analysis. The parametric abstract domain rests on a generalization of Brzozowski derivatives and works for both finite and infinite lattices. We develop both a co-inductive, simulation algorithm for deciding ordering between two domain elements and a widening operator for the domain. Finally we illustrate the domain with a static analysis that analyses a communicating process against a lattice-valued regular expression expressing the environment’s network communication.
Original languageEnglish
Title of host publicationProceedings of the 23rd International Symposium on Static Analysis (SAS 2016)
EditorsXavier Rival
PublisherSpringer
Publication date2016
Pages338-360
ISBN (Print)978-3-662-53412-0
ISBN (Electronic)978-3-662-53413-7
Publication statusPublished - 2016
Event23rd International Symposium on Static Analysis - Edinburgh, United Kingdom
Duration: 8 Sept 201610 Sept 2016
Conference number: 23
http://staticanalysis.org/sas2016/

Conference

Conference23rd International Symposium on Static Analysis
Number23
Country/TerritoryUnited Kingdom
CityEdinburgh
Period08/09/201610/09/2016
Internet address
SeriesLecture Notes in Computer Science
Volume9837
ISSN0302-9743

Fingerprint

Dive into the research topics of 'A Parametric Abstract Domain for Lattice-Valued Regular Expressions'. Together they form a unique fingerprint.

Cite this