Double pushout graph rewriting
ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ, ಡಬಲ್ ಪುಶ್ಔಟ್ ಗ್ರಾಫ್ ಮರುಬರಹವು (ಅಥವಾ ಡಿಪಿಒ ಗ್ರಾಫ್ ಮರುಬರಹ) ಗ್ರಾಫ್ ಮರುಬರಹಕ್ಕೆ ಗಣಿತದ ಚೌಕಟ್ಟನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಇದನ್ನು "ಗ್ರಾಫ್-ವ್ಯಾಕರಣಃ ಒಂದು ಬೀಜಗಣಿತದ ವಿಧಾನ" (1973) ಎಂಬ ಲೇಖನದಲ್ಲಿ ಗ್ರಾಫ್ ಮರುಬರಹಕ್ಕೆ ಮೊದಲ ಬೀಜಗಣಿತದ ವಿಧಾನಗಳಲ್ಲಿ ಒಂದಾಗಿ ಪರಿಚಯಿಸಲಾಯಿತು. ಗ್ರಾಫ್ಗಳಲ್ಲದ ಮರುಬರಹ ರಚನೆಗಳನ್ನು ಅನುಮತಿಸಲು ಮತ್ತು ಇತರ ವಿಸ್ತರಣೆಗಳ ನಡುವೆ ನಕಾರಾತ್ಮಕ ಅಪ್ಲಿಕೇಶನ್ ಷರತ್ತುಗಳನ್ನು ನಿರ್ವಹಿಸಲು ಇದನ್ನು ಸಾಮಾನ್ಯೀಕರಿಸಲಾಗಿದೆ. ವ್ಯಾಖ್ಯಾನ ಡಿಪಿಒ ಗ್ರಾಫ್ ರೂಪಾಂತರ ವ್ಯವಸ್ಥೆಯು (ಅಥವಾ ಗ್ರಾಫ್ ವ್ಯಾಕರಣ) ಒಂದು ಸೀಮಿತ ಗ್ರಾಫ್ ಅನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ, ಇದು ಆರಂಭಿಕ ಸ್ಥಿತಿಯಾಗಿದೆ, ಮತ್ತು ಸೀಮಿತ ಗ್ರಾಫ್ಗಳು ಮತ್ತು ಗ್ರಾಫ್ ಹೋಮೋಮಾರ್ಫಿಸಮ್ಗಳ ವಿಭಾಗದಲ್ಲಿ ಲೇಬಲ್ ಮಾಡಲಾದ ವ್ಯಾಪ್ತಿಗಳ ಸೀಮಿತ ಅಥವಾ ಎಣಿಸಬಹುದಾದ ಗುಂಪನ್ನು ಒಳಗೊಂಡಿದೆ, ಇದು ವ್ಯುತ್ಪತ್ತಿಯ ನಿಯಮಗಳಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ. ನಿಯಮ ವ್ಯಾಪ್ತಿಯನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಏಕರೂಪತೆಗಳಿಂದ ಕೂಡಿದೆ ಎಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ, ಆದರೆ ವಿವರಗಳು ಬದಲಾಗಬಹುದು. ಮರುಬರಹವನ್ನು ಎರಡು ಹಂತಗಳಲ್ಲಿ ಮಾಡಲಾಗುತ್ತದೆಃ ಅಳಿಸುವಿಕೆ ಮತ್ತು ಸೇರ್ಪಡೆ. ಎಡಭಾಗದಿಂದ ಒಂದು ಹೊಂದಾಣಿಕೆಯ ನಂತರ, ಬಲಭಾಗದಲ್ಲಿರದ ನೋಡ್ಗಳು ಮತ್ತು ಅಂಚುಗಳನ್ನು ಅಳಿಸಲಾಗುತ್ತದೆ. ನಂತರ ಬಲಗೈಯನ್ನು ಅಂಟಿಸಲಾಗುತ್ತದೆ. ಗ್ಲುಯಿಂಗ್ ಗ್ರಾಫ್ಗಳು ವಾಸ್ತವವಾಗಿ ಗ್ರಾಫ್ಗಳ ವಿಭಾಗದಲ್ಲಿ ಪುಶ್ಔಟ್ ನಿರ್ಮಾಣವಾಗಿದೆ, ಮತ್ತು ಅಳಿಸುವಿಕೆಯು ಪುಶ್ಔಟ್ ಪೂರಕವನ್ನು ಕಂಡುಹಿಡಿಯುವಂತೆಯೇ ಇರುತ್ತದೆ, ಆದ್ದರಿಂದ ಈ ಹೆಸರು ಬಂದಿದೆ. ಡಬಲ್ ಪುಶ್ಔಟ್ ಗ್ರಾಫ್ ಮರುಬರಹವು ಸ್ಥಿರ ಗಾತ್ರ ಮತ್ತು ಸಂಯೋಜನೆಯ ಮಾದರಿಯನ್ನು ಕಂಡುಹಿಡಿಯುವ ಮತ್ತು ಬದಲಾಯಿಸುವ ಮೂಲಕ ಗ್ರಾಫ್ ರೂಪಾಂತರಗಳ ವಿವರಣೆಯನ್ನು ಅನುಮತಿಸುತ್ತದೆ, ಅಲ್ಲಿ ಮಾದರಿಯ ಭಾಗವನ್ನು ಸಂರಕ್ಷಿಸಬಹುದು. ನಿಯಮದ ಅನ್ವಯವು ಸಂಭಾವ್ಯವಾಗಿ ನಿರ್ಣಾಯಕವಲ್ಲಃ ಹಲವಾರು ವಿಭಿನ್ನ ಹೊಂದಾಣಿಕೆಗಳು ಸಾಧ್ಯವಿದೆ. ಇವು ಓವರ್ಲ್ಯಾಪ್ ಆಗಿರಬಾರದು, ಅಥವಾ ಸಂರಕ್ಷಿತ ವಸ್ತುಗಳನ್ನು ಮಾತ್ರ ಹಂಚಿಕೊಳ್ಳಬಹುದು, ಹೀಗಾಗಿ ಸಮಾನಾಂತರ ಸ್ವಾತಂತ್ರ್ಯ ಎಂದು ಕರೆಯಲ್ಪಡುವ ಒಂದು ರೀತಿಯ ಏಕಕಾಲೀನತೆಯನ್ನು ತೋರಿಸುತ್ತದೆ, ಅಥವಾ ಅವು ಹೊಂದಾಣಿಕೆಯಾಗದೇ ಇರಬಹುದು, ಈ ಸಂದರ್ಭದಲ್ಲಿ ಅಪ್ಲಿಕೇಶನ್ಗಳನ್ನು ಕೆಲವೊಮ್ಮೆ ಅನುಕ್ರಮವಾಗಿ ಕಾರ್ಯಗತಗೊಳಿಸಬಹುದು, ಅಥವಾ ಒಂದನ್ನು ಇನ್ನೊಂದನ್ನು ತಡೆಯಬಹುದು. ಇದನ್ನು ತಂತ್ರಾಂಶ ವಿನ್ಯಾಸ ಮತ್ತು ಪ್ರೋಗ್ರಾಮಿಂಗ್ಗಾಗಿ ಭಾಷೆಯಾಗಿ ಬಳಸಬಹುದು (ಸಾಮಾನ್ಯವಾಗಿ ಗ್ರಾಫ್ಗಳನ್ನು ಆಯ್ಕೆ ಮಾಡುವುದಕ್ಕಿಂತ ಶ್ರೀಮಂತ ರಚನೆಗಳ ಮೇಲೆ ಕೆಲಸ ಮಾಡುವ ರೂಪಾಂತರ). ಡಿಪಿಒ ಗ್ರಾಫ್ ಮರುಬರಹಕ್ಕೆ ಮುಕ್ತಾಯವು ಅನಿಶ್ಚಿತವಾಗಿದೆ ಏಕೆಂದರೆ ಪೋಸ್ಟ್ ಪತ್ರವ್ಯವಹಾರದ ಸಮಸ್ಯೆಯನ್ನು ಅದಕ್ಕೆ ಕಡಿಮೆ ಮಾಡಬಹುದು. ಡಿಪಿಒ ಗ್ರಾಫ್ ಮರುಬರಹವನ್ನು ಪೆಟ್ರಿ ನೆಟ್ಗಳ ಸಾಮಾನ್ಯೀಕರಣವೆಂದು ಪರಿಗಣಿಸಬಹುದು. ಡಿಪಿಒ ಮರುಬರಹವು ಯಾವ ವರ್ಗಗಳಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ ಎಂಬುದನ್ನು ವಿವರಿಸಲು ಸಾಮಾನ್ಯೀಕರಣ ಸೂತ್ರಗಳನ್ನು ಪ್ರಯತ್ನಿಸಲಾಗಿದೆ. ಒಂದು ಸಾಧ್ಯತೆಯೆಂದರೆ ಅಂಟು ವರ್ಗದ ಕಲ್ಪನೆ, ಇದು ಅನೇಕ ಮುಚ್ಚುವ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಸಹ ಹೊಂದಿದೆ. ಸಂಬಂಧಿತ ಕಲ್ಪನೆಗಳೆಂದರೆ ಎಚ್ಎಲ್ಆರ್ ವ್ಯವಸ್ಥೆಗಳು, ಅರೆ-ಅಂಟಿಕೊಳ್ಳುವ ವರ್ಗಗಳು ಮತ್ತು-ಅಂಟಿಕೊಳ್ಳುವ ವರ್ಗಗಳು, ಅಂಟಿಕೊಳ್ಳುವ ಎಚ್ಎಲ್ಆರ್ ವರ್ಗಗಳು. ಅಂಟಿಕೊಳ್ಳುವ ವರ್ಗ ಮತ್ತು ಎಚ್ಎಲ್ಆರ್ ವ್ಯವಸ್ಥೆಯ ಪರಿಕಲ್ಪನೆಗಳು ಸಂಬಂಧಿಸಿವೆ (ಸಹಉತ್ಪನ್ನಗಳೊಂದಿಗೆ ಅಂಟಿಕೊಳ್ಳುವ ವರ್ಗವು ಎಚ್ಎಲ್ಆರ್ ವ್ಯವಸ್ಥೆಯಾಗಿದೆ). ಉದಾಹರಣೆಗೆ, ಹೈಪರ್ಗ್ರಾಫ್, ಟೈಪ್ ಮಾಡಲಾದ ಗ್ರಾಫ್ ಮತ್ತು ಆಪಾದಿತ ಗ್ರಾಫ್ ಮರುಬರಹವನ್ನು ನಿರ್ವಹಿಸಬಹುದು ಏಕೆಂದರೆ ಅವುಗಳನ್ನು ಅಂಟಿಕೊಳ್ಳುವ ಎಚ್ಎಲ್ಆರ್ ವ್ಯವಸ್ಥೆಗಳಾಗಿ ಎರಕಹೊಯ್ದ ಮಾಡಬಹುದು. ಟಿಪ್ಪಣಿಗಳು ಗ್ರಾಫ್ ಕ್ರಮಾವಳಿಗಳು ಗ್ರಾಫ್ ಮರುಬರಹ