On the inclusion problem for finitely ambiguous rational trace languages

A. Bertoni; P. Massazza

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1998)

  • Volume: 32, Issue: 1-3, page 79-98
  • ISSN: 0988-3754

How to cite

top

Bertoni, A., and Massazza, P.. "On the inclusion problem for finitely ambiguous rational trace languages." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 32.1-3 (1998): 79-98. <http://eudml.org/doc/92581>.

@article{Bertoni1998,
author = {Bertoni, A., Massazza, P.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
language = {eng},
number = {1-3},
pages = {79-98},
publisher = {EDP-Sciences},
title = {On the inclusion problem for finitely ambiguous rational trace languages},
url = {http://eudml.org/doc/92581},
volume = {32},
year = {1998},
}

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
PB - EDP-Sciences
VL - 32
IS - 1-3
SP - 79
EP - 98
LA - eng
UR - http://eudml.org/doc/92581
ER -

References

top
  1. 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. Zbl0679.68132MR992783
  2. 2. J. BERSTEL, C. REUTENAUER, Rational series and their languages, Springer-Verlag, Berlin Heidelberg, 1988. Zbl0668.68005MR971022
  3. 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. Zbl0486.68079MR675445
  4. 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. Zbl0627.68060MR875858
  5. 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. Zbl0819.68070MR1313127
  6. 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. Zbl0754.68064MR1183586
  7. 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. MR1478997
  8. 8. N. CHOMSKY, M. P. SCHUETZENBERGER, The algebraic theory of context-free languages, Computer Programming and Formal Systems, North Holland, 1963, p. 118-161. Zbl0148.00804MR152391
  9. 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. MR1470025
  10. 10. P. FLAJOLET, Analytic Models and Ambiguity of Context-Free Languages, Theoretical Computer Science, 49 (1987), p. 283-309. Zbl0612.68069MR909335
  11. 11. H. FURSTENBERG, Algebraic functions over finite fields, Journal of Algebra, 7 (1967), p. 271-277. Zbl0175.03903MR215820
  12. 12. M. R. GAREY, D. S. JOHNSON, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, San Francisco, 1979. Zbl0411.68039MR519066
  13. 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. Zbl0638.68084MR895803
  14. 14. P. HENRICI, Applied and computational complex analysis, vol. 1, John Wiley Interscience, 1974. Zbl0313.30001MR372162
  15. 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. Zbl0365.68059MR461988
  16. 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. Zbl0900.68267MR1127183
  17. 17. L. LIPSHITZ, D-finite Power Series, Journal of Algebra, 122 (1989), p. 353-373. Zbl0695.12018MR999079
  18. 18. A. MAZURKIEWICZ, Concurrent program schemes and their interpretations, DAIMI Rep. PB-78, Aarhus Univ., 1977. 
  19. 19. A. SALOMAA, M. SOITTOLA, Automata-Theoretic Aspects of formal power series, Springer-Verlag, New York, 1978. Zbl0377.68039MR483721
  20. 20. M. P. SCHUETZENBERGER, On the definition of a family of automata, Information and Control, 4 (1961), p. 245-270. Zbl0104.00702MR135680
  21. 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. Zbl0779.20038
  22. 22. D. ZEILBERGER, A holonomic systems approach to special functions identities, J. Comput. Appl. Math. 32 (1990), p. 321-368. Zbl0738.33001MR1090884

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.