Item request has been placed! ×
Item request cannot be made. ×
loading  Processing Request

Random Graph Generation in Context-Free Graph Languages

Item request has been placed! ×
Item request cannot be made. ×
loading   Processing Request
اقرأ أكثر حفظ في قائمتي
  • معلومة اضافية
    • الموضوع:
      2024
    • Collection:
      Computer Science
    • نبذة مختصرة :
      We present a method for generating random hypergraphs in context-free hypergraph languages. It is obtained by adapting Mairson's generation algorithm for context-free string grammars to the setting of hyperedge replacement grammars. Our main results are that for non-ambiguous hyperedge replacement grammars, the method generates hypergraphs uniformly at random and in quadratic time. We illustrate our approach by a running example of a hyperedge replacement grammar generating term graphs.
      Comment: In Proceedings DCM 2023, arXiv:2409.19298
    • الرقم المعرف:
      10.4204/EPTCS.408.7
    • الرقم المعرف:
      edsarx.2410.00541