Papers and manuscripts by Mirek Truszczynski 

(since 1995; earlier papers available by request)


In the pipeline



2012


The View-Update Problem for Indefinite Databases
L. Caroprsese, I. Trubitsyna, M. Truszczynski, E. Zumpano, Proceedings of JELIA 2012

A Tarskian Informal Semantics for Answer Set Programming
M. Denecker, Y. Lierler, M. Truszczynski, J. Vennekens, Proceedings of ICLP 2012

Strong Equivalence of Qualitative Optimization Problems
W. Faber, M. Truszczynski, S. Woltran, Proceedings of KR 2012.

Constructions of asymptotically shortest k-radius sequences
J.W. Jaromczyk, Z. Lonc, M. Truszczynski, J. Combiatorial Theory, ser. A, 119(3): 731-746 (2012).

Connecting First-Order ASP and the Logic FO(ID) through Reducts
M. Truszczynski, in E. Erdem, J. Lee, Y. Lierler, D. Pearce, eds.: Correct Reasoning - Essays on Logic-Based AI in Honour of Vladimir Lifschitz, Springer 2012.


2011


Origins of Answer-Set Programming -- Some Background And Two Personal Accounts
V.W. Marek, I. Niemela, and M. Truszczynski, in G. Brewka, V.M. Marek, and M. Truszczynski, eds. Nonmonotonic Reasoning -- Essays Celebrating its 30th Anniversary, College Publications, 2011.

Reiter's Default Logic Is a Logic of Autoepistemic Reasoning And a Good One, Too
M. Denecker, V.W. Marek and M. Truszczynski, in G. Brewka, V.M. Marek, and M. Truszczynski, eds. Nonmonotonic Reasoning -- Essays Celebrating its 30th Anniversary, College Publications, 2011.

Transition Systems for Model Generators - A Unifying Approach
Y. Lierler, M. Truszczynski, Theory and Practice of Logic Programming, 11(4-5): 629-646

On Graph Equivalences Preserved Under Extensions
Z. Lonc and M. Truszczynski, Discrete Mathematics, 311(12): 966-977 (2011)

Revisiting Epistemic Specifications
M. Truszczynski, In Marcello Balduccini and Tran Cao Son, Editors, The Proceedings of the Symposium on Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning, Essays Dedicated to Michael Gelfond on the Occasion of His 65th Birthday. October 2010, LNAI 6565, Springer


2010


Reducts of propositional theories, satisfiability relations, and generalizations of semantics of logic programs
M. Truszczynski, Artificial Intelligence Journal (a final pre-publication version)
(A substantially extended and improved version of a paper presented at ICLP-2009
Published article available at Science Direct )

Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs
M. Truszczynski, Theory and Practice of Logic Programming (to appear; available at CoRR)
(An extended and improved version of a paper presented at LPNMR-2009)


Active integrity constraints and revision programming
L. Caroprese and M. Truszczynski, Theory and Practice of Logic Programming (to appear)
(Extended and improved version of the papers published in Proceedings of JELIA-2008 and of ICLP-2008)

Simple but hard mixed Horn formulas
G. Namasivayam and M. Truszczynski, Proceedings of SAT-2010


Representing preferences among sets
G. Brewka, M. Truszczynski and S. Woltran, Proceedings of AAAI-2010


Logic Programs with Abstract Constraint Atoms: The Role of Computations (pdf)
L. Liu, E. Pontelli, T.C. Son and M. Truszczynski, Artificial Intelligence, Volume 174, Issues 3-4, March 2010, Pages 295-315.
(Extended and improved version of the paper published in Proceedings of ICLP-2007)


2009


Relativized Hyperequivalence of Logic Programs for Modular Programming
M. Truszczynski, S. Woltran, TPLP 9(6): 781-819 (2009)

Simple Random Logic Programs
G. Namasivayam, M. Truszczynski, Proceedings of LPNMR 2009

Trichotomy Results on the Complexity of Reasoning with Disjunctive Logic Programs
M. Truszczynski, Proceedings of LPNMR 2009

Reducts of Propositional Theories, Satisfiability Relations, and Generalizations of Semantics of Logic Programs
M. Truszczynski, Proceedings of ICLP 2009


