On the rational subsets of the free group

DOI10.1007/s002360050045zbMath0858.68044OpenAlexW2083696051MaRDI QIDQ1924996

Géraud Sénizergues

Publication date: 27 October 1996

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s002360050045

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (9)

Rational subsets of partially reversible monoids ⋮ Free group languages: Rational versus recognizable ⋮ RATIONAL SUBSETS IN HNN-EXTENSIONS AND AMALGAMATED PRODUCTS ⋮ ALGORITHMIC PROBLEMS ON INVERSE MONOIDS OVER VIRTUALLY FREE GROUPS ⋮ Well Quasi-orders in Formal Language Theory ⋮ Solutions to twisted word equations and equations in virtually free groups ⋮ A canonical automaton for one-rule length-preserving string rewrite systems ⋮ Infinite periodic points of endomorphisms over special confluent rewriting systems ⋮ INFINITE WORDS AND CONFLUENT REWRITING SYSTEMS: ENDOMORPHISM EXTENSIONS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Groups and NTS languages
• Decidable sentences of Church-Rosser congruences
• On regularity of context-free languages
• Groups, the theory of ends, and context-free languages
• About the descriptive power of certain classes of finite string-rewriting systems
• The accessibility of finitely presented groups
• Computing presentations for subgroups of polycyclic groups and of context-free groups
• On Free Products
• A Problem on Rational Subsets of the Free Group
• An effective version of Stallings' theorem in the case of context-free groups
• PSPACE-completeness of certain algorithmic problems on the subgroups of free groups
• A Note on Pushdown Store Automata and Regular Systems

This page was built for publication: On the rational subsets of the free group