Victor W. Marek

Last updated

Victor Witold Marek, formerly Wiktor Witold Marek known as Witek Marek (born 22 March 1943) is a Polish mathematician and computer scientist working in the fields of theoretical computer science and mathematical logic.

Contents

Biography

Victor Witold Marek studied mathematics at the Faculty of Mathematics and Physics of the University of Warsaw. Supervised by Andrzej Mostowski, he received both a magister degree in mathematics in 1964 and a doctoral degree in mathematics in 1968. He completed habilitation in mathematics in 1972.

In 1970–1971, Marek was a postdoctoral researcher at Utrecht University, the Netherlands, where he worked under Dirk van Dalen. In 1967–1968 as well as in 1973–1975, he was a researcher at the Institute of Mathematics of the Polish Academy of Sciences, Warsaw, Poland. In 1979–1980 and 1982–1983 he worked at the Venezuelan Institute of Scientific Research. In 1976, he was appointed an Assistant Professor of Mathematics at the University of Warsaw.

In 1983, he was appointed a professor of computer science at the University of Kentucky. In 1989–1990, he was a Visiting Professor of Mathematics at Cornell University, Ithaca, New York. In 2001–2002, he was a visitor at the Department of Mathematics of the University of California, San Diego.

In 2013, Professor Marek was the Chair of the Program Committee of the scientific conference commemorating Andrzej Mostowski's Centennial.

Legacy

Teaching

He has supervised a number of graduate theses and projects. He was an advisor of 16 doctoral candidates both in mathematics and computer science. In particular, he advised dissertations in mathematics by Małgorzata Dubiel-Lachlan, Roman Kossak, Adam Krawczyk, Tadeusz Kreid, Roman Murawski, Andrzej Pelc, Zygmunt Ratajczyk, Marian Srebrny, and Zygmunt Vetulani. In computer science his students were V. K. Cody Bumgardner, Waldemar W. Koczkodaj, Witold Lipski, Joseph Oldham, Inna Pivkina, Michał Sobolewski , Paweł Traczyk, and Zygmunt Vetulani. These individuals have worked in various institutions of higher education in Canada, France, Poland, and the United States.

Mathematics

He investigated a number of areas in the foundations of mathematics, for instance infinitary combinatorics (large cardinals), metamathematics of set theory, the hierarchy of constructible sets, [1] models of second-order arithmetic, [2] the impredicative theory of Kelley–Morse classes. [3] He proved that the so-called Fraïssé conjecture (second-order theories of countable ordinals are all different) is entailed by Gödel's axiom of constructibility. Together with Marian Srebrny, he investigated properties of gaps in a constructible universe.

Computer science

He studied logical foundations of computer science. In the early 1970s, in collaboration with Zdzisław Pawlak, [4] [5] he investigated Pawlak's information storage and retrieval systems, [6] which then was a widely studied concept, especially in Eastern Europe. These systems were essentially single-table relational databases, but unlike Codd's relational databases were bags rather than sets of records. These investigations, in turn, led Pawlak to the concept of rough set, [5] studied by Marek and Pawlak in 1981. [7] The concept of rough set, in computer science, statistics, topology, universal algebra, combinatorics, and modal logic, turned out to be an expressive language for describing, and especially manipulating an incomplete information.

Logic

In the area of nonmonotonic logics, a group of logics related to artificial intelligence, he focused on investigations of Reiter's default logic, [8] and autoepistemic logic of R. Moore. These investigations led to a form of logic programming called answer set programming [9] a computational knowledge representation formalism, studied both in Europe and in the United States. Together with Mirosław Truszczynski, he proved that the problem of existence of stable models of logic programs is NP-complete. In a stronger formalism admitting function symbols, along with Nerode and Remmel he showed that the analogous problem is Σ1
1-complete.

Publications

V. W. Marek is an author of over 180 scientific papers in the area of foundations of mathematics and of computer science. He was also an editor of numerous proceedings of scientific meetings. Additionally, he authored or coauthored several books. These include:

Related Research Articles

<span class="mw-page-title-main">Kazimierz Kuratowski</span> Polish mathematician and logician