2008


My six encounters with Victor Marek - a personal account
M. Truszczynski, AMAI 53(1-4): 17-20 (2008)

Hyperequivalence of logic programs with respect to supported models
M. Truszczynski and S. Woltran, AMAI 53(1-4): 331-365 (2008)
(Extended version of a paper that appeared in Proceedings of AAAI 2008)

On the number of minimal transversals in 3-uniform hypergraphs
Z. Lonc and M. Truszczynski, Discrete Mathematics 308(16): 3668-3687 (2008)

The Computational Complexity of Dominance and Consistency in CP-Nets
J. Goldsmith, J. Lang, M. Truszczynski, N. Wilson, JAIR 33: 403-432 (2008)

Relativized Hyperequivalence of Logic Programs for Modular Programming
M. Truszczynski, S. Woltran, Proceedings of ICLP 2008

Declarative Semantics for Active Integrity Constraints
L. Caroprese, M. Truszczynski, Proceedings of ICLP 2008

Declarative Semantics for Revision Programming and Connections to Active Integrity Constraints
L. Caroprese, M. Truszczynski, Proceedings of JELIA 2008

Hyperequivalence of Logic Programs with Respect to Supported Models
M. Truszczynski, S. Woltran, Proceedings of AAAI 2008

Logic programs with monotone abstract constraint atoms (pdf)
V.W. Marek, I. Niemela, M. Truszczynski, TPLP 8(2), 167-199, 2008
(Extended version of papers published in Proceedings of LPNMR-04 and Proceedings of AAAI-04)

Nonmonotonic Reasoning
G. Brewka, I. Niemela, M. Truszczynski, in: V. Lifschitz, B. Porter, F. van Harmelen (eds.), Handbook of Knowledge Representation, Elsevier, 2008, 239-284


2007


Satisfiability testing of Boolean combinations of pseudo-boolean constraints using local-search techniques
L. Liu and M. Truszczynski, Constraints 12(3), 345 - 369, 2007
(Extended version of papers published in Proceedings of CP-2003 and Proceedings of AAAI-06)

Logic Programs with Abstract Constraint Atoms: The Role of Computations (pdf)
L. Liu, E. Pontelli, T.C. Son and M. Truszczynski, Proceedings of ICLP-07.

Logic Programming for Knowledge Representation (an outline, background and references for the ICLP-07 invited tutorial) (pdf)
M. Truszczynski, Proceedings of ICLP-07.

The Modal Logic S4F, the Default Logic, and the Logic Here-and-There (pdf)
M. Truszczynski, Proceedings of AAAI-07.

An smodels system with limited lookahead computation (pdf)
G. Namasivayam, M. Truszczynski, Proceedings of LPNMR-07.

The First Answer Set Programming System Competition (pdf file only)
M. Gebser, L. Liu, G. Namasivayam, A. Neumann, T. Schaub, M. Truszczynski, Proceedings of LPNMR-07.

Comments on Modeling Languages for Answer-Set Programming (pdf)
M. Truszczynski, Software Engineering for Answer Set Programming (SEA'07).


2006


Strong and uniform equivalence of nonmonotonic theories - an algebraic approach (pdf)
M. Truszczynski, AMAI (2006) 48:245--265.
(Extended version of the paper published in Proceedings of KR2006))

Tools for modeling and solving search problems (pdf)
D. East, M. Iakhiaev, A Mikitiuk, M. Truszczynski, AI Communications, 19(4): 301-312, 2006
(
Preliminary version appeared in Proceedings of the Third International Workshop on Modelling and Reformulating Constraint Satisfaction Problems)

Properties and applications of programs with monotone and convex constraints (pdf)
L. Liu, M. Truszczynski, JAIR, (27): 299-334, 2006.
(Extended version of papers published in Proceedings of AAAI-05 and LPNMR-05)

Computing minimal models, stable models and answer sets (pdf)
Z. Lonc, M. Truszczynski, TPLP, 6(4):395-449, 2006.
(Preliminary version appeared in Proceedings of ICLP-03)

Nonmonotonic logics and their algebraic foundations  (pdf)
M. Truszczynski,  Proceedings of CSL 2006, LNCS, Springer
(Background material and references for the invited talk at CSL 2006)

