On the structure and complexity of rational sets of regular languages

DOI10.4230/LIPICS.FSTTCS.2013.377zbMATH Open1359.68170arXiv1305.6074OpenAlexW177887931MaRDI QIDQ2963928FDOQ2963928

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

Publication date: 21 February 2017

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.

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

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

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)

Cited In (13)

• 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
• Title not available (Why is that?)
• MEMBERSHIP AND FINITENESS PROBLEMS FOR RATIONAL SETS OF REGULAR LANGUAGES
• Closure properties and complexity of rational sets of regular languages
• Title not available (Why is that?)
• 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
• Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract)

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)