Iterated GSMs and CO-CFL

We study the infinite words generated by an iterated generalized sequential machine (gsm). The motivation was twofold. The first one was given by the apparent similarity between the iterated gsm and the iterated morphism. However contrary to the appearences almost all questions become undecidable. The second one was to disprove the following conjecture of Berstel: The language of coprefixes of an infinite word w is context free iff w is generated by an iterated gsm. We use for that the infinite word: \[ w=abca^ 2ba^ 2bca^ 4ba^ 4ba^ 4ba^ 4bc...(a^{2^ n}b)^{2^ n}c...\quad. \] We prove also that the degree of the ambiguity problem for coprefixes of iterated gsm in \(\Pi_ 1\)-complete in the Kleene hierarchy. This result fills the gap between the degree of this problem for iterated morphisms which is \(\Pi_ 0\)- and for arbitrary context-free grammars which is \(\Pi_ 2\)- complete.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Iterated GSMs and CO-CFL

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