Iterated GSMs and CO-CFL
type: Item
instance of: scholarly article
title: Iterated GSMs and CO-CFL
zbMATH Open document ID: 0659.68097
DOI: 10.1007/BF00289160
author: Jean-Michel Autebert
author: Joaquim Gabarró
published in: Acta Informatica
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 4078835
zbMATH Keywords: iterated generalized sequential machine
zbMATH Keywords: ambiguity problem
zbMATH Keywords: Kleene hierarchy
zbMATH Keywords: context-free grammars
zbMATH Keywords: undecidable problems
MaRDI profile type: Publication
cites work: Prefixes of infinite words and ambiguous context-free languages
cites work: Q3704906
cites work: Every iterated morphism yields a co-CFL
cites work: Production en temps réel et complexité de structure de suites infinies
cites work: Adherences of languages
cites work: Q4079524
cites work: Substitution and bounded languages
cites work: An infinite word language which is not co-CFL
cites work: An infinite square-free co-CFL
cites work: Applications of an infinite square-free co-CFL
cites work: Q5590814
cites work: Sur les centres de DOL-langages
cites work: The Turing degree of the inherent ambiguity problem for context-free languages
cites work: Q5573961
full work available at URL: https://doi.org/10.1007/bf00289160
OpenAlex ID: W2076121015
description: scientific article; zbMATH DE number 4078835