DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2013.377

On the Structure and Complexity of Rational Sets of Regular Languages

Authors: Andreas Holzer, Christian Schallhart, Michael Tautschnig, and Helmut Veith

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

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.

Cite as

Andreas Holzer, Christian Schallhart, Michael Tautschnig, and Helmut Veith. On the Structure and Complexity of Rational Sets of Regular Languages. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 377-388, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{holzer_et_al:LIPIcs.FSTTCS.2013.377,
  author =	{Holzer, Andreas and Schallhart, Christian and Tautschnig, Michael and Veith, Helmut},
  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 =	{Seth, Anil and Vishnoi, Nisheeth K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.377},
  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}
}

Search Results

Documents authored by Tautschnig, Michael

On the Structure and Complexity of Rational Sets of Regular Languages

Abstract

Cite as

Thanks for your feedback!

Could not send message