On a code problem concerning planar acyclic graphs

F. Bossut; B. Warin

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

  • Volume: 25, Issue: 3, page 205-218
  • ISSN: 0988-3754

How to cite

top

Bossut, F., and Warin, B.. "On a code problem concerning planar acyclic graphs." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 25.3 (1991): 205-218. <http://eudml.org/doc/92389>.

@article{Bossut1991,
author = {Bossut, F., Warin, B.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {unsolvability; code problem; connected planar; directed ordered acyclic graphs},
language = {eng},
number = {3},
pages = {205-218},
publisher = {EDP-Sciences},
title = {On a code problem concerning planar acyclic graphs},
url = {http://eudml.org/doc/92389},
volume = {25},
year = {1991},
}

TY - JOUR
AU - Bossut, F.
AU - Warin, B.
TI - On a code problem concerning planar acyclic graphs
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1991
PB - EDP-Sciences
VL - 25
IS - 3
SP - 205
EP - 218
LA - eng
KW - unsolvability; code problem; connected planar; directed ordered acyclic graphs
UR - http://eudml.org/doc/92389
ER -

References

top
  1. 1. A. ARNOLD and M. DAUCHET, Théorie des magmoïdes, RAIRO Inform. Théor. Appl., 1978, 12, 3, pp. 235-257. Zbl0391.68037MR510640
  2. 2. A. ARNOLD and M. DAUCHET, Théorie des magmoïdes, RAIRO Inform. Théor. Appl., 1979, 13, 2, pp. 135-154. Zbl0443.68053MR543937
  3. 3. F. BOSSUT and B. WARIN, Rationalité and reconnaissabilité dans des graphes acycliques, Ph. D., University of Lille-I, 1986. 
  4. 4. F. BOSSUT and B. WARIN, Problème de décision sur les dags, publication interne IT 107 du L.I.F.L., Université de Lille-I, Villeneuve-d'Ascq, France, 1987. 
  5. 5. M. DAUCHET, It is undecidable whether a finite set of trees is a code, publication interne IT 109 du L.I.F.L., Université de Lille-I, Villeneuve-d'Ascq, France, 1987. 
  6. 6. J. E. HOPCROFT and J. D. ULLMAN, Formal languages and their relation to automata, Addison Wesley, series in computer science an information processing, 1969. Zbl0196.01701MR237243
  7. 7. G. HOTZ, Eine Algegraisierung des Syntheseproblems von Schaltkreisen, 1965, EIK l, pp. 185-205, 209-231. Zbl0156.25504
  8. 8. T. KAMIMURA and G. SLUTZKI, Parallel and Two-Way Automata on Directed Ordered Acyclic Graphs, Inform. and Control, 1981, 49, pp. 10-51. Zbl0482.68051MR642475
  9. 9. LOECK, The Parsing for General Phrase-Structure Grammars, Inform. and Control, 1970, 16. pp. 443-464. Zbl0207.01601MR272567
  10. 10. M. NIVAT, Code d'arbres, presented to Journées Hispano-Françaises d'Informatique Théorique et Programmation coordonnées avec LANFOR 86, Barcelone, nov. 1986. 
  11. 11. M. NIVAT, Tree codes, Tapsoft 87, Pise, 1987. Zbl0798.68083
  12. 12. C. W. PATTERSON and A. A. SARDINAS, A Necessary and sufficient condition for the unique decomposition of coded messages, IRE intern. conv. Record, 1953, 8, pp. 104-108. 
  13. 13. C. P. SCHNORR, Transformational classes of grammar, Inform. and Control, 1969, 14, pp. 252-277. Zbl0184.28502MR249228

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.