Pojęcie to okazało się być istotne w związkach informatyki ze statystyką, algebrą uniwersalną i kombinatoryką. W dziedzinie logik niemonotonicznych (grupie logik związanych ze sztuczną inteligencją) Marek badał szczególnie tzw. logikę domniemań (ang. default logic) wprowadzoną przez R. Reiter'aM.Denecker, V.W. Marek i M. Truszczynski, Uniform semantic treatment of default and autoepistemic logics. Artificial Intelligence Journal. 143:79--122, 2003 oraz logikę autoepistemiczną (ang. autoepistemic logic) R. Moore’aM.Denecker, V.W. Marek i M. Truszczynski, Fixpoint 3-valued semantics for autoepistemic logic. Festschrift in honor of R. Reiter. Springer-Verlag. H.J. Levesque and F. Pirri (eds.), pages 113--136, 1999. Badania te doprowadziły do wprowadzenia formy programowania logicznego nazywanej Answer Set ProgrammingV.W. Marek i M. Truszczynski, Stable logic programming - an alternative logic programming paradigm. In: 25 years of Logic Programming Paradigm, pages 375-398, Springer-Verlag, 1999, intensywnie badanej w Europie i Stanach Zjednoczonych. W szczególności Marek wraz z M. Truszczyńskim wykazał, że problem istnienia modeli stabilnych dla programów logicznych zdaniowych jest NP-zupełny. Dla programów dopuszczających dowolne symbole  funkcyjne Marek (wraz z A. Nerode i J.