Critical pair (term rewriting)
[ಕಡತಃ ಕ್ರಿಟ್ಪೇರ್ svg.svg |thumb |400px |Triangle ಎರಡು ಮರುಬರಹ ನಿಯಮಗಳಾದ s → t (ಮೇಲಿನ ಸಾಲು, ಎಡ) ಮತ್ತು l → r (ಬಲ) ಗಳಿಂದ ಪಡೆದ ನಿರ್ಣಾಯಕ ಜೋಡಿಯ ರೇಖಾಚಿತ್ರ. ಪರ್ಯಾಯ σ ಉಪಪದವನ್ನು s|p ಅನ್ನು l ನೊಂದಿಗೆ ಸಂಯೋಜಿಸುತ್ತದೆ. ಇದರ ಪರಿಣಾಮವಾಗಿ ಮೇಲ್ಪದರ ಪದ sσ [lσ] p (ಕೆಳಗಿನ ಸಾಲು, ಮಧ್ಯ) ಅನ್ನು ಅನುಕ್ರಮವಾಗಿ tσ ಮತ್ತು sσ [rσ] p (ಕೆಳಗಿನ ಸಾಲು, ಎಡ ಮತ್ತು ಬಲ) ಎಂಬ ಪದಗಳಿಗೆ ಪುನಃ ಬರೆಯಬಹುದು. ಕೊನೆಯ ಎರಡು ಪದಗಳು ನಿರ್ಣಾಯಕ ಜೋಡಿಯನ್ನು ರೂಪಿಸುತ್ತವೆ. ಪುನಃ ಬರೆಯುವ ನಿಯಮವು ಸಂಯೋಜಿತವಾಗಿದ್ದರೆ, ಅವುಗಳನ್ನು ಅಂತಿಮವಾಗಿ ಸಾಮಾನ್ಯ ಪದಕ್ಕೆ ಪುನಃ ಬರೆಯಬಹುದು.] ಎರಡು ಮರುಬರಹ ನಿಯಮಗಳು ಎರಡು ವಿಭಿನ್ನ ಪದಗಳನ್ನು ನೀಡಲು ಅತಿಕ್ರಮಿಸಿದಾಗ ಒಂದು ನಿರ್ಣಾಯಕ ಜೋಡಿ ಪದದ ಮರುಬರಹ ವ್ಯವಸ್ಥೆಯಲ್ಲಿ ಉದ್ಭವಿಸುತ್ತದೆ. ಹೆಚ್ಚು ವಿವರವಾಗಿ ಹೇಳುವುದಾದರೆ, (ಟಿ1, ಟಿ2) ಒಂದು ನಿರ್ಣಾಯಕ ಜೋಡಿಯಾಗಿದ್ದು, ಟಿ ಎಂಬ ಪದವಿದ್ದರೆ, ಅದಕ್ಕೆ ಪುನಃ ಬರೆಯುವ ನಿಯಮದ ಎರಡು ವಿಭಿನ್ನ ಅನ್ವಯಿಕೆಗಳು (ಒಂದೇ ನಿಯಮವನ್ನು ವಿಭಿನ್ನವಾಗಿ ಅನ್ವಯಿಸಲಾಗುತ್ತದೆ, ಅಥವಾ ಎರಡು ವಿಭಿನ್ನ ನಿಯಮಗಳು) ಟಿ1 ಮತ್ತು ಟಿ2 ಎಂಬ ಪದಗಳನ್ನು ನೀಡುತ್ತವೆ. ವ್ಯಾಖ್ಯಾನಗಳು ನಿರ್ಣಾಯಕ ಜೋಡಿಯ ನಿಜವಾದ ವ್ಯಾಖ್ಯಾನವು ಸ್ವಲ್ಪ ಹೆಚ್ಚು ಒಳಗೊಂಡಿರುತ್ತದೆ ಏಕೆಂದರೆ ಇದು ಪರ್ಯಾಯವಾಗಿ ನಿರ್ಣಾಯಕ ಜೋಡಿಗಳಿಂದ ಪಡೆಯಬಹುದಾದ ಜೋಡಿಗಳನ್ನು ಹೊರತುಪಡಿಸುತ್ತದೆ ಮತ್ತು ಓವರ್ಲ್ಯಾಪ್ನ ಆಧಾರದ ಮೇಲೆ ಜೋಡಿಯನ್ನು ಓರಿಯಂಟ್ ಮಾಡುತ್ತದೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, ಒಂದು ಜೋಡಿ ಅತಿಕ್ರಮಿಸುವ ನಿಯಮಗಳಿಗೆ ಮತ್ತು, ಕೆಲವು ಖಾಲಿ-ಇಲ್ಲದ ಸಂದರ್ಭಕ್ಕೆ, ಮತ್ತು ಪದವು (ಅದು ವೇರಿಯೇಬಲ್ ಅಲ್ಲ) ಅತ್ಯಂತ ಸಾಮಾನ್ಯವಾದ ಕೆಲವು ಬದಲಿಗಳ ಅಡಿಯಲ್ಲಿ ಹೊಂದಿಕೆಯಾಗುತ್ತದೆ, ನಿರ್ಣಾಯಕ ಜೋಡಿ. ನಿರ್ಣಾಯಕ ಜೋಡಿಯ ಎರಡೂ ಬದಿಗಳು ಒಂದೇ ಪದಕ್ಕೆ ಇಳಿದಾಗ, ನಿರ್ಣಾಯಕ ಜೋಡಿಯನ್ನು ಒಮ್ಮುಖ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ನಿರ್ಣಾಯಕ ಜೋಡಿಯ ಒಂದು ಭಾಗವು ಇನ್ನೊಂದಕ್ಕೆ ಹೋಲುತ್ತದೆಯಾದರೆ, ನಿರ್ಣಾಯಕ ಜೋಡಿಯನ್ನು ಕ್ಷುಲ್ಲಕ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, ನಿಯಮಗಳೊಂದಿಗೆ ಪುನರ್ಬರಹ ವ್ಯವಸ್ಥೆಯಲ್ಲಿ {|-| f (g (x, y), z) | | → g (x, z) |-| g (x, y) | | → x, |} ಏಕೈಕ ನಿರ್ಣಾಯಕ ಜೋಡಿಯು λg (x, z), f (x, z) ω ಆಗಿದೆ. ಒಂದೇ ಮರುಬರಹ ನಿಯಮವನ್ನು ಅನ್ವಯಿಸುವ ಮೂಲಕ ಈ ಎರಡೂ ಪದಗಳನ್ನು f (g (x, y), z) ಎಂಬ ಪದದಿಂದ ಪಡೆಯಬಹುದು. ಮತ್ತೊಂದು ಉದಾಹರಣೆಯಾಗಿ, ಒಂದೇ ನಿಯಮದೊಂದಿಗೆ ಮರುಬರಹ ವ್ಯವಸ್ಥೆಯನ್ನು ಪರಿಗಣಿಸಿ {|-| f (x, y) | | → x. |-|} ಈ ನಿಯಮವನ್ನು f (f (x, x), x) ಎಂಬ ಪದಕ್ಕೆ ಎರಡು ವಿಭಿನ್ನ ರೀತಿಯಲ್ಲಿ ಅನ್ವಯಿಸುವ ಮೂಲಕ, (f (x, x), f (x, x)) ಒಂದು (ಕ್ಷುಲ್ಲಕ) ನಿರ್ಣಾಯಕ ಜೋಡಿ ಎಂದು ನಾವು ನೋಡುತ್ತೇವೆ. ಕ್ರಿಟಿಕಲ್ ಜೋಡಿ ಲೆಮ್ಮಾ ಸಂಗಮವು ಒಮ್ಮುಖವಾದ ನಿರ್ಣಾಯಕ ಜೋಡಿಗಳನ್ನು ಸ್ಪಷ್ಟವಾಗಿ ಸೂಚಿಸುತ್ತದೆಃ ಯಾವುದೇ ನಿರ್ಣಾಯಕ ಜೋಡಿ λ a, b λ ಉದ್ಭವಿಸಿದರೆ, ನಂತರ a ಮತ್ತು b ಸಾಮಾನ್ಯ ಕಡಿತವನ್ನು ಹೊಂದಿರುತ್ತವೆ ಮತ್ತು ಆದ್ದರಿಂದ ನಿರ್ಣಾಯಕ ಜೋಡಿ ಒಮ್ಮುಖವಾಗಿರುತ್ತದೆ. ಮರುಬರಹ ವ್ಯವಸ್ಥೆ ಎಂಬ ಪದವು ಒಗ್ಗೂಡಿಸದಿದ್ದರೆ, ನಿರ್ಣಾಯಕ ಜೋಡಿಗಳು ಒಮ್ಮುಖವಾಗದೇ ಇರಬಹುದು, ಆದ್ದರಿಂದ ನಿರ್ಣಾಯಕ ಜೋಡಿಗಳು ಸಂಗಮವು ವಿಫಲವಾಗುವ ಸಂಭಾವ್ಯ ಮೂಲಗಳಾಗಿವೆ. ವಿಮರ್ಶಾತ್ಮಕ ಜೋಡಿ ಲೆಮ್ಮಾ 'ಎಂಬ ಪದವು ಮರುಬರಹ ವ್ಯವಸ್ಥೆಯು ದುರ್ಬಲವಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ (ಅಕಾ. ಸ್ಥಳೀಯವಾಗಿ) ಎಲ್ಲಾ ನಿರ್ಣಾಯಕ ಜೋಡಿಗಳು ಒಮ್ಮುಖವಾಗಿದ್ದರೆ ಮಾತ್ರ ಒಗ್ಗೂಡುತ್ತವೆ. ಹೀಗಾಗಿ, ಒಂದು ಪದದ ಮರುಬರಹ ವ್ಯವಸ್ಥೆಯು ದುರ್ಬಲವಾಗಿ ಸಂಯೋಜಿತವಾಗಿದೆಯೇ ಎಂದು ಕಂಡುಹಿಡಿಯಲು, ಎಲ್ಲಾ ನಿರ್ಣಾಯಕ ಜೋಡಿಗಳನ್ನು ಪರೀಕ್ಷಿಸುವುದು ಮತ್ತು ಅವು ಒಮ್ಮುಖವಾಗಿವೆಯೇ ಎಂದು ನೋಡುವುದು ಸಾಕು. ಎರಡು ಪದಗಳು ಒಮ್ಮುಖವಾಗುತ್ತವೆಯೇ ಎಂದು ಅಲ್ಗಾರಿದಮಿಕ್ ಆಗಿ ಪರಿಶೀಲಿಸಬಹುದಾದ್ದರಿಂದ, ಒಂದು ಪದದ ಮರುಬರಹ ವ್ಯವಸ್ಥೆಯು ದುರ್ಬಲವಾಗಿ ಒಗ್ಗೂಡಿದೆಯೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂಬುದನ್ನು ಅಲ್ಗಾರಿದಮಿಕ್ ಆಗಿ ಕಂಡುಹಿಡಿಯಲು ಇದು ಸಾಧ್ಯವಾಗಿಸುತ್ತದೆ. ಫ್ರಾಂಜ್ ಬಾದರ್ ಮತ್ತು ಟೋಬಿಯಾಸ್ ನಿಪ್ಕೋವ್, ಟರ್ಮ್ ರಿವ್ರೈಟಿಂಗ್ ಅಂಡ್ ಆಲ್ ದಟ್, "ಕೇಂಬ್ರಿಡ್ಜ್ ಯೂನಿವರ್ಸಿಟಿ ಪ್ರೆಸ್, 1998 (ಬುಕ್ ವೆಬ್ಲಿಂಕ್) ರಿವ್ರೈಟಿಂಗ್ ಸಿಸ್ಟಮ್ಸ್.