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},
     publisher = {EDP-Sciences},
     volume = {13},
     number = {4},
     year = {1979},
     mrnumber = {556958},
     zbl = {0434.68056},
     language = {fr},
     url = {http://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  - http://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 http://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. http://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. | MR | Zbl

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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