Quelques problèmes ouverts en théorie des langages algébriques
Autebert, J. M. ; Beauquier, J. ; Boasson, L. ; Nivat, M.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 13 (1979), p. 363-378 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{ITA_1979__13_4_363_0,
     author = {Autebert, J. M. and Beauquier, J. and Boasson, L. and Nivat, M.},
     title = {Quelques probl\`emes ouverts en th\'eorie des langages alg\'ebriques},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {13},
     year = {1979},
     pages = {363-378},
     mrnumber = {556958},
     zbl = {0434.68056},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/ITA_1979__13_4_363_0}
}

Autebert, J. M.; Beauquier, J.; Boasson, L.; Nivat, M. Quelques problèmes ouverts en théorie des langages algébriques. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 13 (1979) pp. 363-378. http://gdmltest.u-ga.fr/item/ITA_1979__13_4_363_0/

1. A. V. Aho et J. D. Ullman, The Theory of Parsing, Translation and Compiling, vol. 1, Prentice Hall, 1972. | MR 408321

2. J. M. Autebert, Opérations de cylindre et applications séquentielles gauches inverses, Acta Informatica, vol. 11, 1979, p. 241-258. | Zbl 0388.68076

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. | MR 483732 | Zbl 0377.68045

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. | MR 151376 | Zbl 0106.34501

5. J. Beauquier, Générateurs algébriques et systèmes de paires itérantes, Theoretical Computer Sc., vol. 8, 1979, p. 293-323. | MR 532474 | Zbl 0408.68071

6. J. Beauquier, A Remark About the Syntactic Lemma, soumis à Mathematical Systems Theory.

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. | MR 368487 | Zbl 0263.68038

8. L. Boasson, Two Iteration Theorems for Some Families of Languages, J. Comput. System Sc., vol. 7, 1973, p. 583-596. | MR 386352 | Zbl 0298.68053

9. L. Boasson, Langages algébriques, paires itérantes et transductions rationnelles, Theoretical Computer Sc., vol. 2, 1976, p. 209-223. | MR 441012 | Zbl 0378.68037

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. | MR 495182 | Zbl 0431.68077

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. | MR 334584 | Zbl 0311.68047

12. L. Boasson et M. Nivat, Sur diverses familles de langages fermées par transductions rationnelles, Acta Informatica, vol. 2, 1973, p. 180-188. | MR 331873 | Zbl 0242.68037

13. L. Boasson et M. Nivat, Le cylindre des langages linéaires, Mathematical Systems Theory, vol. 11, 1977, p. 147-155. | MR 455561 | Zbl 0352.68087

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. | Numdam | MR 510637 | Zbl 0387.68054

15. R. V. Book et S. A. Greibach, Quasi Realtime Languages, Mathematical Systems Theory, vol. 4, 1970, p. 97-111. | MR 276019 | Zbl 0188.33102

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. | MR 433992 | Zbl 0292.68023

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.

18. N. Chomsky, Context-Free Grammars and Push-Down Storage, M.I.T. Res. Lab. Electron. Quart. Prog. Rep., vol. 65, 1962.

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. | MR 152391 | Zbl 0148.00804

20. S. Eilenberg, Communication au congrès international des mathématiciens, Nice, 1970.

21. S. Eilenberg, Automata, Languages and Machines, vol. A, Academic Press, New York,, 1974. | MR 530382 | Zbl 0317.94045

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. | MR 216903 | Zbl 0135.00704

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.

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. | MR 235932 | Zbl 0165.32002

25. R. W. Floyd, On Ambiguity in Phrase-Structure Languages, Comm. Assoc. Gomput. Mach., vol. 5, 1962, p. 526-534. | Zbl 0227.68037

26. S. Ginsburg, Algebraic and Automata-Theoretic Properties of Formal Languages, North Holland, 1975. | MR 443446 | Zbl 0325.68002

27. S. Ginsburg, J. Goldstine et S. A. Greibach, Uniformly Erasable AFL, J. Comput. System Sc., vol. 10, 1975, p. 165-182. | MR 391600 | Zbl 0325.68042

28. S. Ginsburg, J. Goldstine et S. A. Greibach, Some Uniformly Erasable Families of Languages, Theoretical Computer Science, vol. 2, 1976, p. 29-44. | MR 411254 | Zbl 0343.68033

29. S. Ginsburg et S. A. Greibach, Deterministic Context Free Languages, Information and Control, vol. 9, 1966, p. 620-648. | MR 207486 | Zbl 0145.00802

30. S. Ginsburg et S. A. Greibach, Abstract Families of Languages, in Memoirs of the Amer. Math. Soc., vol. 87, 1969, p. 1-32. | MR 297491

31. S. Ginsburg et E. H. Spanier, Derivation-Bounded Languages, J. Comp. Syst. Sc., vol. 2, 1968, p. 228-250. | MR 241201 | Zbl 0176.16703

32. A. Ginzburg, Algebraic Theory of Automata, Academic Press, New York, 1968. | MR 242679 | Zbl 0195.02501

33. J. Goldstine, Substitution and Bounded Languages, J. Comput. System Sc, vol. 6, 1972, p. 9-29. | MR 309367 | Zbl 0232.68030

34. S. A. Greibach, Chains of Full AFL's, Mathematical Systems Theory, vol. 4, 1970, p. 231-242. | MR 329324 | Zbl 0203.30102

35. S. A. Greibach, The Hardest Context Free Language, S.I.A.M. J. Comput., vol. 2, 1973, p. 304-310. | MR 334591 | Zbl 0278.68073

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. | MR 371155 | Zbl 0288.68031

37. I. Havel et M. Harrison, Strict Deterministic Grammars, J. Comput. System Sc., vol. 7, 1973, p. 237-277. | MR 319415 | Zbl 0261.68036

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. 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. | Numdam | Zbl 0387.68053

40. D. E. Knuth, A Characterisation of Parenthesis Languages, Information and Control, vol. 11, 1967, p. 269-289. | Zbl 0196.01703

41. P. Landweber, Three Theorems on Phrase-Structure Grammars of Type 1, Information and Control, vol. 6, 1963. | Zbl 0116.11702

42. M. Latteux, Langages commutatifs, Thèse Sc. Math, Université Lille-I, 1978.

43. R. Macnaugthon, Parenthesis Grammars, J. Assoc. Comput. Mach., vol. 14, 1967, p. 490-500. | Zbl 0168.01206

44. M. Nivat, Transductions des langages de Chomsky, Thèse Sc. Math., Paris, 1967. | Numdam | MR 238633 | Zbl 0313.68065

45. W. Ogden, A Helpful Result for Proving Inherent Ambiguity, Mathematical Systems Theory, vol. 2, 1967, p. 191-194. | MR 233645 | Zbl 0175.27802

46. R. J. Parikh, On Context-Free Languages, J. Assoc Comput. Mach., vol, 13, 1968, p. 570-580. | MR 209093 | Zbl 0154.25801

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. | MR 519795 | Zbl 0392.20047

48. A. Salomaa, Formal Languages, Academic Press, New York, 1973. | MR 438755 | Zbl 0262.68025

49. M. P. Schützenberger, Finite Counting Automata, Information and Control, vol. 5, 1962, p. 91-107. | MR 154774 | Zbl 0118.12506

50. M. P. Schützenberger, Sur les relations rationnelles entre monoïdes libres, Theoretical Computer Sc., vol. 3, 1976, p. 243-259. | MR 445927 | Zbl 0358.68129

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. | MR 228297 | Zbl 0165.02302

52. R. E. Stearns, Regularity Test for Push-Down Machines, Information and Control, vol. 11, 1967, p. 323-340. | Zbl 0155.01901

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. | MR 378496 | Zbl 0318.68048

54. L. Valiant, Regularity and Related Problems for Deterministic Push-Down Automata, J. Assoc. Comput. Mach., vol. 22, 1975, p. 1-10. | MR 690083 | Zbl 0293.68046

55. L. Valiant, General Context-Free Recognition in Less than Cubic Time, J. Comput. System Sc., vol. 10, 1975, p. 308-315. | MR 428796 | Zbl 0312.68042

56. A. P. J. Van Der Walt Locally-Linear Families of Languages, Information and Control, vol. 32, 1976, p. 27-32. | MR 411265 | Zbl 0336.68031

57. N. K. Yntema, Inclusion Relations Among Families of Context-Free Languages, Information and Control, vol. 10, 1967, p. 572-597. | Zbl 0207.31405

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. | MR 433995