×

Quelques problèmes ouverts en théorie des langages algébriques. (French) Zbl 0434.68056


MSC:

68Q45 Formal languages and automata
68-02 Research exposition (monographs, survey articles) pertaining to computer science
PDF BibTeX XML Cite
Full Text: EuDML

References:

[1] 1. A. V. AHO et J. D. ULLMAN, The Theory of Parsing, Translation and Compiling, vol. 1, Prentice Hall, 1972. MR408321 · Zbl 0264.68032
[2] 2. J. M. AUTEBERT, Opérations de cylindre et applications séquentielles gauches inverses, Acta Informatica, vol. 11, 1979, p. 241-258. Zbl0388.68076 · Zbl 0388.68076
[3] 3. J. M. AUTEBERT, L. BOASSON et G. COUSINEAU, A Note on 1-Locally-Linear Languages, Information and Control, vol. 37, 1978, p. 1-4. Zbl0377.68045 MR483732 · Zbl 0377.68045
[4] 4. Y. BAR-HILLEL, M. PERLES et E. SHAMIR, On Formal Properties of Simple Phrase Structure Grammars, Z. Phonetik., Sprach. Kommunikation Forsch., vol. 14, 1961, p. 143-172. Zbl0106.34501 MR151376 · Zbl 0106.34501
[5] 5. J. BEAUQUIER, Générateurs algébriques et systèmes de paires itérantes, Theoretical Computer Sc., vol. 8, 1979, p. 293-323. Zbl0408.68071 MR532474 · Zbl 0408.68071
[6] 6. J. BEAUQUIER, A Remark About the Syntactic Lemma, soumis à Mathematical Systems Theory.
[7] 7. L. BOASSON, Un critère de rationalité des langages algébriques. In Automata, Programming and Languages, M. NIVAT, éd., North Holland, 1972, p. 359-365. Zbl0263.68038 MR368487 · Zbl 0263.68038
[8] 8. L. BOASSON, Two Iteration Theorems for Some Families of Languages, J. Comput. System Sc., vol. 7, 1973, p. 583-596. Zbl0298.68053 MR386352 · Zbl 0298.68053
[9] 9. L. BOASSON, Langages algébriques, paires itérantes et transductions rationnelles, Theoretical Computer Sc., vol. 2, 1976, p. 209-223. Zbl0378.68037 MR441012 · Zbl 0378.68037
[10] 10. L. BOASSON, B. COURCELLE et M. NIVAT, A New Complexity Measure for Languages, in A Conference on Theoretical Computer Science, Waterloo, 1977, p. 130-138. Zbl0431.68077 MR495182 · Zbl 0431.68077
[11] 11. L. BOASSON, J. P. CRESTIN et M. NIVAT, Familles de langages translatables et fermées par crochet, Acta Informatica, vol. 2, 1973, p. 383-393. Zbl0311.68047 MR334584 · Zbl 0311.68047
[12] 12. L. BOASSON et M. NIVAT, Sur diverses familles de langages fermées par transductions rationnelles, Acta Informatica, vol. 2, 1973, p. 180-188. Zbl0242.68037 MR331873 · Zbl 0242.68037
[13] 13. L. BOASSON et M. NIVAT, Le cylindre des langages linéaires, Mathematical Systems Theory, vol. 11, 1977, p. 147-155. Zbl0352.68087 MR455561 · Zbl 0352.68087
[14] 14. L. BOASSON et S. HORVATH, On Languages Satisfying Ogden’s Lemma, R.A.I.R.O., Informatique Théorique, vol. 12, 1978, p. 201-202. Zbl0387.68054 MR510637 · Zbl 0387.68054
[15] 15. R. V. BOOK et S. A. GREIBACH, Quasi Realtime Languages, Mathematical Systems Theory, vol. 4, 1970, p. 97-111. Zbl0188.33102 MR276019 · Zbl 0188.33102
[16] 16. R. V. BOOK, M. NIVAT et M. PATERSON, Reversal Bounded Acceptors and Intersection of Linear Languages, S.I.A.M. J. Comput., vol. 3, 1974, p. 283-297. Zbl0292.68023 MR433992 · Zbl 0292.68023
[17] 17. W. J. CHANDLER, Abstract Families of Deterministic Languages, Proceedings du 1er A.C.M. Symposium of Theory on Computing, Marina del Rey, 1969, p. 21-30. · Zbl 1282.68153
[18] 18. N. CHOMSKY, Context-Free Grammars and Push-Down Storage, M.I.T. Res. Lab. Electron. Quart. Prog. Rep., vol. 65, 1962.
[19] 19. N. CHOMSKY et M. P. SCHÜTZENBERGER, The Algebraic Theory of Context-Free Languages, in Computer Programming and Formal Systems, North Holland, 1963, p. 118-161. Zbl0148.00804 MR152391 · Zbl 0148.00804
[20] 20. S. EILENBERG, Communication au congrès international des mathématiciens, Nice, 1970.
[21] 21. S. EILENBERG, Automata, Languages and Machines, vol. A, Academic Press, New York,, 1974. Zbl0317.94045 MR530382 · Zbl 0317.94045
[22] 22. C. C. ELGOT et J. F. MEZEI, On Relations Defined by Generalized Finite Automata, I.B.M. J. Res. Dev., vol. 9, 1962, p. 47-68. Zbl0135.00704 MR216903 · Zbl 0135.00704
[23] 23. R. J. EVEY, The Theory and Application of Push-Down Store Machines, Mathematical Linguistics and Automatic Translation, Harvard University, Computation Lab. Rep., N.S.F. 10, mai 1963. · Zbl 0196.52501
[24] 24. P. C. FISCHER, A. R. MEYER et A. L. ROSENBERG, Counter Machines and Counter Languages, Mathematical Systems Theory, vol. 2, 1968, p. 265-283. Zbl0165.32002 MR235932 · Zbl 0165.32002
[25] 25. R. W. FLOYD, On Ambiguity in Phrase-Structure Languages, Comm. Assoc. Gomput. Mach., vol. 5, 1962, p. 526-534. Zbl0227.68037 · Zbl 0227.68037
[26] 26. S. GINSBURG, Algebraic and Automata-Theoretic Properties of Formal Languages, North Holland, 1975. Zbl0325.68002 MR443446 · Zbl 0325.68002
[27] 27. S. GINSBURG, J. GOLDSTINE et S. A. GREIBACH, Uniformly Erasable AFL, J. Comput. System Sc., vol. 10, 1975, p. 165-182. Zbl0325.68042 MR391600 · Zbl 0325.68042
[28] 28. S. GINSBURG, J. GOLDSTINE et S. A. GREIBACH, Some Uniformly Erasable Families of Languages, Theoretical Computer Science, vol. 2, 1976, p. 29-44. Zbl0343.68033 MR411254 · Zbl 0343.68033
[29] 29. S. GINSBURG et S. A. GREIBACH, Deterministic Context Free Languages, Information and Control, vol. 9, 1966, p. 620-648. Zbl0145.00802 MR207486 · Zbl 0145.00802
[30] 30. S. GINSBURG et S. A. GREIBACH, Abstract Families of Languages, in Memoirs of the Amer. Math. Soc., vol. 87, 1969, p. 1-32. MR297491 · Zbl 0194.31402
[31] 31. S. GINSBURG et E. H. SPANIER, Derivation-Bounded Languages, J. Comp. Syst. Sc., vol. 2, 1968, p. 228-250. Zbl0176.16703 MR241201 · Zbl 0176.16703
[32] 32. A. GINZBURG, Algebraic Theory of Automata, Academic Press, New York, 1968. Zbl0195.02501 MR242679 · Zbl 0195.02501
[33] 33. J. GOLDSTINE, Substitution and Bounded Languages, J. Comput. System Sc, vol. 6, 1972, p. 9-29. Zbl0232.68030 MR309367 · Zbl 0232.68030
[34] 34. S. A. GREIBACH, Chains of Full AFL’s, Mathematical Systems Theory, vol. 4, 1970, p. 231-242. Zbl0203.30102 MR329324 · Zbl 0203.30102
[35] 35. S. A. GREIBACH, The Hardest Context Free Language, S.I.A.M. J. Comput., vol. 2, 1973, p. 304-310. Zbl0278.68073 MR334591 · Zbl 0278.68073
[36] 36. S. A. GREIBACH, Jump PDA’s and Hierarchies of Deterministic Context-Free Languages, S.I.A.M. J. Comput., vol. 3, 1974, p. 111-127. Zbl0288.68031 MR371155 · Zbl 0288.68031
[37] 37. I. HAVEL et M. HARRISON, Strict Deterministic Grammars, J. Comput. System Sc., vol. 7, 1973, p. 237-277. Zbl0261.68036 MR319415 · Zbl 0261.68036
[38] 38. J. E. HOPCROFT et A. J. KORENJAK, Simple Deterministic Languages, I.E.E.E. Conf. Rec. 7th Ann. Symp. Switching and Automata Theory, 1966, p. 36-46.
[39] 39. S. HORVÁTH, The Family of Languages Satisfying Bar Hillel’s Lemma, R.A.I.R.O.-Informatique théorique, vol. 12, 1978, p. 192-200. Zbl0387.68053 · Zbl 0387.68053
[40] 40. D. E. KNUTH, A Characterisation of Parenthesis Languages, Information and Control, vol. 11, 1967, p. 269-289. Zbl0196.01703 · Zbl 0196.01703
[41] 41. P. LANDWEBER, Three Theorems on Phrase-Structure Grammars of Type 1, Information and Control, vol. 6, 1963. Zbl0116.11702 · Zbl 0116.11702
[42] 42. M. LATTEUX, Langages commutatifs, Thèse Sc. Math, Université Lille-I, 1978. · Zbl 0387.68051
[43] 43. R. MACNAUGTHON, Parenthesis Grammars, J. Assoc. Comput. Mach., vol. 14, 1967, p. 490-500. Zbl0168.01206 · Zbl 0168.01206
[44] 44. M. NIVAT, Transductions des langages de Chomsky, Thèse Sc. Math., Paris, 1967. Zbl0313.68065 MR238633 · Zbl 0313.68065
[45] 45. W. OGDEN, A Helpful Result for Proving Inherent Ambiguity, Mathematical Systems Theory, vol. 2, 1967, p. 191-194. Zbl0175.27802 MR233645 · Zbl 0175.27802
[46] 46. R. J. PARIKH, On Context-Free Languages, J. Assoc Comput. Mach., vol, 13, 1968, p. 570-580. Zbl0154.25801 MR209093 · Zbl 0154.25801
[47] 47. J. F. PERROT, Introduction aux monoïdes syntactiques des langages algébriques, in Langages Algébriques, J. P. CRESTIN et M. NIVAT, éds., 1973, p. 167-222. Zbl0392.20047 MR519795 · Zbl 0392.20047
[48] 48. A. SALOMAA, Formal Languages, Academic Press, New York, 1973. Zbl0262.68025 MR438755 · Zbl 0262.68025
[49] 49. M. P. SCHÜTZENBERGER, Finite Counting Automata, Information and Control, vol. 5, 1962, p. 91-107. Zbl0118.12506 MR154774 · Zbl 0118.12506
[50] 50. M. P. SCHÜTZENBERGER, Sur les relations rationnelles entre monoïdes libres, Theoretical Computer Sc., vol. 3, 1976, p. 243-259. Zbl0358.68129 MR445927 · Zbl 0358.68129
[51] 51. E. SHAMIR, A Representation Theorem for Algebraic and Context Free Power Series in Non-Commuting Variables, Information and Control, vol. 11, 1967, p. 239-254. Zbl0165.02302 MR228297 · Zbl 0165.02302
[52] 52. R. E. STEARNS, Regularity Test for Push-Down Machines, Information and Control, vol. 11, 1967, p. 323-340. Zbl0155.01901 · Zbl 0155.01901
[53] 53. I. H. SUDBOROUGH, Note on Tape-Bounded Complexity Classes and Linear Context-Free Languages, J. Assoc. Comput. Mach., vol. 22, 1975, p. 499-500. Zbl0318.68048 MR378496 · Zbl 0318.68048
[54] 54. L. VALIANT, Regularity and Related Problems for Deterministic Push-Down Automata, J. Assoc. Comput. Mach., vol. 22, 1975, p. 1-10. Zbl0293.68046 MR690083 · Zbl 0293.68046
[55] 55. L. VALIANT, General Context-Free Recognition in Less than Cubic Time, J. Comput. System Sc., vol. 10, 1975, p. 308-315. Zbl0312.68042 MR428796 · Zbl 0312.68042
[56] 56. A. P. J. VAN DER WALTLocally-Linear Families of Languages, Information and Control, vol. 32, 1976, p. 27-32. Zbl0336.68031 MR411265 · Zbl 0336.68031
[57] 57. N. K. YNTEMA, Inclusion Relations Among Families of Context-Free Languages, Information and Control, vol. 10, 1967, p. 572-597. Zbl0207.31405 · Zbl 0207.31405
[58] 58. A. B. CREMERS et S. GINSBURG, Context Free Grammars Forms, in Automata, Languages and programming, 2nd I.C.A.L.P., Saarbrücken, 1974, Lecture Notes in Comput. Sc., n^\circ 14, p. 364-382. MR433995
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.