Paper Info
Title
Closure properties and complexity of rational sets of regular languages
Abstract
The test specification language FQL describes relevant test goals as regular expressions over program locations, such that each matching test case has an execution path matching this expression. To specify not only test goals but entire suites, FQL describes families of related test goals by regular expressions over extended alphabets: Herein, each symbol corresponds to a regular expression over program locations, and thus, a word in an FQL expression corresponds to a regular expression describing a single test goal. In this paper we provide a systematic foundation for FQL test specifications, which are in fact rational sets of regular languages (RSRLs). To address practically relevant problems like query optimization, we tackle open questions about RSRLs: We settle closure properties of general and finite RSRLs under common set theoretic operations. We also prove complexity results for checking equivalence and inclusion of star-free RSRLs, and for deciding whether a regular language is a member of a general or star-free RSRL. We settle most closure properties of rational sets of regular languages.We prove complexity results for equivalence, inclusion, and membership checking.We provide a systematic theoretical foundation for test coverage specifications.
Year
DOI
Venue
2015
10.1016/j.tcs.2015.08.035
Theoretical Computer Science
Keywords
Field
DocType
Rational sets,Regular languages,Test specification in FQL,Closure properties,Decision problems
Matching test,Query optimization,Code coverage,Discrete mathematics,Combinatorics,Decision problem,Regular expression,Computer science,Symbol,Equivalence (measure theory),Regular language
Journal
Volume
Issue
ISSN
605
C
0304-3975
Citations 
PageRank 
References 
0
0.34
21
Authors
4
Name
Order
Citations
PageRank
Andreas Holzer119713.62
Christian Schallhart2113756.06
Michael Tautschnig342525.84
Helmut Veith42476140.58