Generalized cancellation-and-permutation properties, regular languages and supports of rational series

 Access to full text

 Full (PDF)

1. 1. J. BERSTEL and C. REUTENAUER, Les séries rationnelles et leurs langages, Masson, Paris, 1984. Zbl0573.68037MR745968
2. 2. A. EHRENFEUCHT, R. PARIKH and G. ROZENBERG, Pumping Lemmas for Regular Sets, SIAM J. Comput., Vol. 10, 1981, pp. 536-541. Zbl0461.68081MR623064
3. 3. A. EHRENFEUCHT, D. HAUSSLER and G. ROZENBERG, On Regularity of Context-free Languages, Theoret. Comput. Sci. Vol. 27, 1983, pp. 311-332. Zbl0553.68044MR731068
4. 4. S. EILENGERG, Automota, Languages and Machines, Volumes A, B, Academic Press, New York, 1974. Zbl0317.94045
5. 5. M. HARRISON, Introduction to Formal Language Theory, Addison-Wesley, Reading, MA 1978. Zbl0411.68058MR526397
6. 6. K. HASHIGUSHI, Positive Pumping Conditions and Cancellation Conditions for Regular Languages, to be published. 
7. 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. Zbl0441.16002MR570720
8. 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. Zbl0374.20074MR473071
9. 9. J. JAFFE, A Necessary and Suffîcient Pumping Lemma for Regular Languages, Sigact News, 1948, pp. 48-49. Zbl0397.68084
10. 10. G. LALLEMENT, Semigroups and combinatorial applications, Wiley, New York, 1979. Zbl0421.20025MR530552
11. 11. M. LOTHAIRE, Combinatorics of Words, Addison-Wesley, Reading, MA 1983. Zbl0514.20045MR675953
12. 12. J. MYHILL, Finite Automata and the Representation of Events, WADD Technical Report 57-624, 1957, Wright-Patterson Air Force Base, Ohio, 45433. 
13. 13. A. NERODE, Linear Automata Transformations, Proc. Amer. Math. Soc., Vol. 9, 1958, pp. 541-544. Zbl0089.33403MR135681
14. 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. JFM52.0046.01
15. 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. Zbl0569.68059MR742708
16. 16. A. RESTIVO and C. REUTENAUER, On the Burnside Problem for Semigroups, J. Algebra, Vol. 89, 1984, pp. 102-104. Zbl0545.20051MR748230
17. 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. Zbl0578.68061MR773418
18. 18. A. RESTIVO and C. REUTENAUER, Rational Languages and the Burnside Problem, Theoret. Comput. Sci., Vol. 40, 1985, pp. 13-30. Zbl0597.68057MR828514
19. 19. A. SALOMAA and M. SOITTOLA, Automata Theoretic Aspects on Fromal Power Series, Springer, Berlin, 1978. Zbl0377.68039MR483721
20. 20. M. P. SCHUTZENBERGER, Finite Counting Automata, Inform. Control, Vol. 5, 1962, pp. 91-107. Zbl0118.12506MR154774
21. 21. A. I. SHIRSHOV, On rings with identity relations, Mat. Sb., Vol. 43, 1957, pp. 277-283 (in russian). Zbl0078.02402MR95192
22. 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. Zbl0564.20045MR910140