• Login
    JavaScript is disabled for your browser. Some features of this site may not work without it.
    On the Structure and Complexity of Rational Sets of Regular Languages 
    •   QMRO Home
    • School of Electronic Engineering and Computer Science
    • Electronic Engineering and Computer Science
    • On the Structure and Complexity of Rational Sets of Regular Languages
    •   QMRO Home
    • School of Electronic Engineering and Computer Science
    • Electronic Engineering and Computer Science
    • On the Structure and Complexity of Rational Sets of Regular Languages
    ‌
    ‌

    Browse

    All of QMROCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects
    ‌
    ‌

    Administrators only

    Login
    ‌
    ‌

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular Authors

    On the Structure and Complexity of Rational Sets of Regular Languages

    View/Open
    Tautschnig Closure properties and complexity of rational sets of regular languages 2014 Accepted.pdf (2.694Mb)
    Metadata
    Show full item record
    Abstract
    In a recent thread of papers, we have introduced FQL, a precise specification language for test coverage, and developed the test case generation engine FShell for ANSI C. In essence, an FQL test specification amounts to a set of regular languages, each of which has to be matched by at least one test execution. To describe such sets of regular languages, the FQL semantics uses an automata-theoretic concept known as rational sets of regular languages (RSRLs). RSRLs are automata whose alphabet consists of regular expressions. Thus, the language accepted by the automaton is a set of regular expressions. In this paper, we study RSRLs from a theoretic point of view. More specifically, we analyze RSRL closure properties under common set theoretic operations, and the complexity of membership checking, i.e., whether a regular language is an element of a RSRL. For all questions we investigate both the general case and the case of finite sets of regular languages. Although a few properties are left as open problems, the paper provides a systematic semantic foundation for the test specification language FQL.
    Authors
    Holzer, A; Schallhart, C; Tautschnig, M; Veith, H
    URI
    http://qmro.qmul.ac.uk/xmlui/handle/123456789/12016
    Collections
    • Electronic Engineering and Computer Science [2375]
    Copyright statements
    © 2015 Published by Elsevier B.V.
    Twitter iconFollow QMUL on Twitter
    Twitter iconFollow QM Research
    Online on twitter
    Facebook iconLike us on Facebook
    • Site Map
    • Privacy and cookies
    • Disclaimer
    • Accessibility
    • Contacts
    • Intranet
    • Current students

    Modern Slavery Statement

    Queen Mary University of London
    Mile End Road
    London E1 4NS
    Tel: +44 (0)20 7882 5555

    © Queen Mary University of London.