Predicate-calculus based logics for modeling and solving search problems (pdf)
D. East, M. Truszczynski, ACM TOCL, 7(1), 38-83.

Strong and uniform equivalence of nonmonotonic theories --- an algebraic approach
(pdf)
M. Truszczynski, Principles of Knowledge Representation and Reasoning, Proceedings of the Tenth International Conference (KR2006)

Local-search techniques for boolean combinations of pseudo-boolean constraints (pdf)
L. Liu, M. Truszczynski, Proceedings of AAAI-06

Generating cellular puzzles with logic programs

R. Finkel, V.W. Marek, M. Truszczynski, Proceedings of ICAI-06



2005


The computational complexity of dominance and consistency in CP-nets (pdf)
J. Goldsmith, J. Lang, M. Truszczynski, N. Wilson, Proceedings of IJCAI-05, 2005.

Prioritized Component Systems (pdf)
G. Brewka, I. Niemela, M. Truszczynski, Proceedings of AAAI-05.

Properties of Programs with Monotone and Convex Constraints (pdf)
L. Liu, M. Truszczynski, Proceedings of AAAI-05.

Pbmodels - Software to Compute Stable Models by Pseudoboolean Solvers (pdf)
L. Liu, M. Truszczynski, Proceedings of LPNMR-05.

Approximating answer sets of unitary Lifschitz-Woo programs (pdf)
V. Marek, I. Pivkina, M. Truszczynski, Proceedings of LPNMR-05.

2004


D. East. M. Iakhiaev, A. Mikitiuk, M. Truszczynski, Third International Workshop on Modelling and Reformulating Constraint Satisfaction Problems, Toronto, 2004

Local search with bootstrapping (pdf)
L. Liu, M. Truszczynski, Proceedings of SAT-2004.
Satisfiability and computing van der Waerden numbers (pdf)
M. Dransfield, L. Liu, V. Marek, M. Truszczynski, The Electronic Journal of Combinatorics, 11(1) (2004)
Preliminary version appeared as M. Dransfield, V. Marek, M. Truszczynski, Satisfiability and computing van der Waerden numbers in Theory and Applications of Satisfiability Testing, LNCS 2919, Springer, 2003 - see below)

Semantics of disjunctive programs with monotone aggregates -  an operator-based approach (pdf)
N. Pelov, M. Truszczynski, Proceedings of NMR-04

Logic programs with abstract constraint atoms (pdf)
V. Marek, M. Truszczynski, Proceedings of AAAI-04

Constraint Lingo: Towards high-level constraint programming (pdf)
R. Finkel, V. Marek, M. Truszczynski, Software Practice and Experience, 34 (2004), 1481-1504
 
Automatic generation of English-language steps in puzzle solving (pdf)
H. Ponnuru, R. Finkel, V. Marek and M. Truszczynski, The 2004 International Conference on Artificial Intelligence (IC-AI'04)

Ultimate approximations in nonmonotonic knowledge representation system  (pdf)
M. Denecker, V.W. Marek, M. Truszczynski,  Information and Computation,  192 (2004), 84-121
(Preliminary version in Proceedings of KR-02 - see below).

2003


Satisfiability and computing van der Waerden numbers (pdf)
M. Dransfield,  V. Marek, M. Truszczynski,  Theory and Applications of Satisfiability Testing, LNCS 2919, Springer, 2003 (selected papers presented at SAT-2003)

WSAT(cc) - a fast local-search ASP solver (pdf)
L. Liu, M. Truszczynski, Proceedings of LPNMR-2003.
Logic programming with monotone cardinality atoms (pdf)
V. Marek, I. Niemela, M. Truszczynski, Proceedings of LPNMR-2003.
Answer Set Optimization (pdf)
G. Brewka, I. Niemela, M. Truszczynski, Proceedings of IJCAI-03, 2003.

Local-search techniques for propositional logic with cardinality constraints (pdf)
L. Liu, M. Truszczynski, Proceedings of CP-2003.

Computing minimal models, stable models and answer sets (pdf)
Z. Lonc, M. Truszczynski, Proceedings of ICLP-2003. Z. Lonc, M. Truszczynski, Theory and Practice of Logic Programming, 4 (2004), pp. 193-231
(Preliminary version appeared in the Proceedings of ICLP-02 - see below)

Fixed-parameter complexity of semantics for logic programs (pdf)
Z. Lonc, M. Truszczynski, ACM Transactions on Computational Logic, 4 (2003) pp. 91-119
(Preliminary version appeared in the Proceedings of ICLP-2001 - see below)

Uniform semantic treatment of default and autoepistemic logics (pdf)
M. Denecker, V. Marek, M. Truszczynski, Artificial Intelligence Journal, 143 (2003), pp. 79-122
(Preliminary version appeared in the Proceedings of KR2000 - see below)


2002


Ultimate approximations in nonmonotonic knowlege representation systems (pdf)
M. Denecker, V. Marek, M. Truszczynski. Principles of Knowledge Representation and Reasoning, Proceedings of the Eighth International Conference (KR2002)}, D. Fensel, D. McGuinness and M.-A. Williams, eds., 2002, Morgan Kaufmann Publishers.

