A tool for intersecting context-free grammars and its applications

Graeme Gange; Jorge A. Navas; Peter Schachte; Harald Søndergaard; Peter J. Stuckey

doi:10.1007/978-3-319-17524-9_31

A tool for intersecting context-free grammars and its applications

Graeme Gange, Jorge A. Navas, Peter Schachte, Harald Søndergaard, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

4 Citations (Scopus)

Abstract

This paper describes a tool for intersecting context-free grammars. Since this problem is undecidable the tool follows a refinement-based approach and implements a novel refinement which is complete for regularly separable grammars. We show its effectiveness for safety verification of recursive multi-threaded programs.

Original language	English
Title of host publication	NASA Formal Methods
Subtitle of host publication	7th International Symposium, NFM 2015 Pasadena, CA, USA, April 27–29, 2015 Proceedings
Editors	Klaus Havelund, Gerard Holzmann, Rajeev Joshi
Place of Publication	Cham Switzerland
Publisher	Springer
Pages	422-428
Number of pages	7
ISBN (Electronic)	9783319175249
ISBN (Print)	9783319175232
DOIs	https://doi.org/10.1007/978-3-319-17524-9_31
Publication status	Published - 2015
Externally published	Yes
Event	NASA Formal Methods Symposium (NFM) 2015 - Pasadena, United States of America Duration: 27 Apr 2015 → 29 Apr 2015 Conference number: 7th https://web.archive.org/web/20150124212932/http://nasaformalmethods.org/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	9058
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	NASA Formal Methods Symposium (NFM) 2015
Abbreviated title	NFM 2015
Country/Territory	United States of America
City	Pasadena
Period	27/04/15 → 29/04/15
Internet address	https://web.archive.org/web/20150124212932/http://nasaformalmethods.org/

Access to Document

10.1007/978-3-319-17524-9_31

Cite this

Gange, G., Navas, J. A., Schachte, P., Søndergaard, H., & Stuckey, P. J. (2015). A tool for intersecting context-free grammars and its applications. In K. Havelund, G. Holzmann, & R. Joshi (Eds.), NASA Formal Methods: 7th International Symposium, NFM 2015 Pasadena, CA, USA, April 27–29, 2015 Proceedings (pp. 422-428). (Lecture Notes in Computer Science ; Vol. 9058). Springer. https://doi.org/10.1007/978-3-319-17524-9_31

Gange, Graeme ; Navas, Jorge A. ; Schachte, Peter et al. / A tool for intersecting context-free grammars and its applications. NASA Formal Methods: 7th International Symposium, NFM 2015 Pasadena, CA, USA, April 27–29, 2015 Proceedings. editor / Klaus Havelund ; Gerard Holzmann ; Rajeev Joshi. Cham Switzerland : Springer, 2015. pp. 422-428 (Lecture Notes in Computer Science ).

@inproceedings{c5ccb332307f4af89cd6abafae6d3e2c,

title = "A tool for intersecting context-free grammars and its applications",

abstract = "This paper describes a tool for intersecting context-free grammars. Since this problem is undecidable the tool follows a refinement-based approach and implements a novel refinement which is complete for regularly separable grammars. We show its effectiveness for safety verification of recursive multi-threaded programs.",

author = "Graeme Gange and Navas, {Jorge A.} and Peter Schachte and Harald S{\o}ndergaard and Stuckey, {Peter J.}",

year = "2015",

doi = "10.1007/978-3-319-17524-9_31",

language = "English",

isbn = "9783319175232",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "422--428",

editor = "Klaus Havelund and Gerard Holzmann and Rajeev Joshi",

booktitle = "NASA Formal Methods",

address = "Switzerland",

note = "NASA Formal Methods Symposium (NFM) 2015, NFM 2015 ; Conference date: 27-04-2015 Through 29-04-2015",

url = "https://web.archive.org/web/20150124212932/http://nasaformalmethods.org/",

}

Gange, G, Navas, JA, Schachte, P, Søndergaard, H & Stuckey, PJ 2015, A tool for intersecting context-free grammars and its applications. in K Havelund, G Holzmann & R Joshi (eds), NASA Formal Methods: 7th International Symposium, NFM 2015 Pasadena, CA, USA, April 27–29, 2015 Proceedings. Lecture Notes in Computer Science , vol. 9058, Springer, Cham Switzerland, pp. 422-428, NASA Formal Methods Symposium (NFM) 2015, Pasadena, California, United States of America, 27/04/15. https://doi.org/10.1007/978-3-319-17524-9_31

A tool for intersecting context-free grammars and its applications. / Gange, Graeme; Navas, Jorge A.; Schachte, Peter et al.
NASA Formal Methods: 7th International Symposium, NFM 2015 Pasadena, CA, USA, April 27–29, 2015 Proceedings. ed. / Klaus Havelund; Gerard Holzmann; Rajeev Joshi. Cham Switzerland: Springer, 2015. p. 422-428 (Lecture Notes in Computer Science ; Vol. 9058).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - A tool for intersecting context-free grammars and its applications

AU - Gange, Graeme

AU - Navas, Jorge A.

AU - Schachte, Peter

AU - Søndergaard, Harald

AU - Stuckey, Peter J.

N1 - Conference code: 7th

PY - 2015

Y1 - 2015

N2 - This paper describes a tool for intersecting context-free grammars. Since this problem is undecidable the tool follows a refinement-based approach and implements a novel refinement which is complete for regularly separable grammars. We show its effectiveness for safety verification of recursive multi-threaded programs.

AB - This paper describes a tool for intersecting context-free grammars. Since this problem is undecidable the tool follows a refinement-based approach and implements a novel refinement which is complete for regularly separable grammars. We show its effectiveness for safety verification of recursive multi-threaded programs.

UR - http://www.scopus.com/inward/record.url?scp=84942588287&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-17524-9_31

DO - 10.1007/978-3-319-17524-9_31

M3 - Conference Paper

AN - SCOPUS:84942588287

SN - 9783319175232

T3 - Lecture Notes in Computer Science

SP - 422

EP - 428

BT - NASA Formal Methods

A2 - Havelund, Klaus

A2 - Holzmann, Gerard

A2 - Joshi, Rajeev

PB - Springer

CY - Cham Switzerland

T2 - NASA Formal Methods Symposium (NFM) 2015

Y2 - 27 April 2015 through 29 April 2015

ER -

Gange G, Navas JA, Schachte P, Søndergaard H, Stuckey PJ. A tool for intersecting context-free grammars and its applications. In Havelund K, Holzmann G, Joshi R, editors, NASA Formal Methods: 7th International Symposium, NFM 2015 Pasadena, CA, USA, April 27–29, 2015 Proceedings. Cham Switzerland: Springer. 2015. p. 422-428. (Lecture Notes in Computer Science ). doi: 10.1007/978-3-319-17524-9_31

A tool for intersecting context-free grammars and its applications

Abstract

Publication series

Conference

Access to Document

Other files and links

Cite this