On the inclusion problem for finitely ambiguous rational trace languages

Bertoni, A.; Massazza, P.

Bertoni, A. ; Massazza, P.

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 32 (1998) no. 1-3, pp. 79-98.

@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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/item/ITA_1998__32_1-3_79_0/

Bibliographie
Cité par

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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