On the structure and complexity of rational sets of regular languages

DOI10.4230/LIPICS.FSTTCS.2013.377MaRDI QIDQ2963928zbMATH OpenOpenAlexFDO

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

Publication date 21 February 2017

Full work available at URL https://arxiv.org/abs/1305.6074

zbMATH Keywords

regular languagesdecision problemsclosure propertiesrational setstest specification in FQL

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60)

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.

Recommendations

• Closure properties and complexity of rational sets of regular languages
• MEMBERSHIP AND FINITENESS PROBLEMS FOR RATIONAL SETS OF REGULAR LANGUAGES
• Developments in Language Theory
• scientific article; zbMATH DE number 176145
• Regular languages are testable with a constant number of queries

Cited in

(13)

• Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract)
• On the separability of sparse context-free languages and of bounded rational relations
• Some results in \(R\)-biordered set languages
• Factor and Subsequence Kernels and Signatures of Rational Languages
• Decision Problems and Applications of Rational Sets of Regular Languages
• scientific article; zbMATH DE number 1824155 (Why is no real title available?)
• MEMBERSHIP AND FINITENESS PROBLEMS FOR RATIONAL SETS OF REGULAR LANGUAGES
• Closure properties and complexity of rational sets of regular languages
• scientific article; zbMATH DE number 4035188 (Why is no real title available?)
• On the computation of quotients and factors of regular languages
• Rational indexes of generators of the cone of context-free languages
• The structure of reflexive regular splicing languages via Schützenberger constants
• Developments in Language Theory

This page was built for publication: On the structure and complexity of rational sets of regular languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2963928)