MEMBERSHIP AND FINITENESS PROBLEMS FOR RATIONAL SETS OF REGULAR LANGUAGES

DOI10.1142/S0129054106003954MaRDI QIDQ5483370zbMATH OpenOpenAlexFDO

Authors Sergey Afonin, Elena Khazova

Publication date 14 August 2006

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054106003954

zbMATH Keywords

finite power propertyfiniteness conditionsrational set of languages

Mathematics Subject Classification ID

Database theory (68P15) Formal languages and automata (68Q45)

Recommendations

• Developments in Language Theory
• Decision Problems and Applications of Rational Sets of Regular Languages
• The rational subset membership problem for groups: a survey
• On the rational subset problem for groups.
• On the structure and complexity of rational sets of regular languages

Cites work

• A Burnside approach to the finite substitution problem
• A finiteness condition for finitely generated semigroups
• Classification of noncounting events
• Complexity of regular language matching and other decidable cases of the satisfiability problem for constraints between regular open terms
• scientific article; zbMATH DE number 3767067 (Why is no real title available?)
• scientific article; zbMATH DE number 3287733 (Why is no real title available?)
• Limitedness theorem on finite automata with distance functions
• On Decompositions of Regular Events
• On language equations with invertible operations
• On semigroups of matrices over the tropical semiring
• Representation theorems on regular languages
• Rewriting of regular expressions and regular path queries
• The limitedness problem on distance automata: Hashiguchi's method revisited

Cited in

(10)

• Membership problems for regular and context-free trace languages
• On the structure and complexity of rational sets of regular languages
• On the structure of finitely generated semigroups of unary regular languages
• Minimal Union-Free Decompositions of Regular Languages
• scientific article; zbMATH DE number 17550 (Why is no real title available?)
• Decision Problems and Applications of Rational Sets of Regular Languages
• The View Selection Problem for Regular Path Queries
• Fundamentals of Computation Theory
• Principles and Practice of Constraint Programming – CP 2004
• Closure properties and complexity of rational sets of regular languages

This page was built for publication: MEMBERSHIP AND FINITENESS PROBLEMS FOR RATIONAL SETS OF REGULAR LANGUAGES

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