License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2013.377
URN: urn:nbn:de:0030-drops-43871
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4387/
Go to the corresponding LIPIcs Volume Portal

Holzer, Andreas ; Schallhart, Christian ; Tautschnig, Michael ; Veith, Helmut

On the Structure and Complexity of Rational Sets of Regular Languages

pdf-format:
28.pdf (0.6 MB)

Abstract

In the recently designed and implemented test specification language FQL, relevant test goals are specified as regular expressions over program locations. To transition from single test goals to test suites, FQL describes suites as regular expressions over finite alphabets where each symbol corresponds to a regular expression over program locations. Hence, each word in a test suite expression yields a test goal specification. Such test suite specifications are in fact rational sets of regular languages (RSRLs). We show 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 checking whether a regular language is a member of a general or star-free RSRL. As the star-free (and thus finite) case underlies FQL specifications, the closure and complexity results provide a systematic foundation for FQL test specifications.

BibTeX - Entry

@InProceedings{holzer_et_al:LIPIcs:2013:4387,
  author =	{Andreas Holzer and Christian Schallhart and Michael Tautschnig and Helmut Veith},
  title =	{{On the Structure and Complexity of Rational Sets of Regular Languages}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{377--388},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Anil Seth and Nisheeth K. Vishnoi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4387},
  URN =		{urn:nbn:de:0030-drops-43871},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.377},
  annote =	{Keywords: Rational Sets, Regular Languages, Test Specification in FQL, Closure Properties, Decision Problems}
}

Keywords: Rational Sets, Regular Languages, Test Specification in FQL, Closure Properties, Decision Problems
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Issue Date: 2013
Date of publication: 10.12.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI