Quelques problèmes ouverts en théorie des langages algébriques

 Access to full text

 Full (PDF)

1. 1. A. V. AHO et J. D. ULLMAN, The Theory of Parsing, Translation and Compiling, vol. 1, Prentice Hall, 1972. Zbl0264.68032MR408321
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
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.68045MR483732
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.34501MR151376
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.68071MR532474
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.68038MR368487
8. 8. L. BOASSON, Two Iteration Theorems for Some Families of Languages, J. Comput. System Sc., vol. 7, 1973, p. 583-596. Zbl0298.68053MR386352
9. 9. L. BOASSON, Langages algébriques, paires itérantes et transductions rationnelles, Theoretical Computer Sc., vol. 2, 1976, p. 209-223. Zbl0378.68037MR441012
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.68077MR495182
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.68047MR334584
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.68037MR331873
13. 13. L. BOASSON et M. NIVAT, Le cylindre des langages linéaires, Mathematical Systems Theory, vol. 11, 1977, p. 147-155. Zbl0352.68087MR455561
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.68054MR510637
15. 15. R. V. BOOK et S. A. GREIBACH, Quasi Realtime Languages, Mathematical Systems Theory, vol. 4, 1970, p. 97-111. Zbl0188.33102MR276019
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.68023MR433992
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. Zbl1282.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.00804MR152391
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.94045MR530382
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.00704MR216903
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. Zbl0196.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.32002MR235932
25. 25. R. W. FLOYD, On Ambiguity in Phrase-Structure Languages, Comm. Assoc. Gomput. Mach., vol. 5, 1962, p. 526-534. Zbl0227.68037
26. 26. S. GINSBURG, Algebraic and Automata-Theoretic Properties of Formal Languages, North Holland, 1975. Zbl0325.68002MR443446
27. 27. S. GINSBURG, J. GOLDSTINE et S. A. GREIBACH, Uniformly Erasable AFL, J. Comput. System Sc., vol. 10, 1975, p. 165-182. Zbl0325.68042MR391600
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.68033MR411254
29. 29. S. GINSBURG et S. A. GREIBACH, Deterministic Context Free Languages, Information and Control, vol. 9, 1966, p. 620-648. Zbl0145.00802MR207486
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. Zbl0194.31402MR297491
31. 31. S. GINSBURG et E. H. SPANIER, Derivation-Bounded Languages, J. Comp. Syst. Sc., vol. 2, 1968, p. 228-250. Zbl0176.16703MR241201
32. 32. A. GINZBURG, Algebraic Theory of Automata, Academic Press, New York, 1968. Zbl0195.02501MR242679
33. 33. J. GOLDSTINE, Substitution and Bounded Languages, J. Comput. System Sc, vol. 6, 1972, p. 9-29. Zbl0232.68030MR309367
34. 34. S. A. GREIBACH, Chains of Full AFL's, Mathematical Systems Theory, vol. 4, 1970, p. 231-242. Zbl0203.30102MR329324
35. 35. S. A. GREIBACH, The Hardest Context Free Language, S.I.A.M. J. Comput., vol. 2, 1973, p. 304-310. Zbl0278.68073MR334591
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.68031MR371155
37. 37. I. HAVEL et M. HARRISON, Strict Deterministic Grammars, J. Comput. System Sc., vol. 7, 1973, p. 237-277. Zbl0261.68036MR319415
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
40. 40. D. E. KNUTH, A Characterisation of Parenthesis Languages, Information and Control, vol. 11, 1967, p. 269-289. Zbl0196.01703
41. 41. P. LANDWEBER, Three Theorems on Phrase-Structure Grammars of Type 1, Information and Control, vol. 6, 1963. Zbl0116.11702
42. 42. M. LATTEUX, Langages commutatifs, Thèse Sc. Math, Université Lille-I, 1978. 
43. 43. R. MACNAUGTHON, Parenthesis Grammars, J. Assoc. Comput. Mach., vol. 14, 1967, p. 490-500. Zbl0168.01206
44. 44. M. NIVAT, Transductions des langages de Chomsky, Thèse Sc. Math., Paris, 1967. Zbl0313.68065MR238633
45. 45. W. OGDEN, A Helpful Result for Proving Inherent Ambiguity, Mathematical Systems Theory, vol. 2, 1967, p. 191-194. Zbl0175.27802MR233645
46. 46. R. J. PARIKH, On Context-Free Languages, J. Assoc Comput. Mach., vol, 13, 1968, p. 570-580. Zbl0154.25801MR209093
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.20047MR519795
48. 48. A. SALOMAA, Formal Languages, Academic Press, New York, 1973. Zbl0262.68025MR438755
49. 49. M. P. SCHÜTZENBERGER, Finite Counting Automata, Information and Control, vol. 5, 1962, p. 91-107. Zbl0118.12506MR154774
50. 50. M. P. SCHÜTZENBERGER, Sur les relations rationnelles entre monoïdes libres, Theoretical Computer Sc., vol. 3, 1976, p. 243-259. Zbl0358.68129MR445927
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.02302MR228297
52. 52. R. E. STEARNS, Regularity Test for Push-Down Machines, Information and Control, vol. 11, 1967, p. 323-340. Zbl0155.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.68048MR378496
54. 54. L. VALIANT, Regularity and Related Problems for Deterministic Push-Down Automata, J. Assoc. Comput. Mach., vol. 22, 1975, p. 1-10. Zbl0293.68046MR690083
55. 55. L. VALIANT, General Context-Free Recognition in Less than Cubic Time, J. Comput. System Sc., vol. 10, 1975, p. 308-315. Zbl0312.68042MR428796
56. 56. A. P. J. VAN DER WALTLocally-Linear Families of Languages, Information and Control, vol. 32, 1976, p. 27-32. Zbl0336.68031MR411265
57. 57. N. K. YNTEMA, Inclusion Relations Among Families of Context-Free Languages, Information and Control, vol. 10, 1967, p. 572-597. Zbl0207.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° 14, p. 364-382. MR433995

1. A. Ehrenfeucht, G. Rozenberg, On the separating power of EOL systems
2. Rockford Ross, Karl Winklmann, Repetitive strings are not context-free
3. A. Terlutte, Sur les centres de DOL-langages
4. L. Boasson, Non-générateurs algébriques et substitution
5. Jean Berstel, Some Recent Results on Squarefree Words