The aspps system (pdf)
D. East, M. Truszczynski, Proceedings of the 8th European Conference on Logics in Artificial Intelligence (JELIA), Lecture Notes in Computer Science, Springer Verlag, 2424, pp. 533-536, 2002

Constraint Lingo: A program for solving logic puzzles and other tabular constraint problems (pdf)
R. Finkel, V. Marek, M. Truszczynski, Proceedings of the 8th European Conference on Logics in Artificial Intelligence (JELIA), Lecture Notes in Computer Science, Springer Verlag, 2424, pp. 513--516.

Computing large and small stable models (pdf)
M. Truszczynski, Theory and Practice of Logic Programming, 2(1), 1-23, 2002.
(Preliminary version appeared in the Proceedings of ICLP-99 see below)

Computing stable models: worst-case performance estimates (pdf)
Z. Lonc, M. Truszczynski, Proceedings of ICLP-02.

Annotated revision programs (pdf)
V.W. Marek, I. Pivkina, M. Truszczynski, Artificial Intelligence Journal, 138(2002), pp. 149-180.
( Preliminary version appeared in Proceedings of LPNMR-99 - see below)

Ultimate approximations in nonmonotonic knowledge representation systems (pdf)
M. Denecker, V.W. Marek, M. Truszczynski, Principles of Knowledge Representation and Reasoning, Proceedings of the Eighth International Conference (KR2002)}, D. Fensel, D. McGuinness and M.-A. Williams, eds., 2002, Morgan Kaufmann Publishers.

2001


Propositional satisfiability in answer-set programming (pdf)
D. East, M. Truszczynski, Proceedings of KI-2001, LNAI 2174, Springer Verlag, 2001.

aspps  - an implementation of answer-set ptogramming with propositional schemata (pdf)
D. East, M. Truszczynski, Proceedings of LPNMR-2001, LNAI 2173, Springer Verlag, 2001.

Fixed-parameter complexity of semantics for logic programs (pdf)
Z. Lonc, M. Truszczynski, Proceedings of ICLP-2001.


On the problem of computing the well-founded semantics (pdf)
Z. Lonc, M. Truszczynski, Theory and Practice of Logic Programming, 1(5), 591-609, 2001.
(Preliminary version   appeared in the Proceedings of CL 2000, Springer Verlag, July 2000 - see below)

2000


Approximations, stable operators, well-founded fixpoints and applications in nonmonotonic reasoning (pdf)
M. Denecker, V. Marek, M. Truszczynski, Logic-Based Artificial Intelligence, J. Minker, ed., Kluwer Academic Publishers, 2000.

Uniform semantic treatment of  default and autoepistemic logics
M. Denecker, V. Marek, M. Truszczynski., Proceedings of KR2000.


DATALOG with constraints - an answer-set programming system
D. East, M. Truszczynski, Proceedings of AAAI-00, 2000.

On the problem of computing the well-founded semantics   (pdf)
Z. Lonc, M. Truszczynski, Proceedings of CL 2000.

1999


Stable logic programming - an alternative logic programming paradigm
V. W. Marek, M. Truszczynski, in: The Logic Programming Paradigm: A 25-Year Perspective, editors: K.R. Apt, V.W. Marek, M. Truszczynski, D.S. Warren, Springer-Verlag, 1999.

