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

finiteness conditionsfinite power propertyrational set of languages

Mathematics Subject Classification ID

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

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

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