Closure properties and complexity of rational sets of regular languages

DOI10.1016/j.tcs.2015.08.035zbMath1330.68160OpenAlexW1788765909MaRDI QIDQ888431

Michael Tautschnig, Helmut Veith, Andreas Holzer, Christian Schallhart

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

decision problemsclosure propertiesregular languagesrational setstest specification in FQL

Mathematics Subject Classification ID

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

Uses Software

• FShell

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rewriting of regular expressions and regular path queries
• Limitedness theorem on finite automata with distance functions
• Representation theorems on regular languages
• The limitedness problem on distance automata: Hashiguchi's method revisited
• Parameterized regular expressions and their languages
• Rational sets in commutative monoids
• On the Structure and Complexity of Rational Sets of Regular Languages
• Graph Logics with Rational Relations and the Generalized Intersection Problem
• Query-Driven Program Testing
• Minimal Union-Free Decompositions of Regular Languages
• THE EQUALITY PROBLEM FOR RATIONAL SERIES WITH MULTIPLICITIES IN THE TROPICAL SEMIRING IS UNDECIDABLE
• Lazy abstraction
• Foundations of Software Science and Computation Structures
• Distance desert automata and the star height problem
• Information Reuse for Multi-goal Reachability Analyses
• An Introduction to Test Specification in FQL
• Lattice Automata
• Developments in Language Theory
• On finite automata with a time-variant structure

This page was built for publication: Closure properties and complexity of rational sets of regular languages