Generalized cancellation-and-permutation properties, regular languages and supports of rational series
Jacob, Gérard
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 22 (1988), p. 461-486 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1988-01-01
@article{ITA_1988__22_4_461_0,
     author = {Jacob, G\'erard},
     title = {Generalized cancellation-and-permutation properties, regular languages and supports of rational series},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {22},
     year = {1988},
     pages = {461-486},
     mrnumber = {984587},
     zbl = {0664.68073},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1988__22_4_461_0}
}

Jacob, Gérard. Generalized cancellation-and-permutation properties, regular languages and supports of rational series. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 22 (1988) pp. 461-486. http://gdmltest.u-ga.fr/item/ITA_1988__22_4_461_0/

1. J. Berstel and C. Reutenauer, Les séries rationnelles et leurs langages, Masson, Paris, 1984. | MR 745968 | Zbl 0573.68037

2. A. Ehrenfeucht, R. Parikh and G. Rozenberg, Pumping Lemmas for Regular Sets, SIAM J. Comput., Vol. 10, 1981, pp. 536-541. | MR 623064 | Zbl 0461.68081

3. A. Ehrenfeucht, D. Haussler and G. Rozenberg, On Regularity of Context-free Languages, Theoret. Comput. Sci. Vol. 27, 1983, pp. 311-332. | MR 731068 | Zbl 0553.68044

4. S. Eilengerg, Automota, Languages and Machines, Volumes A, B, Academic Press, New York, 1974. | Zbl 0317.94045

5. M. Harrison, Introduction to Formal Language Theory, Addison-Wesley, Reading, MA 1978. | MR 526397 | Zbl 0411.68058

6. K. Hashigushi, Positive Pumping Conditions and Cancellation Conditions for Regular Languages, to be published.

7. G. Jacob, Un théorème de factorisation des produits d'endomorphismes de KN, J. of Algebra, Vol. 63, No. 2, 1980, pp. 389-412. | MR 570720 | Zbl 0441.16002

8. G. Jacob, La finitude des représentations linéaires des semi-groupes est décidable, J. of Algebra, Vol. 52, No.2, 1978, pp. 437-459. | MR 473071 | Zbl 0374.20074

9. J. Jaffe, A Necessary and Suffîcient Pumping Lemma for Regular Languages, Sigact News, 1948, pp. 48-49. | Zbl 0397.68084

10. G. Lallement, Semigroups and combinatorial applications, Wiley, New York, 1979. | MR 530552 | Zbl 0421.20025

11. M. Lothaire, Combinatorics of Words, Addison-Wesley, Reading, MA 1983. | MR 675953 | Zbl 0514.20045

12. J. Myhill, Finite Automata and the Representation of Events, WADD Technical Report 57-624, 1957, Wright-Patterson Air Force Base, Ohio, 45433.

13. A. Nerode, Linear Automata Transformations, Proc. Amer. Math. Soc., Vol. 9, 1958, pp. 541-544. | MR 135681 | Zbl 0089.33403

14. F. P. Ramsey, On a Problem of Formal Logic, The Foundations of Mathematics, Routledge and Kegan Paul, 1954, pp. 82-111 and reprinted from Proc. London Math. Soc., Ser 2, Vol. 30, 1928, pp. 338-384. | JFM 52.0046.01

15. A. Restivo and C. Reutenauer, Some Applications of a Theorem of Shirshov to Language Theory, Inform. and Control, Vol. 57, 1983, pp. 205-213. | MR 742708 | Zbl 0569.68059

16. A. Restivo and C. Reutenauer, On the Burnside Problem for Semigroups, J. Algebra, Vol. 89, 1984, pp. 102-104. | MR 748230 | Zbl 0545.20051

17. A. Restivo and C. Reutenauer, On Cancellation Properties of Languages which are Supports of Rational Power Series, J. Comput. System Sci., Vol. 29, 1984, pp. 153-159. | MR 773418 | Zbl 0578.68061

18. A. Restivo and C. Reutenauer, Rational Languages and the Burnside Problem, Theoret. Comput. Sci., Vol. 40, 1985, pp. 13-30. | MR 828514 | Zbl 0597.68057

19. A. Salomaa and M. Soittola, Automata Theoretic Aspects on Fromal Power Series, Springer, Berlin, 1978. | MR 483721 | Zbl 0377.68039

20. M. P. Schutzenberger, Finite Counting Automata, Inform. Control, Vol. 5, 1962, pp. 91-107. | MR 154774 | Zbl 0118.12506

21. A. I. Shirshov, On rings with identity relations, Mat. Sb., Vol. 43, 1957, pp. 277-283 (in russian). | MR 95192 | Zbl 0078.02402

22. H. Straubing, The burnside problem for semigroups of matrices, Combinatorics on Words, Progress and Perspectives, L. J. CUMMINGS, Ed., Academic Press, New York, 1983, pp. 279-295. | MR 910140 | Zbl 0564.20045