Closure properties and complexity of rational sets of regular languages

DOI10.1016/J.TCS.2015.08.035MaRDI QIDQ888431zbMATH OpenOpenAlexFDO

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

Publication date 30 October 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.08.035

zbMATH Keywords

regular languagesdecision problemsclosure propertiesrational setstest specification in FQL

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Recommendations

• On the structure and complexity of rational sets of regular languages
• MEMBERSHIP AND FINITENESS PROBLEMS FOR RATIONAL SETS OF REGULAR LANGUAGES
• Developments in Language Theory
• On the complexity of computing the profinite closure of a rational language
• Decision Problems and Applications of Rational Sets of Regular Languages
• The full quotient and its closure property for regular languages
• Closure properties and descriptional complexity of deterministic regular expressions
• Recognizing pro-\(\mathrm{R}\) closures of regular languages
• A closure property of regular languages
• Regular Closure of Deterministic Languages

Cites work

• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3264082 (Why is no real title available?)
• An introduction to test specification in FQL
• Approximate comparison of distance automata
• Developments in Language Theory
• Distance desert automata and the star height problem
• Foundations of Software Science and Computation Structures
• Graph Logics with Rational Relations and the Generalized Intersection Problem
• Information reuse for multi-goal reachability analyses
• Lattice Automata
• Lazy abstraction
• Limitedness theorem on finite automata with distance functions
• Minimal Union-Free Decompositions of Regular Languages
• On finite automata with a time-variant structure
• On the structure and complexity of rational sets of regular languages
• Parameterized regular expressions and their languages
• Query-Driven Program Testing
• Rational sets in commutative monoids
• Representation theorems on regular languages
• Rewriting of regular expressions and regular path queries
• THE EQUALITY PROBLEM FOR RATIONAL SERIES WITH MULTIPLICITIES IN THE TROPICAL SEMIRING IS UNDECIDABLE
• The limitedness problem on distance automata: Hashiguchi's method revisited

Cited in

(9)

• Finite turns and the regular closure of linear context-free languages
• The congruence theory of closure properties of regular tree languages
• On the structure and complexity of rational sets of regular languages
• Decision Problems and Applications of Rational Sets of Regular Languages
• scientific article; zbMATH DE number 6542558 (Why is no real title available?)
• scientific article; zbMATH DE number 6606340 (Why is no real title available?)
• A closure property of regular languages
• Developments in Language Theory
• An algorithmic approach for checking closure properties of Ω-regular languages

Describes a project that uses

Uses Software

• FShell

This page was built for publication: Closure properties 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 Q888431)