S2S (mathematics)
ಗಣಿತಶಾಸ್ತ್ರದಲ್ಲಿ, ಎಸ್2ಎಸ್ ಎಂಬುದು ಇಬ್ಬರು ಉತ್ತರಾಧಿಕಾರಿಗಳನ್ನು ಹೊಂದಿರುವ ಮೊನಾಡಿಕ್ ಸೆಕೆಂಡ್ ಆರ್ಡರ್ ಸಿದ್ಧಾಂತವಾಗಿದೆ. ಇದು ತಿಳಿದಿರುವ ಅತ್ಯಂತ ಅಭಿವ್ಯಕ್ತಿಶೀಲ ನೈಸರ್ಗಿಕ ನಿರ್ಣಾಯಕ ಸಿದ್ಧಾಂತಗಳಲ್ಲಿ ಒಂದಾಗಿದೆ, ಎಸ್2ಎಸ್ನಲ್ಲಿ ವ್ಯಾಖ್ಯಾನಿಸಬಹುದಾದ ಅನೇಕ ನಿರ್ಣಾಯಕ ಸಿದ್ಧಾಂತಗಳಿವೆ. 1969ರಲ್ಲಿ ರಾಬಿನ್ ಇದರ ನಿರ್ಣಾಯಕತೆಯನ್ನು ಸಾಬೀತುಪಡಿಸಿದರು. ಮೂಲಭೂತ ಗುಣಲಕ್ಷಣಗಳು ಎಸ್2ಎಸ್ನ ಮೊದಲ ಕ್ರಮಾಂಕದ ವಸ್ತುಗಳು ಸೀಮಿತ ಬೈನರಿ ತಂತಿಗಳಾಗಿವೆ. ಸೆಕೆಂಡ್ ಆರ್ಡರ್ ಆಬ್ಜೆಕ್ಟ್ಗಳು ಸೀಮಿತ ಬೈನರಿ ಸ್ಟ್ರಿಂಗ್ಗಳ ಅನಿಯಂತ್ರಿತ ಸೆಟ್ಗಳಾಗಿವೆ (ಅಥವಾ ಯೂನರಿ ಪ್ರಿಡಿಕೇಟ್ಗಳು). ಕೆಲವು ಗುಣಲಕ್ಷಣಗಳು ಮತ್ತು ಸಂಪ್ರದಾಯಗಳುಃ ಪೂರ್ವನಿಯೋಜಿತವಾಗಿ, ಸಣ್ಣ ಅಕ್ಷರಗಳು ಮೊದಲ ಕ್ರಮದ ವಸ್ತುಗಳನ್ನು ಮತ್ತು ದೊಡ್ಡ ಅಕ್ಷರಗಳು ಎರಡನೇ ಕ್ರಮದ ವಸ್ತುಗಳನ್ನು ಉಲ್ಲೇಖಿಸುತ್ತವೆ. ಸೆಟ್ಗಳ ಸೇರ್ಪಡೆಯು S2S ಅನ್ನು ಎರಡನೇ ಕ್ರಮದಲ್ಲಿ ಮಾಡುತ್ತದೆ, "ಮೊನಾಡಿಕ್" k> 1 ಗೆ k-ary ಪ್ರಿಡಿಕೇಟ್ ವೇರಿಯೇಬಲ್ಗಳ ಅನುಪಸ್ಥಿತಿಯನ್ನು ಸೂಚಿಸುತ್ತದೆ. s ಮತ್ತು t ತಂತಿಗಳ ಸಂಯೋಗವನ್ನು st ನಿಂದ ಸೂಚಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ಇದು ಸಾಮಾನ್ಯವಾಗಿ S2S ನಲ್ಲಿ ಲಭ್ಯವಿರುವುದಿಲ್ಲ, s → 0s ಸಹ ಲಭ್ಯವಿರುವುದಿಲ್ಲ. ತಂತಿಗಳ ನಡುವಿನ ಪೂರ್ವಪ್ರತ್ಯಯ ಸಂಬಂಧವನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು. ಸಮಾನತೆಯು ಪ್ರಾಚೀನವಾದುದು, ಅಥವಾ ಇದನ್ನು s = t ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ತಂತಿಗಳ ಸ್ಥಳದಲ್ಲಿ, n → 2n + 1 ಮತ್ತು n → 2n + 2 ಹೊಂದಿರುವ ನೈಸರ್ಗಿಕ ಸಂಖ್ಯೆಗಳನ್ನು ಬಳಸಬಹುದು (ಉದಾಹರಣೆಗೆ) ಆದರೆ ಬೇರೆ ಯಾವುದೇ ಕಾರ್ಯಾಚರಣೆಗಳಿಲ್ಲ. ಎಲ್ಲಾ ಬೈನರಿ ತಂತಿಗಳ ಗುಂಪನ್ನು ಕ್ಲೈನ್ ನಕ್ಷತ್ರವನ್ನು ಬಳಸಿಕೊಂಡು {0,1} * ನಿಂದ ಸೂಚಿಸಲಾಗುತ್ತದೆ. {0,1} * ನ ಆರ್ಬಿಟ್ರರಿ ಉಪಗುಂಪುಗಳನ್ನು ಕೆಲವೊಮ್ಮೆ ಮರಗಳೊಂದಿಗೆ ಗುರುತಿಸಲಾಗುತ್ತದೆ, ನಿರ್ದಿಷ್ಟವಾಗಿ {0,1}-ಲೇಬಲ್ ಮಾಡಿದ ಮರ {0,1} *; {0,1} * ಸಂಪೂರ್ಣ ಅನಂತ ಅವಳಿ ಮರವನ್ನು ರೂಪಿಸುತ್ತದೆ. ಸೂತ್ರದ ಸಂಕೀರ್ಣತೆಗಾಗಿ, ತಂತಿಗಳ ಮೇಲಿನ ಪೂರ್ವಪ್ರತ್ಯಯ ಸಂಬಂಧವನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಮೊದಲ ಕ್ರಮವೆಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ. ಇದು ಇಲ್ಲದೆ, ಎಲ್ಲಾ ಸೂತ್ರಗಳು δ12 ಸೂತ್ರಗಳಿಗೆ ಸಮನಾಗಿರುವುದಿಲ್ಲ. S2S ನಲ್ಲಿ ವ್ಯಕ್ತಪಡಿಸಬಹುದಾದ ಗುಣಲಕ್ಷಣಗಳಿಗೆ (ಎಲ್ಲಾ ಬೈನರಿ ತಂತಿಗಳ ಗುಂಪನ್ನು ಮರದಂತೆ ನೋಡುವುದು), ಪ್ರತಿ ನೋಡ್ಗೆ, ಎಡ ಸಬ್ಟ್ರೀ ಮತ್ತು ಬಲ ಸಬ್ಟ್ರೀ ಮತ್ತು ಉಳಿದವುಗಳ ನಡುವೆ O (1) ಬಿಟ್ಗಳನ್ನು ಮಾತ್ರ ಸಂವಹನ ಮಾಡಬಹುದು (ಸಂವಹನ ಸಂಕೀರ್ಣತೆಯನ್ನು ನೋಡಿ). ಸ್ಥಿರವಾದ k ಗೆ, ತಂತಿಗಳಿಂದ k ಗೆ ಒಂದು ಕಾರ್ಯ (ಅಂದರೆ. k) ಗಿಂತ ಕೆಳಗಿರುವ ನೈಸರ್ಗಿಕ ಸಂಖ್ಯೆಗಳನ್ನು ಒಂದೇ ಗುಂಪಿನಿಂದ ಸಂಕೇತಿಸಬಹುದು. ಇದಲ್ಲದೆ, s, t ಅನ್ನು ದ್ವಿಗುಣಗೊಳಿಸುವ t, t ನ ಪ್ರತಿಯೊಂದು ಅಕ್ಷರವು ಚುಚ್ಚುಮದ್ದು, ಮತ್ತು s ಂಡಲ {s01t: t bul {0,1} *} ಅನ್ನು S2S ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು. ಇದಕ್ಕೆ ತದ್ವಿರುದ್ಧವಾಗಿ, ಸಂವಹನ ಸಂಕೀರ್ಣತೆಯ ವಾದದಿಂದ, ಎಸ್1ಎಸ್ನಲ್ಲಿ (ಕೆಳಗೆ) ಒಂದು ಜೋಡಿ ಸೆಟ್ಗಳನ್ನು ಒಂದೇ ಸೆಟ್ನಿಂದ ಎನ್ಕೋಡ್ ಮಾಡಲಾಗುವುದಿಲ್ಲ. S2Sನ ದುರ್ಬಲತೆಗಳುಃ ದುರ್ಬಲ S2S (WS2S) ಗೆ ಎಲ್ಲಾ ಸೆಟ್ಗಳು ಸೀಮಿತವಾಗಿರಬೇಕು (ಕೋನಿಗ್ಸ್ ಲೆಮ್ಮಾವನ್ನು ಬಳಸಿಕೊಂಡು S2Sನಲ್ಲಿ ಮಿತಿಯನ್ನು ವ್ಯಕ್ತಪಡಿಸಬಹುದು ಎಂಬುದನ್ನು ಗಮನಿಸಿ). '1' ಸ್ಟ್ರಿಂಗ್ಗಳಲ್ಲಿ ಕಾಣಿಸುವುದಿಲ್ಲ ಎಂದು ಹೇಳುವ ಮೂಲಕ S1S ಅನ್ನು ಪಡೆಯಬಹುದು, ಮತ್ತು WS1S ಗೆ ಸಹ ಮಿತಿಯ ಅಗತ್ಯವಿರುತ್ತದೆ. WS1S ಸಹ ಪ್ರೆಸ್ಬರ್ಗರ್ ಅಂಕಗಣಿತವನ್ನು 2ರ ಘಾತಗಳಿಗೆ ಪೂರ್ವಸೂಚಿಯೊಂದಿಗೆ ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು, ಏಕೆಂದರೆ ಸೆಟ್ಗಳನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಬಹುದಾದ ಸೇರ್ಪಡೆಯೊಂದಿಗೆ ಮಿತಿಯಿಲ್ಲದ ಬೈನರಿ ಸಂಖ್ಯೆಗಳನ್ನು ಪ್ರತಿನಿಧಿಸಲು ಬಳಸಬಹುದು. ನಿರ್ಧಾರದ ಸಂಕೀರ್ಣತೆ S2S ನಿರ್ಣಾಯಕವಾಗಿದೆ, ಮತ್ತು S2S, S1S, WS2S, WS1Sಗಳಲ್ಲಿ ಪ್ರತಿಯೊಂದೂ ಘಾತಾಂಕಗಳ ರೇಖೀಯವಾಗಿ ಬೆಳೆಯುತ್ತಿರುವ ಸ್ಟ್ಯಾಕ್ಗೆ ಅನುಗುಣವಾಗಿ ಪೂರಕ ನಿರ್ಧಾರದ ಸಂಕೀರ್ಣತೆಯನ್ನು ಹೊಂದಿಲ್ಲ. ಲೋವರ್ ಬೌಂಡ್ಗೆ, σ11 WS1S ವಾಕ್ಯಗಳನ್ನು ಪರಿಗಣಿಸುವುದು ಸಾಕು. ಅಂಕಗಣಿತದ (ಅಥವಾ ಇತರ) ಗಣನೆಯನ್ನು ಪ್ರಸ್ತಾಪಿಸಲು ಸಿಂಗಲ್ ಸೆಕೆಂಡ್ ಆರ್ಡರ್ ಕ್ವಾಂಟಿಫೈಯರ್ ಅನ್ನು ಬಳಸಬಹುದು, ಯಾವ ಸಂಖ್ಯೆಗಳು ಸಮಾನವಾಗಿವೆ ಎಂಬುದನ್ನು ನಾವು ಪರೀಕ್ಷಿಸಬಹುದಾದರೆ ಇದನ್ನು ಮೊದಲ ಕ್ರಮಾಂಕದ ಕ್ವಾಂಟಿಫೈಯರ್ಗಳನ್ನು ಬಳಸಿ ಪರಿಶೀಲಿಸಬಹುದು. ಇದಕ್ಕಾಗಿ, ನಾವು 1. m ಸಂಖ್ಯೆಗಳನ್ನು ಸೂಕ್ತವಾಗಿ ಎನ್ಕೋಡ್ ಮಾಡಿದರೆ, ನಾವು ಬೈನರಿ ಪ್ರಾತಿನಿಧ್ಯವನ್ನು i1i2.im ಹೊಂದಿರುವ ಸಂಖ್ಯೆಯನ್ನು i1 1 i2 2. IM m ಎಂದು ಎನ್ಕೋಡ್ ಮಾಡಬಹುದು, ಮೊದಲು ಒಂದು ಗಾರ್ಡು ಇರುತ್ತದೆ. ಗಾರ್ಡ್ಗಳ ಪರೀಕ್ಷೆಯನ್ನು ವಿಲೀನಗೊಳಿಸುವ ಮೂಲಕ ಮತ್ತು ವೇರಿಯೇಬಲ್ ಹೆಸರುಗಳನ್ನು ಮರುಬಳಕೆ ಮಾಡುವ ಮೂಲಕ, ಬಿಟ್ಗಳ ಸಂಖ್ಯೆಯು ಘಾತಾಂಕಗಳ ಸಂಖ್ಯೆಯಲ್ಲಿ ರೇಖೀಯವಾಗಿರುತ್ತದೆ. ಮೇಲಿನ ಮಿತಿಯಲ್ಲಿ, ನಿರ್ಧಾರದ ವಿಧಾನವನ್ನು ಬಳಸಿಕೊಂಡು (ಕೆಳಗೆ), ಕೆ-ಪಟ್ಟು ಕ್ವಾಂಟಿಫೈಯರ್ ಪರ್ಯಾಯದೊಂದಿಗೆ ವಾಕ್ಯಗಳನ್ನು ವಾಕ್ಯದ ಉದ್ದದ ಕೆ + ಒ (1)-ಪಟ್ಟು ಘಾತಾಂಕಕ್ಕೆ (ಏಕರೂಪದ ಸ್ಥಿರಾಂಕಗಳೊಂದಿಗೆ) ಅನುಗುಣವಾದ ಸಮಯದಲ್ಲಿ ನಿರ್ಧರಿಸಬಹುದು. ಕೆಲವು ಮೂಲಭೂತ ಗುಣಲಕ್ಷಣಗಳು ಮತ್ತು ಇಂಡಕ್ಷನ್ ಸ್ಕೀಮಾದ ಮೂಲಕ ಆಕ್ಸಿಯೋಮ್ಯಾಟೈಸೇಶನ್ WS2S ಅನ್ನು ಆಕ್ಸಿಯೋಮ್ಯಾಟೈಸ್ ಮಾಡಬಹುದು. S2Sಅನ್ನು ಭಾಗಶಃ ಈ ರೀತಿಯಾಗಿ ಸ್ವಯಂಸಿದ್ಧಗೊಳಿಸಬಹುದುಃ (1) HE! s βt (t0 § s βt1 βs) (ಖಾಲಿ ಸ್ಟ್ರಿಂಗ್, ε ನಿಂದ ಸೂಚಿಸಲಾಗುತ್ತದೆ; HE! s ಎಂದರೆ "ಅನನ್ಯ s ಇದೆ") (2) βs, t βi βl {0,1} βj βl {0,1} (si = tj βs = t βi = j) (i ಮತ್ತು j ನ ಬಳಕೆಯು ಒಂದು ಸಂಕ್ಷೇಪಣವಾಗಿದೆ; i = j ಗೆ, 0 ಸಮನಾಗಿರುವುದಿಲ್ಲ 1) (3) βS (S (ε) βs (S (s) βS (s0) βS ಎಂದಿನಂತೆ, φ ಮುಕ್ತ ಅಸ್ಥಿರಗಳನ್ನು ತೋರಿಸದಿದ್ದರೆ, ನಾವು ಸ್ವಯಂಸಿದ್ಧಾಂತದ ಸಾರ್ವತ್ರಿಕ ಮುಚ್ಚುವಿಕೆಯನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತೇವೆ. ಸಮಾನತೆಯು ಮುನ್ಸೂಚನೆಗಳಿಗೆ ಪ್ರಾಚೀನವಾಗಿದ್ದರೆ, ಒಬ್ಬರು ವಿಸ್ತರಣೆಯನ್ನು ಸಹ ಸೇರಿಸುತ್ತಾರೆ S = T ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ಷ್ಣ ನಮಗೆ ಕಾಂಪ್ರಹೆನ್ಷನ್ ಇರುವುದರಿಂದ, ಇಂಡಕ್ಷನ್ ಒಂದು ಸ್ಕೀಮಾದ ಬದಲು ಒಂದೇ ಹೇಳಿಕೆಯಾಗಿರಬಹುದು. ಎಸ್1ಎಸ್ನ ಸದೃಶ ಸ್ವಯಂಸಿದ್ಧೀಕರಣವು ಪೂರ್ಣಗೊಂಡಿದೆ. ಆದಾಗ್ಯೂ, ಎಸ್2ಎಸ್ಗೆ, ಸಂಪೂರ್ಣತೆ ಮುಕ್ತವಾಗಿದೆ (2021ರಂತೆ). ಎಸ್1ಎಸ್ ಏಕರೂಪತೆಯನ್ನು ಹೊಂದಿದ್ದರೂ, ಯಾವುದೇ ಎಸ್2ಎಸ್ ವ್ಯಾಖ್ಯಾನಿಸಬಹುದಾದ (ನಿಯತಾಂಕಗಳನ್ನು ಸಹ ಅನುಮತಿಸುವ) ಆಯ್ಕೆಯ ಕಾರ್ಯವಿಲ್ಲ, ಅದು ಖಾಲಿ ಇಲ್ಲದ ಸೆಟ್ ಎಸ್ ಅನ್ನು ನೀಡಿದರೆ ಎಸ್ನ ಒಂದು ಅಂಶವನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ, ಮತ್ತು ಕಾಂಪ್ರಹೆನ್ಷನ್ ಸ್ಕೀಮಾಗಳನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಆಯ್ಕೆಯ ಸ್ವಯಂಸಿದ್ಧಾಂತದ ವಿವಿಧ ರೂಪಗಳೊಂದಿಗೆ ಹೆಚ್ಚಿಸಲಾಗುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಕೆಲವು ಸಮಾನತೆಯ ಆಟಗಳಿಗೆ ನಿರ್ಣಾಯಕ ಸ್ಕೀಮಾದೊಂದಿಗೆ ವಿಸ್ತರಿಸಿದಾಗ (1)-(4) ಪೂರ್ಣಗೊಳ್ಳುತ್ತದೆ. S2Sಅನ್ನು Π13 ವಾಕ್ಯಗಳಿಂದ ಸ್ವಯಂಸಿದ್ಧಗೊಳಿಸಬಹುದು (ತಂತಿಗಳ ಮೇಲಿನ ಪೂರ್ವಪ್ರತ್ಯಯ ಸಂಬಂಧವನ್ನು ಪ್ರಾಚೀನವಾಗಿ ಬಳಸಿ). ಆದಾಗ್ಯೂ, ಇದು ಸೀಮಿತವಾಗಿ ಸ್ವಯಂಸಿದ್ಧವಲ್ಲ, ಅಥವಾ ನಾವು ಇಂಡಕ್ಷನ್ ಸ್ಕೀಮಾ ಮತ್ತು ಇತರ ವಾಕ್ಯಗಳ ಸೀಮಿತ ಗುಂಪನ್ನು ಸೇರಿಸಿದರೂ (ಇದು Π12-CA0 ಗೆ ಅದರ ಸಂಪರ್ಕದಿಂದ ಅನುಸರಿಸುತ್ತದೆ) ಇದನ್ನು σ13 ವಾಕ್ಯಗಳಿಂದ ಸ್ವಯಂಸಿದ್ಧಗೊಳಿಸಲಾಗುವುದಿಲ್ಲ. ಪ್ರತಿ ಸೀಮಿತ k ಗೆ, ಮೂರು ಅಗಲ ≤ k (ಮತ್ತು ಅನುಗುಣವಾದ ಮರದ ವಿಭಜನೆ) ಯೊಂದಿಗೆ ಎಣಿಸಬಹುದಾದ ಗ್ರಾಫ್ಗಳ ಮೊನಾಡಿಕ್ ಸೆಕೆಂಡ್ ಆರ್ಡರ್ (MSO) ಸಿದ್ಧಾಂತವನ್ನು S2S ನಲ್ಲಿ ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು (ಕೊರ್ಸೆಲ್ನ ಪ್ರಮೇಯವನ್ನು ನೋಡಿ). ಉದಾಹರಣೆಗೆ, ಮರಗಳ ಎಂ. ಎಸ್. ಓ. ಸಿದ್ಧಾಂತವು (ರೇಖಾಚಿತ್ರಗಳಂತೆ) ಅಥವಾ ಸರಣಿ-ಸಮಾನಾಂತರ ರೇಖಾಚಿತ್ರಗಳು ನಿರ್ಣಾಯಕವಾಗಿವೆ. ಇಲ್ಲಿ (ಅಂದರೆ. ಸೀಮಿತ ಮರದ ಅಗಲಕ್ಕಾಗಿ), ನಾವು ಶೃಂಗಗಳ ಗುಂಪಿಗೆ (ಅಥವಾ ಅಂಚುಗಳಿಗೆ) ಸೀಮಿತತೆಯ ಪರಿಮಾಣಕವನ್ನು ಸಹ ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು, ಮತ್ತು ಒಂದು ಸೆಟ್ ಮಾಡ್ಯುಲೋದಲ್ಲಿ ಸ್ಥಿರ ಪೂರ್ಣಾಂಕದಲ್ಲಿ ಶೃಂಗಗಳನ್ನು (ಅಥವಾ ಅಂಚುಗಳನ್ನು) ಎಣಿಸಬಹುದು. ಲೆಕ್ಕವಿಲ್ಲದಷ್ಟು ಗ್ರಾಫ್ಗಳನ್ನು ಅನುಮತಿಸುವುದರಿಂದ ಸಿದ್ಧಾಂತವು ಬದಲಾಗುವುದಿಲ್ಲ. ಅಲ್ಲದೆ, ಹೋಲಿಕೆಗಾಗಿ, S1S ನಿರ್ಬಂಧಿತ ಪಥದ ಅಗಲದ ಸಂಪರ್ಕಿತ ರೇಖಾಚಿತ್ರಗಳನ್ನು ಅರ್ಥೈಸಬಲ್ಲದು. ಇದಕ್ಕೆ ವ್ಯತಿರಿಕ್ತವಾಗಿ, ಮಿತಿಯಿಲ್ಲದ ಮೂರು ಅಗಲದ ಪ್ರತಿ ಗ್ರಾಫ್ಗಳ ಗುಂಪಿಗೆ, ಅದರ ಅಸ್ತಿತ್ವವು (ಅಂದರೆ. 11) ನಾವು ಶೃಂಗಗಳು ಮತ್ತು ಅಂಚುಗಳೆರಡರಲ್ಲೂ ಭವಿಷ್ಯವಾಣಿಯನ್ನು ಅನುಮತಿಸಿದರೆ ಎಂಎಸ್ಒ ಸಿದ್ಧಾಂತವು ಅನಿಶ್ಚಿತವಾಗಿದೆ. ಹೀಗಾಗಿ, ಒಂದು ಅರ್ಥದಲ್ಲಿ, ಎಸ್2ಎಸ್ನ ನಿರ್ಣಾಯಕತೆಯು ಸಾಧ್ಯವಾದಷ್ಟು ಉತ್ತಮವಾಗಿದೆ. ಮಿತಿಯಿಲ್ಲದ ಮೂರು ಅಗಲದ ಗ್ರಾಫ್ಗಳು ದೊಡ್ಡ ಗ್ರಿಡ್ ಮೈನರ್ಗಳನ್ನು ಹೊಂದಿರುತ್ತವೆ, ಇದನ್ನು ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರವನ್ನು ಅನುಕರಿಸಲು ಬಳಸಬಹುದು. ಎಸ್2ಎಸ್ ಗೆ ಕಡಿತಗೊಳಿಸುವ ಮೂಲಕ, ಎಣಿಸಬಹುದಾದ ಕ್ರಮಗಳ ಎಂಎಸ್ಒ ಸಿದ್ಧಾಂತವು ನಿರ್ಣಾಯಕವಾಗಿದೆ, ಹಾಗೆಯೇ ಅವುಗಳ ಕ್ಲೀನ್-ಬ್ರೌವರ್ ಕ್ರಮಗಳೊಂದಿಗೆ ಎಣಿಸಬಹುದಾದ ಮರಗಳ ಎಂಎಸ್ಒ ಸಿದ್ಧಾಂತವು ನಿರ್ಣಾಯಕವಾಗಿದೆ. ಆದಾಗ್ಯೂ, (, <) ನ ಎಂಎಸ್ಒ ಸಿದ್ಧಾಂತವು ಅನಿಶ್ಚಿತವಾಗಿದೆ. ಆರ್ಡಿನಲ್ಸ್ <ω2 ನ MSO ಸಿದ್ಧಾಂತವು ನಿರ್ಣಾಯಕವಾಗಿದೆ; ω2 ಗೆ ನಿರ್ಣಾಯಕತೆಯು ZFC ಯಿಂದ ಸ್ವತಂತ್ರವಾಗಿದೆ (ಕಾನ್ (ZFC + ದುರ್ಬಲವಾಗಿ ಕಾಂಪ್ಯಾಕ್ಟ್ ಕಾರ್ಡಿನಲ್) ಎಂದು ಊಹಿಸಿಕೊಳ್ಳಿ). ಅಲ್ಲದೆ, ಆರ್ಡಿನಲ್ಗಳ ಮೇಲೆ ಮೊನಾಡಿಕ್ ಸೆಕೆಂಡ್ ಆರ್ಡರ್ ತರ್ಕವನ್ನು ಬಳಸಿಕೊಂಡು ಆರ್ಡಿನಲ್ ಅನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು, ಇದನ್ನು ಆರ್ಡಿನಲ್ ಸೇರ್ಪಡೆ ಮತ್ತು ಗುಣಾಕಾರದ ಮೂಲಕ ವ್ಯಾಖ್ಯಾನಿಸಬಹುದಾದ ನಿಯಮಿತ ಕಾರ್ಡಿನಲ್ಗಳಿಂದ ಪಡೆಯಬಹುದು. ಕೆಲವು ಮಾದರಿ ತರ್ಕಗಳ ನಿರ್ಣಾಯಕತೆಗೆ ಎಸ್2ಎಸ್ ಉಪಯುಕ್ತವಾಗಿದೆ, ಕ್ರಿಪ್ಕೆ ಶಬ್ದಾರ್ಥಗಳು ನೈಸರ್ಗಿಕವಾಗಿ ಮರಗಳಿಗೆ ಕಾರಣವಾಗುತ್ತವೆ. S2S + U (ಅಥವಾ ಕೇವಲ S1S + U) ಯು ಅನ್ಬೌಂಡಿಂಗ್ ಕ್ವಾಂಟಿಫೈಯರ್ ಆಗಿದ್ದರೆ-ಕೆಲವು ಅನಿಯಂತ್ರಿತವಾಗಿ ದೊಡ್ಡದಾದ ಫೈನೈಟ್ X ಗೆ UX ± (X) iff ± (X) ಹಿಡಿದಿಟ್ಟುಕೊಳ್ಳುತ್ತದೆ. ಆದಾಗ್ಯೂ, WS2S + U, ಅನಂತ ಮಾರ್ಗಗಳ ಮೇಲೆ ಪ್ರಮಾಣೀಕರಣದ ಹೊರತಾಗಿಯೂ, U ಅನ್ನು ಹೊಂದಿರದ S2S ಉಪಸೂತ್ರಗಳೊಂದಿಗೂ ಸಹ ನಿರ್ಣಾಯಕವಾಗಿದೆ. ಸೂತ್ರದ ಸಂಕೀರ್ಣತೆ ಬೈನರಿ ತಂತಿಗಳ ಒಂದು ಗುಂಪನ್ನು ಎಸ್2ಎಸ್ನಲ್ಲಿ ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು, ಅದು ನಿಯಮಿತವಾಗಿದ್ದರೆ (ಅಂದರೆ. ಇದು ಸಾಮಾನ್ಯ ಭಾಷೆಯನ್ನು ರೂಪಿಸುತ್ತದೆ). ಎಸ್1ಎಸ್ನಲ್ಲಿ, ಸೆಟ್ಗಳ ಮೇಲಿನ (ಯೂನರಿ) ವಿಶೇಷಣವು (ನಿಯತಾಂಕ-ಮುಕ್ತ) ವ್ಯಾಖ್ಯಾನಿಸಬಹುದಾದ ಒಂದು ω-ನಿಯಮಿತ ಭಾಷೆಯಾಗಿದೆ. S2S ಗೆ, 1 ಅನ್ನು ಹೊಂದಿರದ ತಂತಿಗಳ ಮೇಲೆ ಮಾತ್ರ ತಮ್ಮ ಮುಕ್ತ ಅಸ್ಥಿರಗಳನ್ನು ಬಳಸುವ ಸೂತ್ರಗಳಿಗೆ, ಅಭಿವ್ಯಕ್ತಿಯು S1S ಗೆ ಸಮಾನವಾಗಿರುತ್ತದೆ. ಪ್ರತಿ S2S ಸೂತ್ರ φ (S1,., Sk), (k ಫ್ರೀ ವೇರಿಯೇಬಲ್ಗಳೊಂದಿಗೆ) ಮತ್ತು ಬೈನರಿ ಸ್ಟ್ರಿಂಗ್ಗಳ ಸೀಮಿತ ಮರ T, φ (S1 θT,., Sk θT) ಅನ್ನು |T | ನಲ್ಲಿ ಸಮಯ ರೇಖೀಯವಾಗಿ ಲೆಕ್ಕ ಹಾಕಬಹುದು (ಕೊರ್ಸೆಲ್ಲೆಯ ಪ್ರಮೇಯವನ್ನು ನೋಡಿ), ಆದರೆ ಮೇಲೆ ತಿಳಿಸಿದಂತೆ, ಓವರ್ಹೆಡ್ ಅನ್ನು ಸೂತ್ರದ ಗಾತ್ರದಲ್ಲಿ ಘಾತೀಯವಾಗಿ ಪುನರಾವರ್ತಿಸಬಹುದು (ಹೆಚ್ಚು ನಿಖರವಾಗಿ, ಸಮಯ). S1S ಗೆ, ಪ್ರತಿ ಸೂತ್ರವು Δ11 ಸೂತ್ರಕ್ಕೆ ಮತ್ತು Π02 ಅಂಕಗಣಿತದ ಸೂತ್ರಗಳ ಬೂಲಿಯನ್ ಸಂಯೋಜನೆಗೆ ಸಮಾನವಾಗಿರುತ್ತದೆ. ಇದಲ್ಲದೆ, ಪ್ರತಿ S1S ಸೂತ್ರವು ಸೂತ್ರದ ನಿಯತಾಂಕಗಳ ಅನುಗುಣವಾದ ω-ಸ್ವಯಂಚಾಲಿತತೆಯಿಂದ ಸ್ವೀಕಾರಕ್ಕೆ ಸಮಾನವಾಗಿರುತ್ತದೆ. ಆಟೊಮ್ಯಾಟನ್ ಒಂದು ನಿರ್ಣಾಯಕ ಪ್ಯಾರಿಟಿ ಆಟೊಮ್ಯಾಟನ್ ಆಗಿರಬಹುದುಃ ಪ್ಯಾರಿಟಿ ಆಟೊಮ್ಯಾಟನ್ ಪ್ರತಿ ಸ್ಥಿತಿಗೆ ಪೂರ್ಣಾಂಕ ಆದ್ಯತೆಯನ್ನು ಹೊಂದಿರುತ್ತದೆ ಮತ್ತು ಅನಂತವಾಗಿ ಕಂಡುಬರುವ ಹೆಚ್ಚಿನ ಆದ್ಯತೆಯು ಬೆಸ (ಪರ್ಯಾಯವಾಗಿ, ಸಮ) ಎಂದು ಒಪ್ಪಿಕೊಳ್ಳುತ್ತದೆ. S2S ಗೆ, ಮರದ ಸ್ವಯಂಚಾಲಿತವನ್ನು ಬಳಸಿಕೊಂಡು (ಕೆಳಗೆ), ಪ್ರತಿ ಸೂತ್ರವು δ12 ಸೂತ್ರಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ. ಇದಲ್ಲದೆ, ಪ್ರತಿ S2S ಸೂತ್ರವು ಕೇವಲ ನಾಲ್ಕು ಕ್ವಾಂಟಿಫೈಯರ್ಗಳನ್ನು ಹೊಂದಿರುವ ಸೂತ್ರಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ, (ನಮ್ಮ ಔಪಚಾರಿಕತೆಯು ಪೂರ್ವಪ್ರತ್ಯಯ ಸಂಬಂಧ ಮತ್ತು ಉತ್ತರಾಧಿಕಾರಿ ಕಾರ್ಯಗಳೆರಡನ್ನೂ ಹೊಂದಿದೆ ಎಂದು ಭಾವಿಸಿ). S1S ಗೆ, ಮೂರು ಕ್ವಾಂಟಿಫೈಯರ್ಗಳು ಸಾಕಾಗುತ್ತವೆ, ಮತ್ತು WS2S ಮತ್ತು WS1S ಗೆ, ಎರಡು ಕ್ವಾಂಟಿಫೈಯರ್ಗಳು ಸಾಕಾಗುತ್ತವೆ; WS2S ಮತ್ತು WS1S ಗೆ ಇಲ್ಲಿ ಪೂರ್ವಪ್ರತ್ಯಯ ಸಂಬಂಧದ ಅಗತ್ಯವಿಲ್ಲ. ಆದಾಗ್ಯೂ, ಮುಕ್ತ ಎರಡನೇ ಕ್ರಮಾಂಕದ ಅಸ್ಥಿರಗಳೊಂದಿಗೆ, ಪ್ರತಿ S2S ಸೂತ್ರವನ್ನು ಎರಡನೇ ಕ್ರಮಾಂಕದ ಅಂಕಗಣಿತದಲ್ಲಿ ಕೇವಲ Π11 ಟ್ರಾನ್ಸ್ಫೈನೈಟ್ ಪುನರಾವರ್ತನೆಯ ಮೂಲಕ ವ್ಯಕ್ತಪಡಿಸಲಾಗುವುದಿಲ್ಲ (ಹಿಮ್ಮುಖ ಗಣಿತವನ್ನು ನೋಡಿ). RCA0 + (ಸ್ಕೀಮಾ) {τ: τ ಒಂದು ನಿಜವಾದ S2S ವಾಕ್ಯವಾಗಿದೆ} ಇದು (ಸ್ಕೀಮಾ) ಗೆ ಸಮಾನವಾಗಿದೆ {τ: τ ಎಂಬುದು Π12-CA0} ನಲ್ಲಿ ಸಾಬೀತುಪಡಿಸಬಹುದಾದ Π13 ವಾಕ್ಯವಾಗಿದೆ. ಒಂದು ಮೂಲ ಸಿದ್ಧಾಂತದ ಮೇಲೆ, ಸ್ಕೀಮಾಗಳು (ಸ್ಕೀಮಾ ಓವರ್ ಕೆ) βS βS βS βS βS β1 <. <αk Lα1 (S) βS1. βS1 Lαk (S) ಗೆ ಸಮನಾಗಿರುತ್ತದೆ, ಅಲ್ಲಿ L ಎಂಬುದು ರಚನಾತ್ಮಕ ಬ್ರಹ್ಮಾಂಡವಾಗಿದೆ (ದೊಡ್ಡ ಎಣಿಸಬಹುದಾದ ಆರ್ಡಿನಲ್ ಅನ್ನು ಸಹ ನೋಡಿ). ಸೀಮಿತ ಪ್ರಚೋದನೆಯ ಕಾರಣದಿಂದಾಗಿ, ಅಂತಹ ಪ್ರತಿಯೊಂದು ವಾಕ್ಯವು Π12-CA0 ಎಂದು ಸಾಬೀತುಪಡಿಸಬಹುದಾದರೂ, ಎಲ್ಲಾ ನಿಜ (ಪ್ರಮಾಣಿತ ನಿರ್ಧಾರ ಕಾರ್ಯವಿಧಾನದ ಅಡಿಯಲ್ಲಿ) Π13 S2S ಹೇಳಿಕೆಗಳು ನಿಜವೆಂದು Π12-CA0 ಸಾಬೀತುಪಡಿಸುವುದಿಲ್ಲ. ಇದಲ್ಲದೆ, ಎಸ್ ಮತ್ತು ಟಿ ಎಂಬ ಬೈನರಿ ತಂತಿಗಳ ಸೆಟ್ಗಳನ್ನು ನೀಡಿದರೆ, ಈ ಕೆಳಗಿನವುಗಳು ಸಮಾನವಾಗಿವೆಃ (1) ಎಸ್ ನಿಂದ ಗಣಿಸಬಹುದಾದ ಬೈನರಿ ತಂತಿಗಳ ಬಹುಪದ ಸಮಯದ ಕೆಲವು ಸೆಟ್ಗಳಿಂದ ಟಿ ಅನ್ನು ಎಸ್ 2 ಎಸ್ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು. (2) ಟಿ ಅನ್ನು ಕೆಲವು ಆಟಗಳಿಗೆ ಗೆಲ್ಲುವ ಸ್ಥಾನಗಳ ಸೆಟ್ನಿಂದ ಲೆಕ್ಕ ಹಾಕಬಹುದು, ಅದರ ಪ್ರತಿಫಲವು Π02 (ಎಸ್) ಸೆಟ್ಗಳ ಸೀಮಿತ ಬೂಲಿಯನ್ ಸಂಯೋಜನೆಯಾಗಿದೆ. (3) Tಯನ್ನು Sನಿಂದ ಅಂಕಗಣಿತದ μ-ಕ್ಯಾಲ್ಕುಲಸ್ನಲ್ಲಿ ವ್ಯಾಖ್ಯಾನಿಸಬಹುದು (ಅಂಕಗಣಿತದ ಸೂತ್ರಗಳು + ಕನಿಷ್ಠ ಸ್ಥಿರ-ಬಿಂದು ತರ್ಕ) (4) T ಕನಿಷ್ಠ β-ಮಾದರಿಯಲ್ಲಿದೆ (ಅಂದರೆ. ಒಂದು ω-ಮಾದರಿಯು ಅದರ ಸೆಟ್-ಸೈದ್ಧಾಂತಿಕ ಪ್ರತಿರೂಪವು ಪರಿವರ್ತನಶೀಲವಾಗಿದೆ) S ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ ಮತ್ತು Π12-CA0ನಲ್ಲಿನ ಎಲ್ಲಾ Π13 ಪರಿಣಾಮಗಳನ್ನು ತೃಪ್ತಿಪಡಿಸುತ್ತದೆ. ಎಸ್1ಎಸ್ ಮತ್ತು ಎಸ್2ಎಸ್ನ ಮಾದರಿಗಳು ಪ್ರಮಾಣಿತ ಮಾದರಿಯ ಜೊತೆಗೆ (ಇದು ಎಸ್1ಎಸ್ ಮತ್ತು ಎಸ್2ಎಸ್ನ ವಿಶಿಷ್ಟ ಎಂಎಸ್ಒ ಮಾದರಿಯಾಗಿದೆ), ಎಸ್1ಎಸ್ ಮತ್ತು ಎಸ್2ಎಸ್ಗಾಗಿ ಇತರ ಮಾದರಿಗಳಿವೆ, ಇವು ಡೊಮೇನ್ನ ಎಲ್ಲಾ ಉಪಗುಂಪುಗಳಿಗಿಂತ ಕೆಲವನ್ನು ಬಳಸುತ್ತವೆ (ಹೆಂಕಿನ್ ಶಬ್ದಾರ್ಥಶಾಸ್ತ್ರವನ್ನು ನೋಡಿ). ಪ್ರತಿ ಎಸ್ ω ಗೆ, ಎಸ್ ನಲ್ಲಿ ಪುನರಾವರ್ತಿತ ಸೆಟ್ಗಳು ಪ್ರಮಾಣಿತ ಎಸ್ 1 ಎಸ್ ಮಾದರಿಯ ಪ್ರಾಥಮಿಕ ಉಪ ಮಾದರಿಯನ್ನು ರೂಪಿಸುತ್ತವೆ, ಮತ್ತು ಟ್ಯೂರಿಂಗ್ ಜಾಯಿನ್ ಮತ್ತು ಟ್ಯೂರಿಂಗ್ ರಿಡ್ಯೂಸಿಬಲಿಟಿಯ ಅಡಿಯಲ್ಲಿ ಮುಚ್ಚಿದ ω ನ ಖಾಲಿ-ಅಲ್ಲದ ಉಪಗುಂಪುಗಳ ಪ್ರತಿ ಸಂಗ್ರಹಕ್ಕೂ ಒಂದೇ ಆಗಿರುತ್ತದೆ. ಇದು S1S ವ್ಯಾಖ್ಯಾನಿಸಬಹುದಾದ ಸೆಟ್ಗಳ ಸಾಪೇಕ್ಷ ಪುನರಾವರ್ತನೆಯಿಂದ ಮತ್ತು ಏಕರೂಪತೆಯಿಂದ ಅನುಸರಿಸುತ್ತದೆಃ-φ (s) ಅನ್ನು (s ನ ಕಾರ್ಯವಾಗಿ) φ ನ ನಿಯತಾಂಕಗಳಿಂದ ಮತ್ತು s ನ ಸೀಮಿತ ಗುಂಪಿಗೆ φ (s) ಮೌಲ್ಯಗಳಿಂದ ಲೆಕ್ಕ ಹಾಕಬಹುದು (ಅದರ ಗಾತ್ರವು φ ಗಾಗಿ ನಿರ್ಣಾಯಕ ಸ್ವಯಂಚಾಲಿತ ಸ್ಥಿತಿಯಲ್ಲಿನ ಸ್ಥಿತಿಗಳ ಸಂಖ್ಯೆಯಿಂದ ಸೀಮಿತವಾಗಿದೆ). - k ಮತ್ತು S ನ S ನ ಸೀಮಿತ ತುಣುಕನ್ನು ಆಯ್ಕೆ ಮಾಡುವ ಮೂಲಕ ಮತ್ತು ಪ್ರತಿ ವಿಸ್ತರಣೆಯ ಸಮಯದಲ್ಲಿ ಹೆಚ್ಚಿನ ಆದ್ಯತೆಯು k ಆಗಿರುತ್ತದೆ ಮತ್ತು ವಿಸ್ತರಣೆಯನ್ನು k ಗಿಂತ ಹೆಚ್ಚಿನ ಆದ್ಯತೆಗಳನ್ನು ಹೊಡೆಯದೆ φ ಅನ್ನು ತೃಪ್ತಿಪಡಿಸುವ S ಆಗಿ ಪೂರ್ಣಗೊಳಿಸಬಹುದು (ಇವುಗಳನ್ನು ಆರಂಭಿಕ S ಗೆ ಮಾತ್ರ ಅನುಮತಿಸಲಾಗಿದೆ). ಅಲ್ಲದೆ, ನಿಘಂಟಿನ ಪ್ರಕಾರ ಅತ್ಯಂತ ಚಿಕ್ಕದಾದ ಆಯ್ಕೆಗಳನ್ನು ಬಳಸುವ ಮೂಲಕ, φ 'ಮತ್ತು HE S φ (S) φ! S φ' (S) (ಅಂದರೆ. ಏಕರೂಪತೆ; φ ತೋರಿಸದ ಮುಕ್ತ ಅಸ್ಥಿರಗಳನ್ನು ಹೊಂದಿರಬಹುದು; φ 'ಎಂಬುದು φ ಸೂತ್ರವನ್ನು ಮಾತ್ರ ಅವಲಂಬಿಸಿರುತ್ತದೆ). ಎಸ್2ಎಸ್ನ ಕನಿಷ್ಠ ಮಾದರಿಯು ಬೈನರಿ ತಂತಿಗಳ ಮೇಲೆ ಎಲ್ಲಾ ಸಾಮಾನ್ಯ ಭಾಷೆಗಳನ್ನು ಒಳಗೊಂಡಿದೆ. ಇದು ಪ್ರಮಾಣಿತ ಮಾದರಿಯ ಪ್ರಾಥಮಿಕ ಉಪ-ಮಾದರಿಯಾಗಿದೆ, ಆದ್ದರಿಂದ ಎಸ್2ಎಸ್ ನಿಯತಾಂಕ-ಮುಕ್ತ ವ್ಯಾಖ್ಯಾನಿಸಬಹುದಾದ ಮರಗಳ ಗುಂಪೊಂದು ಖಾಲಿಯಾಗಿಲ್ಲದಿದ್ದರೆ, ಅದು ಸಾಮಾನ್ಯ ಮರವನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. ಒಂದು ಸಾಮಾನ್ಯ ಭಾಷೆಯನ್ನು ಸಾಮಾನ್ಯ {0,1}-ಲೇಬಲ್ ಮಾಡಲಾದ ಸಂಪೂರ್ಣ ಅನಂತ ಬೈನರಿ ಮರ ಎಂದೂ ಪರಿಗಣಿಸಬಹುದು (ತಂತಿಗಳ ಮೇಲೆ ಊಹೆಗಳೊಂದಿಗೆ ಗುರುತಿಸಲಾಗುತ್ತದೆ). ಆರಂಭಿಕ ಶೃಂಗದೊಂದಿಗೆ ಶೃಂಗ-ಲೇಬಲ್ ಮಾಡಲಾದ ಸೀಮಿತ ನಿರ್ದೇಶಿತ ಗ್ರಾಫ್ ಅನ್ನು ಉರುಳಿಸುವ ಮೂಲಕ ಅದನ್ನು ಪಡೆಯಲು ಸಾಧ್ಯವಾದರೆ ಲೇಬಲ್ ಮಾಡಲಾದ ಮರವು ನಿಯಮಿತವಾಗಿರುತ್ತದೆ; ಆರಂಭಿಕ ಶೃಂಗದಿಂದ ತಲುಪಬಹುದಾದ ಗ್ರಾಫ್ನಲ್ಲಿನ (ನಿರ್ದೇಶಿತ) ಚಕ್ರವು ಅನಂತ ಮರವನ್ನು ನೀಡುತ್ತದೆ. ಸಾಮಾನ್ಯ ಮರಗಳ ಈ ವ್ಯಾಖ್ಯಾನ ಮತ್ತು ಎನ್ಕೋಡಿಂಗ್ನೊಂದಿಗೆ, ಪ್ರತಿ ನಿಜವಾದ S2S ವಾಕ್ಯವು ಈಗಾಗಲೇ ಪ್ರಾಥಮಿಕ ಕಾರ್ಯದ ಅಂಕಗಣಿತದಲ್ಲಿ ಸಾಬೀತುಪಡಿಸಬಹುದಾಗಿದೆ. ಇದು ನಿಯತಕಾಲಿಕವಲ್ಲದ ಮರಗಳಾಗಿದ್ದು, ನಿರ್ಣಾಯಕತೆಗಾಗಿ (ಕೆಳಗೆ) ಪೂರ್ವಭಾವಿ ಗ್ರಹಿಕೆಯ ಅಗತ್ಯವಿರಬಹುದು. ಅನಿಯಮಿತವಾದವುಗಳಿವೆ (ಅಂದರೆ. ನಿಯಮಿತವಲ್ಲದ ಭಾಷೆಗಳನ್ನು ಹೊಂದಿರುವ) ಎಸ್1ಎಸ್ನ ಮಾದರಿಗಳು (ಮತ್ತು ಪ್ರಾಯಶಃ ಎಸ್2ಎಸ್) (ಪ್ರಮಾಣಿತ ಮೊದಲ ಕ್ರಮಾಂಕದ ಭಾಗದೊಂದಿಗೆ ಮತ್ತು ಇಲ್ಲದೆ) ಗಣಿಸಬಹುದಾದ ತೃಪ್ತಿ ಸಂಬಂಧದೊಂದಿಗೆ. ಆದಾಗ್ಯೂ, ಗ್ರಹಿಕೆ ಮತ್ತು ನಿರ್ಣಾಯಕತೆಯ ವೈಫಲ್ಯದಿಂದಾಗಿ ತಂತಿಗಳ ಪುನರಾವರ್ತಿತ ಸೆಟ್ಗಳ ಸೆಟ್ ಎಸ್ 2 ಎಸ್ ಮಾದರಿಯನ್ನು ರೂಪಿಸುವುದಿಲ್ಲ. ಎಸ್2ಎಸ್ನ ನಿರ್ಣಾಯಕತೆ ಪ್ರತಿ ಸೂತ್ರವು ಅನಿರ್ಧಾರಣೀಯ ಮರದ ಸ್ವಯಂಚಾಲಿತತೆಯಿಂದ ಸ್ವೀಕಾರಕ್ಕೆ ಸಮಾನವಾಗಿದೆ ಎಂದು ತೋರಿಸುವ ಮೂಲಕ ನಿರ್ಣಾಯಕತೆಯ ಪುರಾವೆಯಾಗಿದೆ (ಟ್ರೀ ಆಟೋಮ್ಯಾಟನ್ ಮತ್ತು ಇನ್ಫೈನೈಟ್-ಟ್ರೀ ಆಟೋಮ್ಯಾಟನ್ ನೋಡಿ). ಅನಂತ ಮರದ ಸ್ವಯಂಚಾಲಿತ ಯಂತ್ರವು ಮೂಲದಿಂದ ಪ್ರಾರಂಭವಾಗಿ ಮರವನ್ನು ಮೇಲಕ್ಕೆ ಚಲಿಸುತ್ತದೆ ಮತ್ತು ಪ್ರತಿ ಮರದ ಕೊಂಬೆಯು ಸ್ವೀಕರಿಸುವ ಐಎಫ್ಎಫ್ ಅನ್ನು ಸ್ವೀಕರಿಸುತ್ತದೆ. ನಿರ್ಧಿಷ್ಟವಲ್ಲದ ಮರದ ಸ್ವಯಂಚಾಲಿತ ಯಂತ್ರವು ಐಎಫ್ಎಫ್ ಆಟಗಾರ 1 ಗೆಲ್ಲುವ ತಂತ್ರವನ್ನು ಹೊಂದಿದೆ, ಅಲ್ಲಿ ಆಟಗಾರ 1 ಅನುಮತಿಸಲಾದ (ಪ್ರಸ್ತುತ ಸ್ಥಿತಿ ಮತ್ತು ಇನ್ಪುಟ್ಗಾಗಿ) ಹೊಸ ಸ್ಥಿತಿಗಳ ಜೋಡಿಯನ್ನು (ಪಿ0, ಪಿ1) ಆಯ್ಕೆ ಮಾಡಿಕೊಳ್ಳುತ್ತಾನೆ, ಆದರೆ ಆಟಗಾರ 2 ಶಾಖೆಯನ್ನು ಆಯ್ಕೆ ಮಾಡಿಕೊಳ್ಳುತ್ತಾನೆ, 0 ಅನ್ನು ಆಯ್ಕೆ ಮಾಡಿದರೆ ಪಿ0 ಗೆ ಮತ್ತು ಇಲ್ಲದಿದ್ದರೆ ಪಿ1 ಗೆ ಪರಿವರ್ತನೆಗೊಳ್ಳುತ್ತದೆ. ಸಹ-ನಿರ್ಣಾಯಕ ಸ್ವಯಂಚಾಲಿತ ಆಟಕ್ಕೆ, ಎಲ್ಲಾ ಆಯ್ಕೆಗಳು ಆಟಗಾರ 2 ರಿಂದ, ಆದರೆ ನಿರ್ಣಾಯಕ ಆಟಕ್ಕೆ, (p0, p1) ರಾಜ್ಯ ಮತ್ತು ಇನ್ಪುಟ್ನಿಂದ ನಿಗದಿಪಡಿಸಲಾಗುತ್ತದೆ; ಮತ್ತು ಆಟ ಸ್ವಯಂಚಾಲಿತ ಆಟಕ್ಕೆ, ಇಬ್ಬರು ಆಟಗಾರರು ಶಾಖೆ ಮತ್ತು ರಾಜ್ಯವನ್ನು ಹೊಂದಿಸಲು ಸೀಮಿತ ಆಟವನ್ನು ಆಡುತ್ತಾರೆ. ಒಂದು ಶಾಖೆಯ ಮೇಲಿನ ಸ್ವೀಕಾರವು ಶಾಖೆಯ ಮೇಲೆ ಅನಂತವಾಗಿ ಸಾಮಾನ್ಯವಾಗಿ ಕಂಡುಬರುವ ಸ್ಥಿತಿಗಳನ್ನು ಆಧರಿಸಿದೆ; ಪ್ಯಾರಿಟಿ ಆಟೋಮ್ಯಾಟಾವು ಇಲ್ಲಿ ಸಾಕಷ್ಟು ಸಾಮಾನ್ಯವಾಗಿದೆ. ಸೂತ್ರಗಳನ್ನು ಸ್ವಯಂಚಾಲಿತವಾಗಿ ಪರಿವರ್ತಿಸಲು, ಮೂಲ ಪ್ರಕರಣವು ಸುಲಭವಾಗಿದೆ, ಮತ್ತು ಅನಿರ್ದಿಷ್ಟತೆಯು ಅಸ್ತಿತ್ವವಾದದ ಕ್ವಾಂಟಿಫೈಯರ್ಗಳ ಅಡಿಯಲ್ಲಿ ಮುಚ್ಚುವಿಕೆಯನ್ನು ನೀಡುತ್ತದೆ, ಆದ್ದರಿಂದ ನಮಗೆ ಪೂರಕತೆಯ ಅಡಿಯಲ್ಲಿ ಮಾತ್ರ ಮುಚ್ಚುವ ಅಗತ್ಯವಿದೆ. ಸಮಾನತೆಯ ಆಟಗಳ ಸ್ಥಾನಿಕ ನಿರ್ಣಯವನ್ನು ಬಳಸುವುದು (ಇಲ್ಲಿ ನಮಗೆ ನಂಬಲಾಗದ ಗ್ರಹಿಕೆಯ ಅಗತ್ಯವಿದೆ), ಆಟಗಾರ 1 ರ ಗೆಲುವಿನ ಕಾರ್ಯತಂತ್ರದ ಅಸ್ತಿತ್ವವು ಆಟಗಾರನಿಗೆ 2 ಗೆಲುವಿನ ಕಾರ್ಯತಂತ್ರವನ್ನು ನೀಡುತ್ತದೆ, ಸಹ-ನಿರ್ಣಾಯಕವಲ್ಲದ ಮರದ ಸ್ವಯಂಚಾಲಿತತೆಯು ಅದರ ದೃಢತೆಯನ್ನು ಪರಿಶೀಲಿಸುತ್ತದೆ. ಸ್ವಯಂಚಾಲಿತ ಯಂತ್ರವನ್ನು ನಂತರ ನಿರ್ಣಾಯಕವಾಗಿಸಬಹುದು (ಇಲ್ಲಿ ನಾವು ಸ್ಥಿತಿಗಳ ಸಂಖ್ಯೆಯಲ್ಲಿ ಘಾತೀಯ ಹೆಚ್ಚಳವನ್ನು ಪಡೆಯುತ್ತೇವೆ), ಮತ್ತು ಹೀಗಾಗಿ ಎಸ್ನ ಅಸ್ತಿತ್ವವು ನಿರ್ಣಾಯಕವಲ್ಲದ ಸ್ವಯಂಚಾಲಿತ ಯಂತ್ರದ ಸ್ವೀಕಾರಕ್ಕೆ ಅನುರೂಪವಾಗಿದೆ. ನಿರ್ಣಾಯಕತೆಃ ZFCಯಲ್ಲಿ, ಬೋರೆಲ್ ಆಟಗಳನ್ನು ನಿರ್ಧರಿಸಲಾಗುತ್ತದೆ, ಮತ್ತು Π02 ಸೂತ್ರಗಳ ಬೂಲಿಯನ್ ಸಂಯೋಜನೆಗಳಿಗೆ (ಅನಿಯಂತ್ರಿತ ನೈಜ ನಿಯತಾಂಕಗಳೊಂದಿಗೆ) ನಿರ್ಣಾಯಕ ಪುರಾವೆಯು ಇಲ್ಲಿ ಪ್ರಸ್ತುತ ಸ್ಥಿತಿ ಮತ್ತು ಮರದ ಸ್ಥಾನದ ಮೇಲೆ ಮಾತ್ರ ಅವಲಂಬಿತವಾಗಿರುವ ಕಾರ್ಯತಂತ್ರವನ್ನು ನೀಡುತ್ತದೆ. ಆದ್ಯತೆಗಳ ಸಂಖ್ಯೆಯ ಮೇಲೆ ಪ್ರಚೋದನೆಯು ಸಾಕ್ಷಿಯಾಗಿದೆ. ಕೆ ಆದ್ಯತೆಗಳಿವೆ ಎಂದು ಭಾವಿಸಿ, ಹೆಚ್ಚಿನ ಆದ್ಯತೆಯು ಕೆ ಆಗಿದೆ, ಮತ್ತು ಕೆ ಆಟಗಾರ 2 ಕ್ಕೆ ಸರಿಯಾದ ಸಮಾನತೆಯನ್ನು ಹೊಂದಿದೆ. ಪ್ರತಿ ಸ್ಥಾನಕ್ಕೂ (ಟ್ರೀ ಪೊಸಿಷನ್ + ಸ್ಟೇಟ್) ಕನಿಷ್ಠ ಆರ್ಡಿನಲ್ α (ಯಾವುದಾದರೂ ಇದ್ದರೆ) ಅನ್ನು ನಿಯೋಜಿಸಿ, ಅಂದರೆ ಆಟಗಾರ 1 ಗೆಲ್ಲುವ ತಂತ್ರವನ್ನು ಹೊಂದಿದ್ದು, ಎಲ್ಲಾ ನಮೂದಿಸಿದ (ಒಂದು ಅಥವಾ ಹೆಚ್ಚಿನ ಹಂತಗಳ ನಂತರ) ಆದ್ಯತೆಯ k ಸ್ಥಾನಗಳು (ಯಾವುದಾದರೂ ಇದ್ದರೆ) <α ಲೇಬಲ್ಗಳನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಆರಂಭಿಕ ಸ್ಥಾನವನ್ನು ಲೇಬಲ್ ಮಾಡಿದರೆ ಆಟಗಾರ 1 ಗೆಲ್ಲಬಹುದುಃ ಪ್ರತಿ ಬಾರಿ ಆದ್ಯತೆಯ ಕೆ ಸ್ಥಿತಿಯನ್ನು ತಲುಪಿದಾಗ, ಆರ್ಡಿನಲ್ ಕಡಿಮೆಯಾಗುತ್ತದೆ, ಮತ್ತು ಹೆಚ್ಚುವರಿಯಾಗಿ, ಆಟಗಾರ 1 ಕೆ-1 ಆದ್ಯತೆಗಳಿಗಾಗಿ ತಂತ್ರವನ್ನು ಬಳಸಬಹುದು. ಸ್ಥಾನವನ್ನು ಲೇಬಲ್ ಮಾಡದಿದ್ದರೆ ಆಟಗಾರ 2 ಗೆಲ್ಲಬಹುದುಃ ಕೆ-1 ಆದ್ಯತೆಗಳ ನಿರ್ಣಾಯಕತೆಯಿಂದ, ಆಟಗಾರ 2 ಗೆಲ್ಲುವ ಅಥವಾ ಲೇಬಲ್ ಮಾಡದ ಆದ್ಯತೆಯ ಕೆ ಸ್ಥಿತಿಯನ್ನು ಪ್ರವೇಶಿಸುವ ತಂತ್ರವನ್ನು ಹೊಂದಿದೆ, ಈ ಸಂದರ್ಭದಲ್ಲಿ ಆಟಗಾರ 2 ಮತ್ತೆ ಆ ತಂತ್ರವನ್ನು ಬಳಸಬಹುದು. ತಂತ್ರವನ್ನು ಸ್ಥಾನಿಕವಾಗಿಸಲು (ಕೆ ಮೇಲೆ ಪ್ರಚೋದನೆಯ ಮೂಲಕ), ಸಹಾಯಕ ಆಟವನ್ನು ಆಡುವಾಗ, ಆಯ್ಕೆ ಮಾಡಿದ ಎರಡು ಸ್ಥಾನಿಕ ತಂತ್ರಗಳು ಒಂದೇ ಸ್ಥಾನಕ್ಕೆ ಕಾರಣವಾದರೆ, ಕೆಳಗಿನ α ಯೊಂದಿಗೆ ತಂತ್ರವನ್ನು ಮುಂದುವರಿಸಿ, ಅಥವಾ ಅದೇ α (ಅಥವಾ ಆಟಗಾರ 2 ಕ್ಕೆ) ಕಡಿಮೆ ಆರಂಭಿಕ ಸ್ಥಾನಕ್ಕಾಗಿ (ಆದ್ದರಿಂದ ನಾವು ತಂತ್ರವನ್ನು ಸೀಮಿತವಾಗಿ ಅನೇಕ ಬಾರಿ ಬದಲಾಯಿಸಬಹುದು). ಸ್ವಯಂಚಾಲಿತ ನಿರ್ಣಯಃ ಸಹ-ನಿರ್ಣಾಯಕವಲ್ಲದ ಮರದ ಸ್ವಯಂಚಾಲಿತವನ್ನು ನಿರ್ಧರಿಸಲು, ω-ಸ್ವಯಂಚಾಲಿತವನ್ನು ಪರಿಗಣಿಸುವುದು ಸಾಕು, ಶಾಖೆಯ ಆಯ್ಕೆಯನ್ನು ಇನ್ಪುಟ್ ಎಂದು ಪರಿಗಣಿಸುವುದು, ಸ್ವಯಂಚಾಲಿತವನ್ನು ನಿರ್ಧರಿಸುವುದು ಮತ್ತು ಅದನ್ನು ನಿರ್ಣಾಯಕ ಮರದ ಸ್ವಯಂಚಾಲಿತಕ್ಕಾಗಿ ಬಳಸುವುದು. ಇದು ನಿರ್ಧಿಷ್ಟವಲ್ಲದ ಮರದ ಸ್ವಯಂಚಾಲಿತತೆಗೆ ಎಡಕ್ಕೆ ಹೋಗುವ ನಿರ್ಧಾರವಾಗಿ ಕೆಲಸ ಮಾಡುವುದಿಲ್ಲ ಎಂಬುದನ್ನು ಗಮನಿಸಿ (ಅಂದರೆ. s → s0) ಸರಿಯಾದ ಶಾಖೆಯ ವಿಷಯಗಳನ್ನು ಅವಲಂಬಿಸಿರುತ್ತದೆ; ಅನಿರ್ದಿಷ್ಟವಾದಕ್ಕೆ ವ್ಯತಿರಿಕ್ತವಾಗಿ, ನಿರ್ಣಾಯಕ ಮರದ ಸ್ವಯಂಚಾಲಿತತೆಯು ನಿಖರವಾಗಿ ಖಾಲಿ ಇಲ್ಲದ ಸೆಟ್ಗಳನ್ನು ಸಹ ಸ್ವೀಕರಿಸಲು ಸಾಧ್ಯವಿಲ್ಲ. ನಿರ್ಣಾಯಕವಲ್ಲದ ω-ಸ್ವಯಂಚಾಲಿತ ಎಂ ಅನ್ನು ನಿರ್ಧರಿಸಲು (ಸಹ-ನಿರ್ಣಾಯಕಕ್ಕಾಗಿ, ಪೂರಕವನ್ನು ತೆಗೆದುಕೊಳ್ಳಿ, ನಿರ್ಣಾಯಕ ಸಮಾನತೆಯ ಸ್ವಯಂಚಾಲಿತತೆಯನ್ನು ಪೂರಕಗಳ ಅಡಿಯಲ್ಲಿ ಮುಚ್ಚಲಾಗಿದೆ ಎಂದು ಗಮನಿಸಿ), ನಾವು ಪ್ರತಿ ನೋಡ್ನೊಂದಿಗೆ ಎಂನ ಸಂಭವನೀಯ ಸ್ಥಿತಿಗಳ ಗುಂಪನ್ನು ಸಂಗ್ರಹಿಸುವ ಸಫ್ರಾ ಮರವನ್ನು ಬಳಸಬಹುದು, ಮತ್ತು ಹೆಚ್ಚಿನ ಆದ್ಯತೆಯ ಸ್ಥಿತಿಗಳನ್ನು ತಲುಪುವ ಆಧಾರದ ಮೇಲೆ ನೋಡ್ ರಚನೆ ಮತ್ತು ಅಳಿಸುವಿಕೆಯನ್ನು ಬಳಸಬಹುದು. ವಿವರಗಳಿಗಾಗಿ, ನೋಡಿ ಅಥವಾ. ಸ್ವೀಕಾರದ ನಿರ್ಣಾಯಕತೆಃ ಖಾಲಿ ಮರದ ನಿರ್ಣಾಯಕವಲ್ಲದ ಸಮಾನತೆಯ ಸ್ವಯಂಚಾಲಿತತೆಯಿಂದ ಸ್ವೀಕಾರವು ಸೀಮಿತ ಗ್ರಾಫ್ ಜಿ ಮೇಲಿನ ಸಮಾನತೆಯ ಆಟಕ್ಕೆ ಅನುರೂಪವಾಗಿದೆ. ಮೇಲಿನ ಸ್ಥಾನಿಕ (ಸ್ಮರಣೆಯಿಲ್ಲದ) ನಿರ್ಣಾಯಕತೆಯನ್ನು ಬಳಸಿಕೊಂಡು, ಇದನ್ನು ನಾವು ಲೂಪ್ ಅನ್ನು ತಲುಪಿದಾಗ ಕೊನೆಗೊಳ್ಳುವ ಸೀಮಿತ ಆಟದಿಂದ ಅನುಕರಿಸಬಹುದು, ಲೂಪ್ನಲ್ಲಿನ ಹೆಚ್ಚಿನ ಆದ್ಯತೆಯ ಸ್ಥಿತಿಯನ್ನು ಆಧರಿಸಿದ ಗೆಲುವಿನ ಸ್ಥಿತಿಯೊಂದಿಗೆ. ಬುದ್ಧಿವಂತ ಆಪ್ಟಿಮೈಸೇಶನ್ ಕ್ವಾಸಿಪೋಲಿನೋಮಿಯಲ್ ಟೈಮ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ನೀಡುತ್ತದೆ, ಇದು ಆದ್ಯತೆಗಳ ಸಂಖ್ಯೆಯು ಸಾಕಷ್ಟು ಕಡಿಮೆಯಾದಾಗ ಬಹುಪದೀಯ ಸಮಯವಾಗಿದೆ (ಇದು ಸಾಮಾನ್ಯವಾಗಿ ಆಚರಣೆಯಲ್ಲಿ ಸಂಭವಿಸುತ್ತದೆ). ಮರಗಳ ಸಿದ್ಧಾಂತಃ ಮರಗಳ ಮೇಲೆ ಎಂಎಸ್ಒ ತರ್ಕದ ನಿರ್ಣಾಯಕತೆಗಾಗಿ (ಅಂದರೆ. ಮರಗಳಾಗಿರುವ ಗ್ರಾಫ್ಗಳು), ಮೊದಲ ಕ್ರಮಾಂಕದ ವಸ್ತುಗಳಿಗೆ ಸೀಮಿತತೆ ಮತ್ತು ಮಾಡ್ಯುಲರ್ ಎಣಿಕೆಯ ಕ್ವಾಂಟಿಫೈಯರ್ಗಳೊಂದಿಗೂ ಸಹ, ನಾವು ಎಣಿಸಬಹುದಾದ ಮರಗಳನ್ನು ಸಂಪೂರ್ಣ ಬೈನರಿ ಮರದಲ್ಲಿ ಅಳವಡಿಸಬಹುದು ಮತ್ತು S2S ನ ನಿರ್ಣಾಯಕತೆಯನ್ನು ಬಳಸಬಹುದು. ಉದಾಹರಣೆಗೆ, ನೋಡ್ s ಗೆ, ನಾವು ಅದರ ಮಕ್ಕಳನ್ನು s1, s01, s001, ಇತ್ಯಾದಿಗಳಿಂದ ಪ್ರತಿನಿಧಿಸಬಹುದು. ಲೆಕ್ಕವಿಲ್ಲದಷ್ಟು ಮರಗಳಿಗೆ, ನಾವು ಶೇಲಾ-ಸ್ಟಪ್ ಪ್ರಮೇಯವನ್ನು (ಕೆಳಗೆ) ಬಳಸಬಹುದು. ನಾವು ಕಾರ್ಡಿನಲಿಟಿ ω1 ಹೊಂದಿರುವ ಸೆಟ್ ಫಸ್ಟ್ ಆರ್ಡರ್ ಆಬ್ಜೆಕ್ಟ್ಗಳಿಗೆ ಮತ್ತು ಕಾರ್ಡಿನಲಿಟಿ ω2 ಗಾಗಿ ಪ್ರಿಡಿಕೇಟ್ ಅನ್ನು ಕೂಡ ಸೇರಿಸಬಹುದು, ಮತ್ತು ಹೀಗೆ ಅನಂತ ನಿಯಮಿತ ಕಾರ್ಡಿನಲ್ಗಳಿಗೆ. ಸುತ್ತುವರಿದ ಮರದ ಅಗಲದ ರೇಖಾಚಿತ್ರಗಳನ್ನು ಮರಗಳನ್ನು ಬಳಸಿ ಅರ್ಥೈಸಿಕೊಳ್ಳಬಹುದು, ಮತ್ತು ಅಂಚುಗಳ ಮೇಲೆ ಮುನ್ಸೂಚನೆಗಳಿಲ್ಲದೆ ಇದು ಸುತ್ತುವರಿದ ಗುಂಪಿನ ಅಗಲದ ರೇಖಾಚಿತ್ರಗಳಿಗೂ ಅನ್ವಯಿಸುತ್ತದೆ. ಇತರ ನಿರ್ಣಾಯಕ ಸಿದ್ಧಾಂತಗಳೊಂದಿಗೆ S2S ಅನ್ನು ಸಂಯೋಜಿಸುವುದು ಮೊನಾಡಿಕ್ ಸಿದ್ಧಾಂತಗಳ ಟ್ರೀ ವಿಸ್ತರಣೆಗಳುಃ ಶೆಲಾ-ಸ್ಟಪ್ ಪ್ರಮೇಯದ ಪ್ರಕಾರ, ಮೊನಾಡಿಕ್ ರಿಲೇಷನಲ್ ಮಾಡೆಲ್ M ನಿರ್ಣಾಯಕವಾಗಿದ್ದರೆ, ಅದರ ಟ್ರೀ ಪ್ರತಿರೂಪವೂ ಸಹ ನಿರ್ಣಾಯಕವಾಗಿದೆ. ಉದಾಹರಣೆಗೆ, (ಔಪಚಾರಿಕತೆಯ ಮಾಡ್ಯುಲೋ ಆಯ್ಕೆ) ಎಸ್2ಎಸ್ ಎಂಬುದು {0,1} ನ ಮರದ ಪ್ರತಿರೂಪವಾಗಿದೆ. ಮರದ ಪ್ರತಿರೂಪದಲ್ಲಿ, ಮೊದಲ ಕ್ರಮದ ವಸ್ತುಗಳು ವಿಸ್ತರಣೆಯ ಮೂಲಕ ಆದೇಶಿಸಲಾದ M ಅಂಶಗಳ ಸೀಮಿತ ಅನುಕ್ರಮಗಳಾಗಿವೆ, ಮತ್ತು M-ಸಂಬಂಧದ ಪೈ ಅನ್ನು ಪೈ '(vd1,., vdk) ಪೈ (d1,., dk) ಗೆ ಮ್ಯಾಪ್ ಮಾಡಲಾಗುತ್ತದೆ, ಇಲ್ಲದಿದ್ದರೆ ಪೈ' ಫಾಲ್ಸ್ (dj bul M, ಮತ್ತು v ಎಂಬುದು M ಅಂಶಗಳ (ಬಹುಶಃ ಖಾಲಿ) ಅನುಕ್ರಮವಾಗಿದೆ. ಈ ಪುರಾವೆಯು S2S ನಿರ್ಣಾಯಕತೆಯ ಪುರಾವೆಯನ್ನು ಹೋಲುತ್ತದೆ. ಪ್ರತಿ ಹಂತದಲ್ಲೂ, ಒಂದು (ನಿರ್ಣಾಯಕವಲ್ಲದ) ಸ್ವಯಂಚಾಲಿತ ಯಂತ್ರವು ಎಂ ಆಬ್ಜೆಕ್ಟ್ಗಳ (ಪ್ರಾಯಶಃ ಎರಡನೇ ಕ್ರಮ) ಟುಪಲ್ ಅನ್ನು ಇನ್ಪುಟ್ ಆಗಿ ಪಡೆಯುತ್ತದೆ ಮತ್ತು ಎಂ ಸೂತ್ರವು ಯಾವ ಸ್ಥಿತಿ ಪರಿವರ್ತನೆಗಳನ್ನು ಅನುಮತಿಸಲಾಗಿದೆ ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸುತ್ತದೆ. ಪ್ಲೇಯರ್ 1 (ಮೇಲಿನಂತೆ) ಸೂತ್ರದಿಂದ ಅನುಮತಿಸಲಾದ ಮ್ಯಾಪಿಂಗ್ ಚೈಲ್ಡ್ ಸ್ಥಿತಿಯನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ (ಪ್ರಸ್ತುತ ಸ್ಥಿತಿಯನ್ನು ನೀಡಲಾಗಿದೆ), ಮತ್ತು ಪ್ಲೇಯರ್ 2 ಮುಂದುವರಿಸಲು ಚೈಲ್ಡ್ ಅನ್ನು (ನೋಡ್ನ) ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ. ನಿರ್ಣಾಯಕವಲ್ಲದ ಸ್ವಯಂಚಾಲಿತ ಯಂತ್ರದಿಂದ ನಿರಾಕರಣೆಗೆ ಸಾಕ್ಷಿಯಾಗಲು, ಪ್ರತಿ (ನೋಡ್, ಸ್ಟೇಟ್) (ಚೈಲ್ಡ್, ಸ್ಟೇಟ್) ಜೋಡಿಗಳ ಗುಂಪನ್ನು ಆಯ್ಕೆ ಮಾಡಿ, ಅಂದರೆ ಪ್ರತಿ ಆಯ್ಕೆಗೂ, ಕನಿಷ್ಠ ಒಂದು ಜೋಡಿಗೆ ಹೊಡೆತ ಬೀಳುತ್ತದೆ ಮತ್ತು ಎಲ್ಲಾ ಫಲಿತಾಂಶದ ಮಾರ್ಗಗಳು ನಿರಾಕರಣೆಗೆ ಕಾರಣವಾಗುತ್ತವೆ. ಮೊನಾಡಿಕ್ ಸಿದ್ಧಾಂತವನ್ನು ಮೊದಲ ಕ್ರಮದ ಸಿದ್ಧಾಂತದೊಂದಿಗೆ ಸಂಯೋಜಿಸುವುದುಃ ಫೆಫರ್ಮಾನ್-ವೋಟ್ ಪ್ರಮೇಯವು ಈ ಕೆಳಗಿನಂತೆ ವಿಸ್ತರಿಸುತ್ತದೆ/ಅನ್ವಯಿಸುತ್ತದೆ. M ಒಂದು MSO ಮಾದರಿಯಾಗಿದ್ದರೆ ಮತ್ತು N ಒಂದು ಮೊದಲ ಕ್ರಮದ ಮಾದರಿಯಾಗಿದ್ದರೆ, M ಅನ್ನು ಎಲ್ಲಾ ಕಾರ್ಯಗಳೊಂದಿಗೆ ವರ್ಧಿಸಿದರೂ ಸಹ (ಥಿಯರಿ (M), ಥಿಯರಿ (N)) ಒರಾಕಲ್ಗೆ ಸಂಬಂಧಿಸಿದಂತೆ M ನಿರ್ಣಾಯಕವಾಗಿ ಉಳಿಯುತ್ತದೆ M → N ಅಲ್ಲಿ M ಅನ್ನು ಅದರ ಮೊದಲ ವಸ್ತುಗಳೊಂದಿಗೆ ಗುರುತಿಸಲಾಗುತ್ತದೆ, ಮತ್ತು ಪ್ರತಿ s bul M ಗೆ ನಾವು N ನ ಬೇರ್ಪಡಿಸಿದ ನಕಲನ್ನು ಬಳಸುತ್ತೇವೆ, ಅದಕ್ಕೆ ಅನುಗುಣವಾಗಿ ಭಾಷೆಯನ್ನು ಮಾರ್ಪಡಿಸಲಾಗುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, N ಎಂಬುದು (, 0, +, ⋅) ಆಗಿದ್ದರೆ, ನಾವು (ಫಂಕ್ಷನ್ f) ಅನ್ನು ಹೇಳಬಹುದು (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) (ಫಂಕ್ಷನ್ f) ( M ಯು S2S ಆಗಿದ್ದರೆ (ಅಥವಾ ಹೆಚ್ಚು ಸಾಮಾನ್ಯವಾಗಿ, ಕೆಲವು ಮೊನಾಡಿಕ್ ಮಾದರಿಯ ಮರದ ಪ್ರತಿರೂಪ), ಆಟೋಮ್ಯಾಟಾವು ಈಗ N-ಸೂತ್ರಗಳನ್ನು ಬಳಸಬಹುದು, ಮತ್ತು ಆ ಮೂಲಕ f: M → Nk ಅನ್ನು M ಸೆಟ್ಗಳ ಟುಪಲ್ ಆಗಿ ಪರಿವರ್ತಿಸಬಹುದು. ಭಿನ್ನಾಭಿಪ್ರಾಯವು ಅಗತ್ಯವಾಗಿದೆ, ಇಲ್ಲದಿದ್ದರೆ ಸಮಾನತೆಯೊಂದಿಗೆ ಪ್ರತಿ ಅನಂತ N ಗೆ, ವಿಸ್ತೃತ S2S ಅಥವಾ ಕೇವಲ WS1S ಅನ್ನು ನಿರ್ಧರಿಸಲಾಗುವುದಿಲ್ಲ. ಅಲ್ಲದೆ, ಟಿ (ಬಹುಶಃ ಅಪೂರ್ಣ) ಸಿದ್ಧಾಂತಕ್ಕೆ, ಟಿ-ಯ ಎಂ-ಉತ್ಪನ್ನಗಳ ಟಿಎಂ ಸಿದ್ಧಾಂತವು (ಥಿಯರಿ (ಎಂ), ಟಿ) ಒರಾಕಲ್ಗೆ ಸಂಬಂಧಿಸಿದಂತೆ ನಿರ್ಣಾಯಕವಾಗಿದೆ, ಅಲ್ಲಿ ಟಿಎಂನ ಮಾದರಿಯು ಪ್ರತಿ ಎಸ್ Π ಎಂಗೆ ಟಿ ಯ ಅನಿಯಂತ್ರಿತ ಬೇರ್ಪಡಿಸುವ ಮಾದರಿ ಎನ್ಎಸ್ ಅನ್ನು ಬಳಸುತ್ತದೆ (ಮೇಲಿನಂತೆ, ಎಂ ಒಂದು ಎಂಎಸ್ಒ ಮಾದರಿಯಾಗಿದೆ; ಥಿಯರಿ (ಎನ್ಎಸ್) ಎಸ್ ಅನ್ನು ಅವಲಂಬಿಸಿರಬಹುದು). ಸೂತ್ರದ ಸಂಕೀರ್ಣತೆಯ ಮೇಲೆ ಪ್ರಚೋದನೆಯು ಪುರಾವೆಯಾಗಿದೆ. ಫಂಕ್ಷನ್ ಎಫ್ ಮುಕ್ತವಾಗಿದ್ದರೆ ಎಫ್ (ಗಳು) ಸೇರಿದಂತೆ ಉಚಿತ ಎನ್ಎಸ್ ಅಸ್ಥಿರಗಳ ಪಟ್ಟಿ ವರ್ಸಸ್ ಆಗಿರಲಿ. ಇಂಡಕ್ಷನ್ ಮೂಲಕ, ವಿಎಸ್ ಅನ್ನು |vs | ಫ್ರೀ ವೇರಿಯೇಬಲ್ಗಳೊಂದಿಗೆ ಎನ್-ಸೂತ್ರಗಳ ಸೀಮಿತ ಗುಂಪಿನ ಮೂಲಕ ಮಾತ್ರ ಬಳಸಲಾಗುತ್ತದೆ ಎಂದು ತೋರಿಸುತ್ತದೆ. ಹೀಗಾಗಿ, ಸಾಧ್ಯವಾದುದಕ್ಕೆ ಉತ್ತರಿಸಲು ಎನ್ (ಅಥವಾ ಟಿ) ಅನ್ನು ಬಳಸುವ ಮೂಲಕ ನಾವು ಎಲ್ಲಾ ಸಂಭವನೀಯ ಫಲಿತಾಂಶಗಳನ್ನು ಪ್ರಮಾಣೀಕರಿಸಬಹುದು, ಮತ್ತು ಪಟ್ಟಿ ಸಾಧ್ಯತೆಗಳನ್ನು (ಅಥವಾ ನಿರ್ಬಂಧಗಳನ್ನು) ನೀಡಿದರೆ, ಎಂನಲ್ಲಿ ಅನುಗುಣವಾದ ವಾಕ್ಯವನ್ನು ರೂಪಿಸಬಹುದು. ಎಸ್2ಎಸ್ನ ವಿಸ್ತರಣೆಗಳಾಗಿ ಕೋಡಿಂಗ್ಃ ಸ್ಟ್ರಿಂಗ್ಗಳ ಮೇಲಿನ ಪ್ರತಿಯೊಂದು ನಿರ್ಣಾಯಕ ಮುನ್ಸೂಚನೆಯನ್ನು ಎನ್ಕೋಡ್ ಮಾಡಲಾದ ಮುನ್ಸೂಚನೆಯೊಂದಿಗೆ ಎಸ್2ಎಸ್ನ (ಮೇಲಿನ ವಿಸ್ತರಣೆಗಳೊಂದಿಗೆ) ನಿರ್ಣಾಯಕತೆಗಾಗಿ ಎನ್ಕೋಡ್ ಮಾಡಬಹುದು (ರೇಖೀಯ ಸಮಯ ಎನ್ಕೋಡಿಂಗ್ ಮತ್ತು ಡಿಕೋಡಿಂಗ್ನೊಂದಿಗೆ). ಪುರಾವೆಃ ನಿರ್ಣಾಯಕವಲ್ಲದ ಅನಂತ ಮರದ ಸ್ವಯಂಚಾಲಿತವನ್ನು ನೀಡಿದರೆ, ನಾವು ಸೀಮಿತ ಬೈನರಿ ಲೇಬಲ್ ಮರಗಳ ಗುಂಪನ್ನು (ಸ್ವಯಂಚಾಲಿತವಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸಬಹುದಾದ ಲೇಬಲ್ಗಳನ್ನು ಹೊಂದಿರುವ) ಸೀಮಿತವಾಗಿ ಅನೇಕ ವರ್ಗಗಳಾಗಿ ವಿಂಗಡಿಸಬಹುದು, ಅಂದರೆ ಸಂಪೂರ್ಣ ಅನಂತ ಬೈನರಿ ಮರವನ್ನು ಒಂದೇ ವರ್ಗದ ಮರಗಳಿಂದ ಸಂಯೋಜಿಸಬಹುದಾದರೆ, ಸ್ವೀಕಾರವು ವರ್ಗ ಮತ್ತು ಆರಂಭಿಕ ಸ್ಥಿತಿಯನ್ನು ಮಾತ್ರ ಅವಲಂಬಿಸಿರುತ್ತದೆ (ಅಂದರೆ. ಸ್ವಯಂಚಾಲಿತ ಯಂತ್ರವು ಮರವನ್ನು ಪ್ರವೇಶಿಸುತ್ತದೆ ಎಂದು ತಿಳಿಸಿ). (ಪಂಪಿಂಗ್ ಲೆಮ್ಮಾದೊಂದಿಗೆ ಸ್ಥೂಲವಾದ ಹೋಲಿಕೆಯನ್ನು ಗಮನಿಸಿ.) ಉದಾಹರಣೆಗೆ (ಪ್ಯಾರಿಟಿ ಆಟೋಮ್ಯಾಟನ್ಗಾಗಿ), ಆರಂಭಿಕ _ ಸ್ಥಿತಿ ಮತ್ತು ಸೆಟ್ ಕ್ಯೂ ಆಫ್ (ಸ್ಟೇಟ್, ಹೈಯೆಸ್ಟ್ _ ಪ್ರಿಯಾರಿಟಿ _ ರೀಚ್ಡ್) ಜೋಡಿಗಳು ಆಟಗಾರ 1 (ಅಂದರೆ. ಅನಿರ್ದಿಷ್ಟತೆ) ಏಕಕಾಲದಲ್ಲಿ ಎಲ್ಲಾ ಶಾಖೆಗಳನ್ನು ಕ್ಯೂ ಅಂಶಗಳಿಗೆ ಹೊಂದಿಕೆಯಾಗುವಂತೆ ಒತ್ತಾಯಿಸಬಹುದು. ಈಗ, ಪ್ರತಿ k ಗೆ, k ಗೆ ಅಡ್ಡಲಾಗಿ ಸ್ಥಿರವಾದ ವರ್ಗದ ಆಯ್ಕೆಯೊಂದಿಗೆ, ಆಟೋಮ್ಯಾಟಾ 1-k ಗೆ ಒಂದೇ ವರ್ಗಕ್ಕೆ ಸೇರಿದ ಸೀಮಿತ ಮರಗಳ ಗುಂಪನ್ನು (ಕೋಡಿಂಗ್ಗೆ ಸೂಕ್ತವಾದ) ಆಯ್ಕೆ ಮಾಡಿ. ಒಂದು ಊಹೆಯನ್ನು ಎನ್ಕೋಡ್ ಮಾಡಲು, k = 1 ಅನ್ನು ಬಳಸಿಕೊಂಡು ಕೆಲವು ಬಿಟ್ಗಳನ್ನು ಎನ್ಕೋಡ್ ಮಾಡಿ, ನಂತರ k = 2 ಅನ್ನು ಬಳಸಿಕೊಂಡು ಹೆಚ್ಚಿನ ಬಿಟ್ಗಳನ್ನು ಎನ್ಕೋಡ್ ಮಾಡಿ, ಮತ್ತು ಹೀಗೆ. ಉಲ್ಲೇಖಗಳು ಹೆಚ್ಚುವರಿ ಉಲ್ಲೇಖಃ ಗಣಿತದ ತರ್ಕದ ಗಣನೀಯತೆ ಸಿದ್ಧಾಂತ ಪುರಾವೆಗಳನ್ನು ಹೊಂದಿರುವ ಲೇಖನಗಳು