Polynomial size test sets for commutative languages

Ismo Hakala; Juha Kortelainen

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

  • Volume: 31, Issue: 3, page 291-304
  • ISSN: 0988-3754

How to cite

top

Hakala, Ismo, and Kortelainen, Juha. "Polynomial size test sets for commutative languages." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 31.3 (1997): 291-304. <http://eudml.org/doc/92563>.

@article{Hakala1997,
author = {Hakala, Ismo, Kortelainen, Juha},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {commutative language},
language = {eng},
number = {3},
pages = {291-304},
publisher = {EDP-Sciences},
title = {Polynomial size test sets for commutative languages},
url = {http://eudml.org/doc/92563},
volume = {31},
year = {1997},
}

TY - JOUR
AU - Hakala, Ismo
AU - Kortelainen, Juha
TI - Polynomial size test sets for commutative languages
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1997
PB - EDP-Sciences
VL - 31
IS - 3
SP - 291
EP - 304
LA - eng
KW - commutative language
UR - http://eudml.org/doc/92563
ER -

References

top
  1. 1. J. ALBERT and K. CULIK II, Test sets for homomorphism équivalence on context free languages, Information and Control, 1980, 45, pp. 273-284. Zbl0453.68048MR590851
  2. 2. J. ALBERT, K. CULIK II and J. KARHUMÄKI, Test sets for context free languages and algebraic systems of equations over free monoid, Information and Control, 1982, 52, pp. 172-186. Zbl0522.68064MR701592
  3. 3. M. H. ALBERT and J. LAWRENCE, A proof of Ehrenfeucht's conjecture, Theoret. Comput. Sci., 1985, 41, pp. 121-123. Zbl0602.68066MR841029
  4. 4. J. ALBERT and D. WOOD, Checking sets, test sets rich languages and commutatively closed languages, Journal of Computer and System Sciences, 1983, 26, pp. 82-91. Zbl0507.68049MR699221
  5. 5. I. HAKALA and J. KORTELAINEN, On the system of word equations xi1 xi2...xim = yi1 yi2...y1n (i = 1, 2, ...) in a free monoid, Acta Inform., 1997, 34, pp. 217-230. Zbl0877.68073MR1465039
  6. 6. I. HAKALA and J. KORTELAINEN, On the system of word equations xo ui1 xo ui1 x1 ui2 x2 ui3 x3 = yo vi1 y1 vi2 y2 vi3 y3 (i = 0, 1, 2,...) in a free monoid, Theor. Comput Sci. (to appear). MR1708036
  7. 7. M. A. HARRISON, Introduction to Formal Language Theory, Addison-Wesley, Reading Massachusetts, 1978. Zbl0411.68058MR526397
  8. 8. J. KARHUMÄKI, W. PLANDOWSKI and W. RYTTER, Polynomial-size test sets for context-free languages, Lecture Notes in Computer Sciences, 1992, 623, pp. 53-64. Zbl0834.68065MR1250630
  9. 9. J. KARHUMÄKI, W. PLANDOWSKI and W. RYTTER, Polynomial-size test sets for context-free languages, Journal of Computer and System Sciences, 1995, 50, pp. 11-19. Zbl0834.68065MR1322629
  10. 10. J. KARHUMÄKI, W. PLANDOWSKI and S. JAROMINEK, Efficient construction of test sets for regular and context-free languages, Theor. Comp. Sci., 1993, 116, pp. 305-316. Zbl0793.68090MR1231947
  11. 11. M. LOTHAIRE, Combinatorics on Words, Addison-Wesley, Reading Massachusetts, 1983. Zbl0514.20045MR675953

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.