×

There does not exist an enumerable family of context-free grammars that generates the class of single-valued languages. (English. Russian original) Zbl 0800.68535

Math. Notes 50, No. 1, 683-687 (1991); translation from Mat. Zametki 50, No. 1, 34-40 (1991).

MSC:

68Q42 Grammars and rewriting systems
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. L. Semenov, ?Algorithmic problems for power series and context-free grammars,? Dokl. Akad. Nauk SSSR,212, No. 1, 50-52 (1973). · Zbl 0322.68052
[2] An. A. Muchnik, ?Application of Semenov’s method to the analysis of the structure of context-free languages,? in: Semiotic Aspects of Formalization of Mental Activity [in Russian], VINITI, Moscow (1985), pp. 212-214.
[3] J. E. Hopcroft, ?On the equivalence and containment problems for context-free languages,? Math. Syst. Theor.,3, No. 2, 119-124 (1969). · Zbl 0179.02203 · doi:10.1007/BF01746517
[4] W. Brauer, Introduction to the Theory of Finite Automata [Russian translation], Radio i Svyaz’, Moscow (1987).
[5] H. Lalleman, Semigroups and Combinatorial Applications [Russian translation], Mir, Moscow (1985).
[6] A. V. Gladkii, ?The essential indeterminacy of context-free languages is not algorithmically recognizable,? Algebra Logika,4, No. 4, 53-64 (1965).
[7] K. Culik and J. Karhumäki, ?The equivalence of finite-valued transducers (on HDTOL languages) is decidable,? Theor. Comput. Sci.,47, 71-84 (1986). · Zbl 0621.68049 · doi:10.1016/0304-3975(86)90134-9
[8] E. Gurari and O. Ibarra, ?A note on finite-valued and finitely ambiguous transducers,? Math. Systems Theory,16, 61-66 (1983). · Zbl 0502.68022 · doi:10.1007/BF01744569
[9] A. Weber, ?A decomposition theorem for finite valued transducers and application to the equivalence problem,? unpub. ms. (1987).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.