Kazimierz Kuratowski was a Polish mathematician and logician. He was one of the leading representatives of the Warsaw School of Mathematics. He worked as a professor at the University of Warsaw and at the Mathematical Institute of the Polish Academy of Sciences. Between 1946 and 1953, he served as President of the Polish Mathematical Society.

Proof theory is a major branch of mathematical logic and theoretical computer science within which proofs are treated as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures such as lists, boxed lists, or trees, which are constructed according to the axioms and rules of inference of a given logical system. Consequently, proof theory is syntactic in nature, in contrast to model theory, which is semantic in nature.

A non-monotonic logic is a formal logic whose conclusion relation is not monotonic. In other words, non-monotonic logics are devised to capture and represent defeasible inferences, i.e., a kind of inference in which reasoners draw tentative conclusions, enabling reasoners to retract their conclusion(s) based on further evidence. Most studied formal logics have a monotonic entailment relation, meaning that adding a formula to a theory never produces a pruning of its set of conclusions. Intuitively, monotonicity indicates that learning a new piece of knowledge cannot reduce the set of what is known. A monotonic logic cannot handle various reasoning tasks such as reasoning by default, abductive reasoning, some important approaches to reasoning about knowledge, and similarly, belief revision.

Default logic is a non-monotonic logic proposed by Raymond Reiter to formalize reasoning with default assumptions.

<span class="mw-page-title-main">Polish Academy of Sciences</span> National academy of sciences for Poland

The Polish Academy of Sciences is a Polish state-sponsored institution of higher learning. Headquartered in Warsaw, it is responsible for spearheading the development of science across the country by a society of distinguished scholars and a network of research institutes. It was established in 1951, during the early period of the Polish People's Republic following World War II.

<span class="mw-page-title-main">Andrzej Mostowski</span> Polish mathematician

Andrzej Mostowski was a Polish mathematician. He is perhaps best remembered for the Mostowski collapse lemma.

Fundamenta Mathematicae is a peer-reviewed scientific journal of mathematics with a special focus on the foundations of mathematics, concentrating on set theory, mathematical logic, topology and its interactions with algebra, and dynamical systems.

In mathematics, logic and philosophy of mathematics, something that is impredicative is a self-referencing definition. Roughly speaking, a definition is impredicative if it invokes the set being defined, or another set that contains the thing being defined. There is no generally accepted precise definition of what it means to be predicative or impredicative. Authors have given different but related definitions.

The concept of a stable model, or answer set, is used to define a declarative semantics for logic programs with negation as failure. This is one of several standard approaches to the meaning of negation in logic programming, along with program completion and the well-founded semantics. The stable model semantics is the basis of answer set programming.

<span class="mw-page-title-main">Andrzej Grzegorczyk</span> Polish mathematician and philosopher

Andrzej Grzegorczyk was a Polish logician, mathematician, philosopher, and ethicist noted for his work in computability, mathematical logic, and the foundations of mathematics.

Vladimir Lifschitz is the Gottesman Family Centennial Professor in Computer Sciences at the University of Texas at Austin. He received a degree in mathematics from the Steklov Institute of Mathematics in Russia in 1971 and emigrated to the United States in 1976. Lifschitz's research interests are in the areas of computational logic and knowledge representation. He is a Fellow of the Association for the Advancement of Artificial Intelligence, the Editor-in-Chief of the ACM Transactions on Computational Logic, and an Editorial Advisor of the journal Theory and Practice of Logic Programming.

<span class="mw-page-title-main">Kazimierz Vetulani</span> Polish civil engineer

Kazimierz Franciszek Vetulani was a Polish civil engineer, professor at the Lviv Polytechnic, member of the Polish Mathematical Society, author of several dozen papers in the fields of technology and mathematics, as well as in the field of musical scale theory.

Michael Gelfond is a Professor in Computer Sciences at Texas Tech University in the United States. He received a degree in mathematics from the Steklov Institute of Mathematics in Russia in 1974 and emigrated to the United States in 1978. Gelfond's research interests are in the areas of computational logic and knowledge representation. He is a Fellow of the Association for the Advancement of Artificial Intelligence, and an Area Editor of the journal Theory and Practice of Logic Programming.

<span class="mw-page-title-main">Henryk Struve</span> Polish philosopher

