On the inclusion problem for finitely ambiguous rational trace languages
Bertoni, A. ; Massazza, P.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 32 (1998), p. 79-98 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1998-01-01
@article{ITA_1998__32_1-3_79_0,
     author = {Bertoni, A. and Massazza, P.},
     title = {On the inclusion problem for finitely ambiguous rational trace languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {32},
     year = {1998},
     pages = {79-98},
     mrnumber = {1657515},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1998__32_1-3_79_0}
}

Bertoni, A.; Massazza, P. On the inclusion problem for finitely ambiguous rational trace languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 32 (1998) pp. 79-98. http://gdmltest.u-ga.fr/item/ITA_1998__32_1-3_79_0/

1. I. J. J. Aalbersberg, H. J. Hoogeboom, Characterizations of the decidability of some problems for regular trace languages, Mathematical Systems Theory, 22 (1989), p. 1-19. | MR 992783 | Zbl 0679.68132

2. J. Berstel, C. Reutenauer, Rational series and their languages, Springer-Verlag, Berlin Heidelberg, 1988. | MR 971022 | Zbl 0668.68005

3. A. Bertoni, G. Mauri, N. Sabadini, Equivalence and membership problems for regular trace languages, Lectures Notes in Computer Sciences, 140 (1982), p. 61-72. | MR 675445 | Zbl 0486.68079

4. A. Bertoni, G. Mauri, N. Sabadini, Unambiguous regular trace languages, Proc. of the Coll. on Algebra, Combinatorics and Logic in Computer Science, Colloquia Mathematica Soc. J. Bolyay, North Holland, vol. 42 (1985), p. 113-123. | MR 875858 | Zbl 0627.68060

5. A. Bertoni, P. Massazza, A Parallel Algorithm for the Hadamard Product of Holonomic Formal Series, International Journal of Algebra and Computation, vol. 4, n° 4 (1994), p. 561-573. | MR 1313127 | Zbl 0819.68070

6. A. Bertoni, P. Massazza, N. Sabadini, Holonomic generating functions and context free languages, International Journal of Foundations of Computer Science, vol. 3, n° 2 (1992), p. 181-191. | MR 1183586 | Zbl 0754.68064

7. A. Bertoni, M. Goldwurm, G. Mauri, N. Sabadini, Counting Techniques for Inclusion, Equivalence and Membership Problems, in The Book of Traces (V. Diekert, G. Rozemberg eds.), World Scientific (1995), p. 131-163. | MR 1478997

8. N. Chomsky, M. P. Schuetzenberger, The algebraic theory of context-free languages, Computer Programming and Formal Systems, North Holland, 1963, p. 118-161. | MR 152391 | Zbl 0148.00804

9. V. Diekert, Y. Metivier, Partial Commutation and Traces, in Handbook of Formal Languages (G. Rozemberg, A. Salomaa eds.), vol. 3, Beyond Words, Springer (1997), p. 457-533. | MR 1470025

10. P. Flajolet, Analytic Models and Ambiguity of Context-Free Languages, Theoretical Computer Science, 49 (1987), p. 283-309. | MR 909335 | Zbl 0612.68069

11. H. Furstenberg, Algebraic functions over finite fields, Journal of Algebra, 7 (1967), p. 271-277. | MR 215820 | Zbl 0175.03903

12. M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, San Francisco, 1979. | MR 519066 | Zbl 0411.68039

13. A. Gibbons, W. Rytter, On the decidability of some problems about rational subsets of free partially commutative monoids, Theoretical Computer Science, 48 (1986) p. 329-337. | MR 895803 | Zbl 0638.68084

14. P. Henrici, Applied and computational complex analysis, vol. 1, John Wiley Interscience, 1974. | MR 372162 | Zbl 0313.30001

15. O. H. Ibarra, Reversal-bounded multicounter machines and their decision problems, Journal of the Association of Computing Machinery, vol. 25 (1978), p. 116-133. | MR 461988 | Zbl 0365.68059

16. R. M. Karp, V. Ramachandran, Parallel Algorithms for Shared-Memory Machines, in Handbook of theoretical computer science, J. van Leeuwen ed., Elsevier (1990), p. 871-941. | MR 1127183 | Zbl 0900.68267

17. L. Lipshitz, D-finite Power Series, Journal of Algebra, 122 (1989), p. 353-373. | MR 999079 | Zbl 0695.12018

18. A. Mazurkiewicz, Concurrent program schemes and their interpretations, DAIMI Rep. PB-78, Aarhus Univ., 1977.

19.A. Salomaa, M. Soittola, Automata-Theoretic Aspects of formal power series, Springer-Verlag, New York, 1978. | MR 483721 | Zbl 0377.68039

20. M. P. Schuetzenberger, On the definition of a family of automata, Information and Control, 4 (1961), p. 245-270. | MR 135680 | Zbl 0104.00702

21. S. Varricchio, On the decidability of the equivalence problem for partially commutative rational power series, LITP, Univ. Paris VII, Internal report 90.97, 1990.

22. D. Zeilberger, A holonomic systems approach to special functions identities, J. Comput. Appl. Math. 32 (1990), p. 321-368. | MR 1090884 | Zbl 0738.33001