Loops in automata and HDTOL relations

Karel Culik II; Juhani Karhumäki

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

  • Volume: 24, Issue: 4, page 327-337
  • ISSN: 0988-3754

How to cite

top

Culik II, Karel, and Karhumäki, Juhani. "Loops in automata and HDTOL relations." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 24.4 (1990): 327-337. <http://eudml.org/doc/92361>.

@article{CulikII1990,
author = {Culik II, Karel, Karhumäki, Juhani},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {n-tape automata; HDTOL relation},
language = {eng},
number = {4},
pages = {327-337},
publisher = {EDP-Sciences},
title = {Loops in automata and HDTOL relations},
url = {http://eudml.org/doc/92361},
volume = {24},
year = {1990},
}

TY - JOUR
AU - Culik II, Karel
AU - Karhumäki, Juhani
TI - Loops in automata and HDTOL relations
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1990
PB - EDP-Sciences
VL - 24
IS - 4
SP - 327
EP - 337
LA - eng
KW - n-tape automata; HDTOL relation
UR - http://eudml.org/doc/92361
ER -

References

top
  1. [1] J. BERSTEL, Transductions and Context-Free Languages, Teubner, Stuttgart, 1979. Zbl0424.68040MR549481
  2. [2] M. BIRD, The Equivalence Problem for Deterministic two-tape Automata, J. Comput. Sci., Vol. 7, 1973, pp.218-236. Zbl0271.94039MR342290
  3. [3] K. CULIK II, A Purely Homomorphic Characterization of Recursively Enumerate Sets, J. Assoc. Comput. Mach., Vol. 6, 1979, pp.345-350. Zbl0395.68076MR528036
  4. [4] K. CULIK II and J. KARHUMÄKI, Systems of equations over a free Monoid and Ehrenfeucht's Conjecture, Discrete Math., Vol. 43, 1983, pp. 139-153. Zbl0528.68057MR685623
  5. [5] K. CULIK II and J. KARHUMÄKI, The Equivalence of Finite Valued Ttansducers (on HDTOL Languages) is Decidable, Theoret. Comput. Sci., Vol. 47, 1986, pp. 71-84. Zbl0621.68049MR871465
  6. [6] K. CULIK II and J. KARHUMÄKI, Systems of Equations Over a Finitely Generated free Monoid Having an Effectively Equivalent Finite Subsystem, Lecture Notes in Mathematics (to appear). Zbl0648.68084
  7. [7] K. CULIK II and J. KARHUMÄKI, HDTOL Matching of Computations of Multiple Automata, Acta Informatica (to appear). Zbl0689.68103
  8. [8] S. GINSBURG, The Matematical Theory of Context-Free Languages, McGraw Hill, New York, 1966. Zbl0184.28401MR211815
  9. [9] S. GINSBURG and E. H. SPANIER, AFL with the Semilinear Property, J of Comput. and System Sciences, Vol. 5, 1971, pp. 365-396. Zbl0235.68029MR339558
  10. [10] M. HARRISON, Introduction to Formal Langage Theory, Addison-Wesley, Reading, 1978. Zbl0411.68058MR526397
  11. [11] E. KINBER, The Inclusion Problem for Some Classes of Deterministic Multitape Automata, Theoret. Comput. Sci., Vol. 26, 1983, pp. 1-24. Zbl0523.68047MR726910
  12. [12] M. LATTEAUX, Intersections de languages algébriques bornés Acta Informatica, Vol., 11, 1979, pp. 233-240. Zbl0416.68064MR525751
  13. [13] H. R. LEWIS, A New Decidability Problem with Applications, Proceedings of 18th FOCS Conference, 1979, pp. 62-73. MR488960
  14. [14] M. RABIN and D. SCOTT, Finite Automata and their Decision Problems, I.B.M. J. Res. Develop., Vol. 3, 1959, pp. 114-125. Zbl0158.25404MR103795
  15. [15] G. ROZENBERG and A. SALOMAA, The Mathematical Theory of L Systems, Academic Press, New York, 1980. Zbl0508.68031MR561711

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.