Henryk Struve (1840–1912) was a Polish philosopher. He has been called "perhaps the most remarkable person in logic in Warsaw in the 19th century". Struve taught philosophy at Warsaw University from 1862 to 1903. He wrote works in Polish, German and Russian.

<span class="mw-page-title-main">Zygmunt Vetulani (computer scientist)</span> Polish mathematician and computer scientist

Zygmunt Władysław Vetulani is a Polish mathematician and computer scientist who specializes in language engineering and artificial intelligence, professor of technical sciences and professor at the Adam Mickiewicz University where he is also Head of the Department of Information Linguistics and Artificial Intelligence.

<span class="mw-page-title-main">Johann Makowsky</span>

Johann (János) A. Makowsky is a Hungarian-born naturalised Swiss mathematician who works in mathematical logic and the logical foundations of computer science and combinatorics. He studied at ETH Zurich from 1967–73. He was a student in Zürich of Ernst Specker and Hans Läuchli in mathematical logic,, of Beno Eckmann and Volker Strassen (Algorithmics), and in Warsaw of Andrzej Mostowski and Witek Marek, where he spent 1972 as an exchange student. Makowsky held visiting positions at the Banach Center in Warsaw (Poland), Stanford University (USA), Simon Fraser University (Canada), University of Florence (Italy), MIT (USA), Lausanne University and ETH Zurich (Switzerland). He held regular positions at the Free University of Berlin and the Technion – Israel Institute of Technology where he was a full professor.

<span class="mw-page-title-main">Grażyna Vetulani</span> Polish philologist

Grażyna Małgorzata Vetulani née Świerczyńska is a Polish philologist and linguist, professor of the humanities, professor at the Adam Mickiewicz University in Poznań and the Nicolaus Copernicus University in Toruń.

<span class="mw-page-title-main">Witold Kosiński</span> Polish mathematician and computer scientist

Witold Kosiński was a Polish mathematician and computer scientist. He was the lead inventor and main propagator of Ordered Fuzzy Numbers.

<span class="mw-page-title-main">Witold Lipski</span> Polish computer scientist

Witold Lipski Jr. was a Polish computer scientist, and an author of two books: Combinatorics for Programmers and (jointly with Wiktor Marek Combinatorial analysis. Lipski, jointly with his PhD student, Tomasz Imieliński, created foundations of the theory of incomplete information in relational databases.

Krzysztof R. Apt is a Polish computer scientist. He defended his PhD in mathematical logic in Warsaw, Poland in 1974. His research interests include program correctness and semantics, use of logic as a programming language, distributed computing, and game theory. Besides his own research, he has been heavily involved in service to the computing community, notably by promoting the use of logic in computer science and by advocating open access to scientific literature.

References

  1. ↑ W. Marek and M. Srebrny, Gaps in constructible universe, Annals of Mathematical Logic, 6:359–394, 1974.
  2. ↑ K.R. Apt and W. Marek, Second order arithmetic and related topics, Annals of Mathematical Logic, 6:177–229, 1974
  3. ↑ W. Marek, On the metamathematics of impredicative set theory. Dissertationes Mathematicae 98, 45 pages, 1973
  4. ↑ Z. Pawlak, Mathematical foundations of information retrieval. Institute of Computer Sciences, Polish Academy of Sciences, Technical Report 101, 8 pages, 1973
  5. 1 2 Z. Pawlak, Rough sets. Institute of Computer Science, Polish Academy of Sciences, Technical Report 431, 12 pages, 1981
  6. ↑ W. Marek and Z. Pawlak On the foundations of information retrieval. Bull. Acad. Pol. Sci. 22:447–452, 1974
  7. ↑ W. Marek and Z. Pawlak. Rough sets and information systems, Institute of Computer Science, Technical Report 441, Polish Academy of Sciences, 15 pages, 1981
  8. ↑ M.Denecker, V.W. Marek and M. Truszczynski, Uniform semantic treatment of default and autoepistemic logics. Artificial Intelligence. 143:79–122, 2003
  9. ↑ V.W. Marek and M. Truszczynski, Stable logic programming – an alternative logic programming paradigm. In: 25 years of Logic Programming Paradigm, pages 375–398, Springer-Verlag, 1999
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.