Geodesic
On the inclusion problem for finitely ambiguous rational trace languages
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 32 (1998) no. 1-3, pp. 79-98.

Voir la notice de l'article provenant de la source Numdam

@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},
     pages = {79--98},
     publisher = {EDP-Sciences},
     volume = {32},
     number = {1-3},
     year = {1998},
     mrnumber = {1657515},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ITA_1998__32_1-3_79_0/}
}
TY  - JOUR
AU  - Bertoni, A.
AU  - Massazza, P.
TI  - On the inclusion problem for finitely ambiguous rational trace languages
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1998
SP  - 79
EP  - 98
VL  - 32
IS  - 1-3
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/item/ITA_1998__32_1-3_79_0/
LA  - en
ID  - ITA_1998__32_1-3_79_0
ER  - 
%0 Journal Article
%A Bertoni, A.
%A Massazza, P.
%T On the inclusion problem for finitely ambiguous rational trace languages
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1998
%P 79-98
%V 32
%N 1-3
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/item/ITA_1998__32_1-3_79_0/
%G en
%F 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) no. 1-3, pp. 79-98. http://geodesic.mathdoc.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. | Zbl | MR

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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