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

Autebert, J. M.; Beauquier, J.; Boasson, L.; Nivat, M.

Autebert, J. M. ; Beauquier, J. ; Boasson, L. ; Nivat, M.

RAIRO. Informatique théorique, Tome 13 (1979) no. 4, pp. 363-378

MR Zbl | 5 citations dans Numdam

@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. Informatique th\'eorique},
     pages = {363--378},
     year = {1979},
     publisher = {EDP Sciences},
     volume = {13},
     number = {4},
     mrnumber = {556958},
     zbl = {0434.68056},
     language = {fr},
     url = {https://www.numdam.org/item/ITA_1979__13_4_363_0/}
}

TY  - JOUR
AU  - Autebert, J. M.
AU  - Beauquier, J.
AU  - Boasson, L.
AU  - Nivat, M.
TI  - Quelques problèmes ouverts en théorie des langages algébriques
JO  - RAIRO. Informatique théorique
PY  - 1979
SP  - 363
EP  - 378
VL  - 13
IS  - 4
PB  - EDP Sciences
UR  - https://www.numdam.org/item/ITA_1979__13_4_363_0/
LA  - fr
ID  - ITA_1979__13_4_363_0
ER  -

%0 Journal Article
%A Autebert, J. M.
%A Beauquier, J.
%A Boasson, L.
%A Nivat, M.
%T Quelques problèmes ouverts en théorie des langages algébriques
%J RAIRO. Informatique théorique
%D 1979
%P 363-378
%V 13
%N 4
%I EDP Sciences
%U https://www.numdam.org/item/ITA_1979__13_4_363_0/
%G fr
%F 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. Informatique théorique, Tome 13 (1979) no. 4, pp. 363-378. https://www.numdam.org/item/ITA_1979__13_4_363_0/

Bibliographie
Cité par

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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