Fixpoint 3-valued semantics for autoepistemic logic (pdf)
M. Denecker, V.W. Marek, M. Truszczynski, in: Logical Foundations for Cognitive Agents: Contributions in Honor of Ray Reiter, editors: H.J. Levesque, F. Pirri, Springer-Verlag, pp. 113-136, 1999.

Contributions to the theory of rough sets (pdf)
V.W. Marek, M. Truszczynski, Fundamenta Informaticae, 39(1999), pp. 389-489.

On the accuracy and running time of GSAT (pdf)
D. East, M. Truszczynski, Proceedings of EPIA-99, Springer-Verlag, 1999.

Extremal problems in logic programming and stable model computation (pdf)
P. Cholewinski, M. Truszczynski,  Journal of Logic Programming, 38 (1999), pp. 219--242.

Computing large and small stable models (pdf)
M. Truszczynski, Proceedings of ICLP-99, MIT Press, 1999.

Annotated revision programms (pdf)
V. Marek, I. Pivkina, M. Truszczynski, Proceedings of LPNMR-99, Springer-Verlag, 1999.

Computing with default logic (pdf)
P. Cholewinski, V.W. Marek, A. Mikitiuk, M. Truszczynski, Artificial Intelligence Journal, 112(1999), pp. 105-146.

Revision programming = logic programming + constraints (pdf)
V.W. Marek, I. Pivkina, M. Truszczynski, Proceedings of the Computer Science Logic Conference (CSL 98), Springer-Verlag,1999.

1998


Fixpoint 3-valued semantics for autoepistemic logic (pdf)
M. Denecker, V.W. Marek, M. Truszczynski, Proceedings of AAAI-98, pp. 840-845, MIT Press 1998.

Revision programming (pdf)
V.W. Marek, M. Truszczynski, Theoretical Computer Science, 190(1998), pp. 241-277.

1997


Representation Theory for Default Logic (pdf)
V.W. Marek, Jan Treur, M. Truszczynski, Annals of Mathematics and Artificial Intelligence, 21 (1997), pp. 343-358.

1996


Nonmonotonic reasoning is sometimes simpler (pdf)
M. Truszczynski, Grigori Schwarz Journal of Logic and Computation, 6(1996), 295 -- 308.

Approximating the stable model semantics is hard (pdf)
G. Gottlob, M. Truszczynski, Fundamenta Informaticae, 28(1996), 123 -- 128.

Default reasoning system DeReS (pdf)
P. Cholewinski, V.W. Marek, M. Truszczynski, Proceedings of KR-96, Morgan Kaufmann, 1996.

Infinitary Default Logic for Specification of Nonmonotonic Reasoning (pdf)
J. Engelfriet, V. Marek, J. Treur, M. Truszczynski, Proceedings of JELIA-96, Springer Lecture Notes in Computer Science 1126, pp. 224-236, 1996.

1995


Revision programming, database updates and integrity constraints (pdf)
V.W. Marek, M. Truszczynski, Proceedings of the 5th International Conference on Database Theory --- ICDT 95, Springer-Verlag, 1995.

Constrained and rational default logics (pdf)
A. Mikitiuk, M. Truszczynski, Proceedings of IJCAI-95. Morgan Kaufmann, 1995.

Experimenting with Nonmonotonic Reasoning (pdf)
P. Cholewinski, V.W. Marek, A. Mikitiuk, M. Truszczynski, Proceedings of the 12th International Conference on Logic Programming, MIT Press, 1995.

Skeptical rational extensions (pdf)
A. Mikitiuk, M. Truszczynski, Proceedings of LPNMR-95, Springer-Verlag, 1995.

Algorithms for Maintaining Authorization Base (pdf)
W. Brooks, V.W. Marek, M. Truszczynski, Proceedings of the 2nd International Conference on Object-Orieented Information Systems, Springer-Verlag, 1995.

Unpublished


Logic programming with costs (pdf)
V.W. Marek, M. Truszczynski, unpublished note.

Minimal number of permutations sufficient to compute all extensions (pdf)
P. Cholewinski, M. Truszczynski, unpublished note.