On the complexity of computing the profinite closure of a rational language

DOI10.1016/J.TCS.2011.06.022zbMath1222.68106OpenAlexW2032947973MaRDI QIDQ719326

Pierre-Cyrille Héam

Publication date: 10 October 2011

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

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

zbMATH Keywords

finite automataprofinite topologystate complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Topologies for the free monoid
• Abelian pointlikes of a monoid
• A polynomial time algorithm to compute the Abelian kernel of a finite monoid
• Finite state automata: A geometric approach
• A topological approach to a conjecture of Rhodes
• A Conjecture on the Hall Topology for the Free Group
• ASH'S TYPE II THEOREM, PROFINITE TOPOLOGY AND MALCEV PRODUCTS: PART I
• On The Profinite Topology on a Free Group
• Polynomial closure of group languages and open sets of the Hall topology
• Extending partial automorphisms and the profinite topology on free groups
• A topology for free groups and related groups

This page was built for publication: On the complexity of computing the profinite closure of a rational language