1 Search Results for "Tautschnig, Michael"

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-dev.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}
}
  • Refine by Author
  • 1 Holzer, Andreas
  • 1 Schallhart, Christian
  • 1 Tautschnig, Michael
  • 1 Veith, Helmut

  • Refine by Classification

  • Refine by Keyword
  • 1 Closure Properties
  • 1 Decision Problems
  • 1 Rational Sets
  • 1 Regular Languages
  • 1 Test Specification in FQL

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2013

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact