előfordulási próba

Kapcsolódó fogalmak: 
term
Kapcsolódó fogalmak: 
elsőrendű logika
Rövid szöveges bemutatás: 
Az előfordulási próba egy elégséges feltételt vizsgál arra, hogy egy változót tudunk-e a vizsgált termhez illeszteni valamilyen módon. A próba azt nézi meg, hogy a változó szerepel-e az adott termben. Ha igen, akkor az illesztés nem lehetséges. Például az X=f(X) illesztés egy hibás eredményt adna, így végrehajtása a próba szerint nem lehetséges. Ennek ellenőrzése alapesetben a term hosszában négyzetes, újabb alkalmazásokban sikerült leredukálni lineáris időre a végrehajtást a term hosszában.