AIICS

Andrzej Szalas

All Publications

Hide abstracts BibTeX entries
2014
[123] L.A. Nguyen, T.-B.-L. Nguyen and Andrzej Szalas. 2014.
On horn knowledge bases in regular description logic with inverse.
In KNOWLEDGE AND SYSTEMS ENGINEERING (KSE 2013), VOL 1, pages 37–49. In series: Advances in Intelligent Systems and Computing #Vol 244. Springer Berlin/Heidelberg. ISBN: 9783319027401.
DOI: 10.1007/978-3-319-02741-8_6.

We study a Horn fragment called Horn-RegI of the regular description logic with inverse RegI, which extends the description logic ALC with inverse roles and regular role inclusion axioms characterized by finite automata. In contrast to the well-known Horn fragmentsEL, DL-Lite, DLP, Horn-SH IQ and Horn-SROIQof description logics, Horn-RegI allows a form of the concept constructor universal restriction to appear at the left hand side of terminological inclusion axioms, while still has PTIME data complexity. Namely, a universal restriction can be used in such places in conjunction with the corresponding existential restriction. We provide an algorithm with PTIME data complexity for checking satisfiability of Horn-RegI knowledge bases.

[122] Son Thanh Cao, Linh Anh Nguyen and Andrzej Szalas. 2014.
WORL: a nonmonotonic rule language for the semantic web.
Vietnam Journal of Computer Science, 1(1):57–69. Springer Berlin/Heidelberg.
DOI: 10.1007/s40595-013-0009-y.

We develop a new Web ontology rule language, called WORL, which combines a variant of OWL 2 RL with eDatalog ¬ . We allow additional features like negation, the minimal number restriction and unary external checkable predicates to occur at the left-hand side of concept inclusion axioms. Some restrictions are adopted to guarantee a translation into eDatalog ¬ . We also develop the well-founded semantics and the stable model semantics for WORL as well as the standard semantics for stratified WORL (SWORL) via translation into eDatalog ¬ . Both WORL with respect to the well-founded semantics and SWORL with respect to the standard semantics have PTime data complexity. In contrast to the existing combined formalisms, in WORL and SWORL negation in concept inclusion axioms is interpreted using nonmonotonic semantics.

2013
[121] Linh Anh Nguyen, Thi-Bich-Loc Nguyen and Andrzej Szalas. 2013.
HornDL: An Expressive Horn Description Logic with PTime Data Complexity.
In Wolfgang Faber, Domenico Lembo, editors, Web Reasoning and Rule Systems, pages 259–264. In series: Lecture Notes in Computer Science #7994. Springer Berlin/Heidelberg. ISBN: 978-3-642-39665-6.
DOI: 10.1007/978-3-642-39666-3_25.

[120] Barbara Dunin-Keplicz, Linh Anh Nguyen and Andrzej Szalas. 2013.
Horn-TeamLog: A Horn Fragment of TeamLog with PTime Data Complexity.
In Costin Bǎdicǎ, Ngoc Thanh Nguyen, Marius Brezovan, editors, Computational Collective Intelligence. Technologies and Applications, pages 143–153. In series: Lecture Notes in Computer Science #8083. Springer Berlin/Heidelberg. ISBN: ISBN: 978-3-642-40494-8.
DOI: 10.1007/978-3-642-40495-5_15.

[119] Linh Anh Nguyen and Andrzej Szalas. 2013.
On the Horn Fragments of Serial Regular Grammar Logics with Converse.
In Dariusz Barbucha, Manh Thanh Le, Robert J. Howlett, Lakhmi C. Jain, editors, Advanced Methods and Technologies for Agent and Multi-Agent Systems: Proceedings of the 7th KES Conference on Agent and Multi-Agent Systems - Technologies and Applications (KES-AMSTA 2013), pages 225–234. In series: Frontiers in Artificial Intelligence and Applications #252. IOS Press. ISBN: 978-1-61499-253-0.
DOI: 10.3233/978-1-61499-254-7-225.

We study Horn fragments of serial multimodal logics which are characterized by regular grammars with converse. Such logics are useful for reasoning about epistemic states of multiagent systems as well as similarity-based approximate reasoning. We provide the first algorithm with PTIME data complexity for checking satisfiability of a Horn knowledge base in a serial regular grammar logic with converse.

[118] Jan Maluszynski and Andrzej Szalas. 2013.
Partiality and Inconsistency in Agents' Belief Bases.
In Dariusz Barbucha, Manh Thanh Le, Robert J. Howlett, Lakhmi C. Jain, editors, Advanced Methods and Technologies for Agent and Multi-Agent Systems: Proceedings of the 7th KES Conference on Agent and Multi-Agent Systems - Technologies and Applications (KES-AMSTA 2013), pages 3–17. In series: Frontiers in Artificial Intelligence and Applications #252. IOS Press. ISBN: 978-1-61499-253-0.
DOI: 10.3233/978-1-61499-254-7-3.

Agents' beliefs can be incomplete and partially inconsistent. The process of agents' belief formation in such contexts has to be supported by suitable tools allowing one to express a variety of inconsistency resolving and nonmonotonic reasoning techniques.In this paper we discuss 4QL*, a general purpose rule-based query language allowing one to use rules with negation in the premises and in the conclusions of rules. It is based on a simple and intuitive semantics and provides uniform tools for lightweight versions of well-known forms of nonmonotonic reasoning. In addition, it is tractable w.r.t. data complexity and captures PTIME queries, so can be used in real-world applications.Reasoning in 4QL* is based on well-supported models. We simplify and at the same time generalize previous definitions of well-supported models and develop a new algorithm for computing such models.

[117] Barbara Dunin-Keplicz, Alina Strachocka, Andrzej Szalas and Rineke Verbrugge. 2013.
Perceiving Speech Acts under Incomplete and Inconsistent Information.
In Dariusz Barbucha, Manh Thanh Le, Robert J. Howlett, Lakhmi C. Jain, editors, Advanced Methods and Technologies for Agent and Multi-Agent Systems: Proceedings of the 7th KES Conference on Agent and Multi-Agent Systems - Technologies and Applications (KES-AMSTA 2013), pages 255–264. In series: Frontiers in Artificial Intelligence and Applications #252. IOS Press. ISBN: 978-1-61499-253-0.
DOI: 10.3233/978-1-61499-254-7-255.

This paper discusses an implementation of four speech acts: assert, concede, request and challenge in a paraconsistent framework. A natural four-valued model of interaction yields multiple new cognitive situations. They are analyzed in the context of communicative relations, which partially replace the concept of trust. These assumptions naturally lead to six types of situations, which often require performing conflict resolution and belief revision.The particular choice of a rule-based, DATALOG$^{\neg \neg}$-like query language 4QL as a four-valued implementation framework ensures that, in contrast to the standard two-valued approaches, tractability of the model is achieved.

[116] Barbara Dunin-Keplicz and Andrzej Szalas. 2013.
Taming Complex Beliefs.
In Ngoc Thanh Nguyen, editor, Transactions on Computational Collective Intelligence XI, pages 1–21. In series: Lecture Notes in Computer Science #8065. Springer Berlin/Heidelberg. ISBN: 978-3-642-41775-7 (print), 978-3-642-41776-4 (online).
DOI: 10.1007/978-3-642-41776-4_1.

A novel formalization of beliefs in multiagent systems has recently been proposed by Dunin-Kęplicz and Szałas. The aim has been to bridge the gap between idealized logical approaches to modeling beliefs and their actual implementations. Therefore the stages of belief acquisition, intermediate reasoning and final belief formation have been isolated and analyzed. In conclusion, a novel semantics reflecting those stages has been provided. This semantics is based on the new concept of epistemic profile, reflecting agent’s reasoning capabilities in a dynamic and unpredictable environment. The presented approach appears suitable for building complex belief structures in the context of incomplete and/or inconsistent information. One of original ideas is that of epistemic profiles serving as a tool for transforming preliminary beliefs into final ones. As epistemic profile can be devised both on an individual and a group level in analogical manner, a uniform treatment of single agent and group beliefs has been achieved.In the current paper these concepts are further elaborated. Importantly, we indicate an implementation framework ensuring tractability of reasoning about beliefs, propose the underlying methodology and illustrate it on an example.

[115] Andrzej Szalas. 2013.
How an agent might think.
Logic journal of the IGPL (Print), 21(3):515–535. Oxford University Press (OUP): Policy A - Oxford Open Option A.
DOI: 10.1093/jigpal/jzs051.

The current article is devoted to extensions of the rule query language 4QL proposed by Małuszyński and Szałas. 4QL is a Datalog<sup>¬¬</sup>-like language, allowing one to use rules with negation in heads and bodies of rules. It is based on a simple and intuitive semantics and provides uniform tools for lightweight versions of well-known forms of non-monotonic reasoning. In addition, 4QL is tractable w.r.t. data complexity and captures PTime queries. In the current article we relax most of restrictions of 4QL, obtaining a powerful but still tractable query language 4QL<sup>+</sup>. In its development we mainly focused on its pragmatic aspects: simplicity, tractability and generality. In the article we discuss our approach and choices made, define a new, more general semantics and investigate properties of 4QL<sup>+</sup>.

[114] Linh Anh Nguyen and Andrzej Szalas. 2013.
Logic-Based Roughification.
In A. Skowron and Z. Suraj, editors, Rough Sets and Intelligent Systems - Professor Zdzisław Pawlak in Memoriam (vol. I), pages 517–543. In series: Intelligent Systems Reference Library #42. Springer Berlin/Heidelberg. ISBN: 978-3-642-30343-2.
DOI: 10.1007/978-3-642-30344-9_19.

The current chapter is devoted to <em>roughification</em>. In the most general setting, we intend the term <em>roughification</em> to refer to methods/techniques of constructing equivalence/similarity relations adequate for Pawlak-like approximations. Such techniques are fundamental in rough set theory. We propose and investigate novel roughification techniques. We show that using the proposed techniques one can often discern objects indiscernible by original similarity relations, what results in improving approximations. We also discuss applications of the proposed techniques in granulating relational databases and concept learning. The last application is particularly interesting, as it shows an approach to concept learning which is more general than approaches based solely on information and decision systems.

[113] Barbara Dunin-Keplicz and Andrzej Szalas. 2013.
Distributed Paraconsistent Belief Fusion.
In Giancarlo Fortino , Costin Badica , Michele Malgeri and Rainer Unland, editors, Intelligent Distributed Computing VI: Proceedings of the 6th International Symposium on Intelligent Distributed Computing - IDC 2012, Calabria, Italy, September 2012, pages 59–69. In series: Studies in Computational Intelligence #446. Springer Berlin/Heidelberg. ISBN: 978-3-642-32523-6.
DOI: 10.1007/978-3-642-32524-3_9.
find book at a swedish library/hitta boken i ett svenskt bibliotek: http://libris.kb.se/bib/13601893

The current paper is devoted to belief fusion when information sources may deliver incomplete and inconsistent information. In such cases paraconsistent and commonsense reasoning techniques can be used to complete missing knowledge and disambiguate inconsistencies. We propose a novel, realistic model of distributed belief fusion and an implementation framework guaranteeing its tractability.

2012
[112] Ha Quang-Thuy, Hoang Thi-Lan-Giao, Linh Anh Nguyen, Hung Son Nguyen, Andrzej Szalas and Tran Thanh-Luong. 2012.
Concept Learning for Description Logic-based Information Systems.
In KSE 2012 - International Conference on Knowledge and Systems Engineering, pages 65–73. IEEE Computer Society.
DOI: 10.1109/KSE.2012.23.

[111] Ha Quang-Thuy, Hoang Thi-Lan-Giao, Linh Anh Nguyen, Nguyen Hung-Son, Andrzej Szalas and Tran Thanh-Luong. 2012.
A Bisimulation-based Method of Concept Learning for Knowledge Bases in Description Logics.
In SoICT 2012 - 3rd International Symposium on Information and Communication Technology, pages 241–249. ACM Press.
DOI: 10.1145/2350716.2350753.

We develop the first bisimulation-based method of concept learning, called BBCL, for knowledge bases in description logics (DLs). Our method is formulated for a large class of useful DLs, with well-known DLs like <em>ALC, SHIQ, SHOIQ, SROIQ</em>. As bisimulation is the notion for characterizing indis-cernibility of objects in DLs, our method is natural and very promising.

[110] Barbara Dunin-Keplicz and Andrzej Szalas. 2012.
Epistemic Profiles and Belief Structures.
In Gordan Jezic , Mario Kusek , Ngoc-Thanh Nguyen , Robert J. Howlett and Lakhmi C. Jain, editors, Agent and Multi-Agent Systems. Technologies and Applications: 6th KES International Conference, KES-AMSTA 2012, Dubrovnik, Croatia, June 25-27, 2012. Proceedings, pages 360–369. In series: Lecture Notes in Computer Science #7327. Springer Berlin/Heidelberg. ISBN: 978-3-642-30946-5, e- 978-3-642-30947-2.
DOI: 10.1007/978-3-642-30947-2_40.

The paper is devoted to a novel formalization of beliefs in multiagent systems. Our aim is to bridge the gap between idealized logical approaches to modeling beliefs and their actual implementations. Therefore the stages of belief acquisition, intermediate reasoning and final belief formation are isolated and analyzed. We give a novel semantics reflecting those stages and suitable for building complex belief structures in the context of incomplete and/or inconsistent information. Namely, an agent starts with constituents, i.e., sets of initial beliefs acquired by perception, expert supplied knowledge, communication with other agents and perhaps other ways. Next, the constituents are transformed into consequents according to agents’ epistemic profiles. Additionally, a uniform treatment of single agent and group beliefs is achieved. Importantly, we indicate an implementation framework ensuring tractability of reasoning about beliefs.

[109] Linh Anh Nguyen and Andrzej Szalas. 2012.
Paraconsistent Reasoning for Semantic Web Agents.
In Ngoc Thanh Nguyen, editor, Transactions on Compuational Collective Intelligence VI, pages 36–55. In series: Lecture Notes in Computer Science #7190. Springer Berlin/Heidelberg. ISBN: 978-3-642-29355-9, e-978-3-642-29356-6.
DOI: 10.1007/978-3-642-29356-6_2.

Description logics refer to a family of formalisms concentrated around concepts, roles and individuals. They are used in many multiagent and Semantic Web applications as a foundation for specifying knowledge bases and reasoning about them. Among them, one of the most important logics is <em>SROIQ</em><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char53.png\" /><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char52.png\" /><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char4F.png\" /><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char49.png\" /><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char51.png\" />, providing the logical foundation for the OWL 2 Web Ontology Language recommended by W3C in October 2009. In the current paper we address the problem of inconsistent knowledge. Inconsistencies may naturally appear in the considered application domains, for example as a result of fusing knowledge from distributed sources. We introduce a number of paraconsistent semantics for <em>SROIQ</em><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char53.png\" /><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char52.png\" /><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char4F.png\" /><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char49.png\" /><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char51.png\" />, including three-valued and four-valued semantics. The four-valued semantics reflects the well-known approach introduced in [5,4] and is considered here for comparison reasons only. We also study the relationship between the semantics and paraconsistent reasoning in <em>SROIQ</em><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char53.png\" /><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char52.png\" /><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char4F.png\" /><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char49.png\" /><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char51.png\" /> through a translation into the traditional two-valued semantics. Such a translation allows one to use existing tools and reasoners to deal with inconsistent knowledge.

[108] Barbara Dunin-Keplicz and Andrzej Szalas. 2012.
Agents in Approximate Environments.
In Jan Ejick and Rineke Verbrugge, editors, Games, Actions and Social Software: Multidisciplinary Aspects, pages 141–163. In series: Lecture Notes in Computer Science #7010. Springer. ISBN: 978-3-642-29325-2 (print), 978-3-642-29326-9 (online).
DOI: 10.1007/978-3-642-29326-9_8.

The starting point of this research is the multimodal approach to modeling multiagent systems, especially Beliefs, Goals and Intention systems. Such an approach is suitable for specifying and verifying many subtle aspects of agents’ informational and motivational attitudes.However, in this chapter we make a shift in a perspective. More precisely, we propose the method of embedding multimodal approaches into a form of approximate reasoning suitable for modeling perception, namely a <em>similarity-based approximate reasoning</em>. We argue that this formalism allows one to both keep the intuitive semantics compatible with that of multimodal logics as well as to model and implement phenomena occurring at the perception level.

[107] Full text  Patrick Doherty, Jonas Kvarnström and Andrzej Szalas. 2012.
Temporal Composite Actions with Constraints.
In Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR), pages 478–488. AAAI Press. ISBN: 978-1-57735-560-1, 978-1-57735-561-8.
Link: http://www.aaai.org/ocs/index.php/KR/KR1...

Complex mission or task specification languages play a fundamentally important role in human/robotic interaction. In realistic scenarios such as emergency response, specifying temporal, resource and other constraints on a mission is an essential component due to the dynamic and contingent nature of the operational environments. It is also desirable that in addition to having a formal semantics, the language should be sufficiently expressive, pragmatic and abstract. The main goal of this paper is to propose a mission specification language that meets these requirements. It is based on extending both the syntax and semantics of a well-established formalism for reasoning about action and change, Temporal Action Logic (TAL), in order to represent temporal composite actions with constraints. Fixpoints are required to specify loops and recursion in the extended language. The results include a sound and complete proof theory for this extension. To ensure that the composite language constructs are adequately grounded in the pragmatic operation of robotic systems, Task Specification Trees (TSTs) and their mapping to these constructs are proposed. The expressive and pragmatic adequacy of this approach is demonstrated using an emergency response scenario.

2011
[106] Jan Maluszynski and Andrzej Szalas. 2011.
Living with Inconsistency and Taming Nonmonotonicity.
In O. de Moor, G. Gottlob, T. Furche, A. Sellers, editors, Datalog Reloaded, pages 334–398. In series: Lecture Notes in Computer Science #6702. Springer Berlin/Heidelberg. ISBN: 978-3-642-24205-2.
DOI: 10.1007/978-3-642-24206-9_22.

In this paper we consider rule-based query languages with negation inbodies and heads of rules, traditionally denoted by DATALOG--. Tractable andat the same time intuitive semantics for DATALOG-- has not been provided evenif the area of deductive databases is over 30 years old. In this paper we identifysources of the problem and propose a query language, which we call 4QL.The 4QL language supports a modular and layered architecture and providesa tractable framework for many forms of rule-based reasoning both monotonicand nonmonotonic. As the underpinning principle we assume openness of theworld, which may lead to the lack of knowledge. Negation in rule heads may leadto inconsistencies. To reduce the unknown/inconsistent zones we introduce simpleconstructs which provide means for application-specific disambiguation ofinconsistent information, the use of Local Closed World Assumption (thus alsoClosed World Assumption, if needed), as well as various forms of default anddefeasible reasoning.

[105] Son Thanh Cao, Linh Anh Nguyen and Andrzej Szalas. 2011.
WORL: A Web Ontology Rule Language.
In Proceedings of the 3rd International Conference on Knowledge and Systems Engineering (KSE), pages 32–39. IEEE. ISBN: 978-1-4577-1848-9.
DOI: 10.1109/KSE.2011.14.

We develop a Web ontology rule language, called WORL, which combines a variant of OWL 2 RL with eDatalog-with-negation. We disallow the features of OWL 2 RL that play the role of constraints (i.e., the ones that are translated to negative clauses), but allow additional features like negation, the minimal number restriction and unary external checkable predicates to occur in the left hand side of concept inclusion axioms. Some restrictions are adopted to guarantee a translation into eDatalog-with-negation. We also develop the well-founded semantics for WORL and the standard semantics for stratified WORL (SWORL) via translation into eDatalog-with-negation. Both WORL and SWORL have PTime data complexity. In contrast to the existing combined formalisms, in WORL and SWORL negation in concept inclusion axioms is interpreted using nonmonotonic semantics.

[104] Patrick Doherty, Barbara Dunin-Keplicz and Andrzej Szalas. 2011.
Tractable model checking for fragments of higher-order coalition logic.
In Liz Sonenberg, Peter Stone, Kagan Tumer, Pinar Yolum, editors, Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems - Volume 2, pages 743–750. AAAI Press. ISBN: 0-9826571-6-1, 978-0-9826571-6-4.
Link: http://dl.acm.org/citation.cfm?id=203172...

A number of popular logical formalisms for representing and reasoning about the abilities of teams or coalitions of agents have been proposed beginning with the Coalition Logic (CL) of Pauly. Ågotnes et al introduced a means of succinctly expressing quantification over coalitions without compromising the computational complexity of model checking in CL by introducing Quantified Coalition Logic (QCL). QCL introduces a separate logical language for characterizing coalitions in the modal operators used in QCL. Boella et al, increased the representational expressibility of such formalisms by introducing Higher-Order Coalition Logic (HCL), a monadic second-order logic with special set grouping operators. Tractable fragments of HCL suitable for efficient model checking have yet to be identified. In this paper, we relax the monadic restriction used in HCL and restrict ourselves to the diamond operator. We show how formulas using the diamond operator are logically equivalent to second-order formulas. This permits us to isolate and define well-behaved expressive fragments of second-order logic amenable to model-checking in PTime. To do this, we appeal to techniques used in deductive databases and quantifier elimination. In addition, we take advantage of the monotonicity of the effectivity function resulting in exponentially more succinct representation of models. The net result is identification of highly expressible fragments of a generalized HCL where model checking can be done efficiently in PTime.

[103] Son Thanh Cao, Anh Linh Nguyen and Andrzej Szalas. 2011.
On the Web Ontology Rule Language OWL 2 RL.
In Piotr Jedrzejowicz, Ngoc Thanh Nguyen and Kiem Hoang, editors, Proceedings of the 3rd International Conference on Computational Collective Intelligence, Technologies and Applications (ICCCI), pages 254–264. In series: Lecture Notes in Computer Science #6922. Springer Berlin/Heidelberg. ISBN: 978-3-642-23934-2.
DOI: 10.1007/978-3-642-23935-9_25.

It is known that the OWL 2 RL Web Ontology Language Profile has PTime data complexity and can be translated into Datalog. However, a knowledge base in OWL 2 RL may be unsatisfiable. The reason is that, when translated into Datalog, the result may consist of a Datalog program and a set of constraints in the form of negative clauses. In this paper we first identify a maximal fragment of OWL 2 RL called OWL 2 RL<sup> + </sup>with the property that every knowledge base expressed in this fragment can be translated into a Datalog program and hence is satisfiable. We then propose some extensions of OWL 2 RL and OWL 2 RL<sup> + </sup> that still have PTime data complexity.

[102] Full text  Patrick Doherty, Tomasz Michalak, Jacek Sroka and Andrzej Szalas. 2011.
Contextual Coalitional Games.
In Mohua Banerjee, Anil Seth, editors, Proceedings of the 4th Indian Conference on Logic and its Applications (ICLA), pages 65–78. In series: Lecture Notes in Artificial Intelligence #6521. Springer Berlin/Heidelberg.
DOI: 10.1007/978-3-642-18026-2_7.

The study of cooperation among agents is of central interest in multi-agent systems research. A popular way to model cooperation is through coalitional game theory. Much research in this area has had limited practical applicability as regards real-world multi-agent systems due to the fact that it assumes<em>deterministic</em> payoffs to coalitions and in addition does not apply to multi-agent environments that are<em>stochastic</em> in nature. In this paper, we propose a novel approach to modeling such scenarios where coalitional games will be contextualized through the use of logical expressions representing environmental and other state, and probability distributions will be placed on the space of contexts in order to model the stochastic nature of the scenarios. More formally, we present a formal representation language for representing contextualized coalitional games embedded in stochastic environments and we define and show how to compute <em>expected Shapley values</em> in such games in a computationally efficient manner. We present the value of the approach through an example involving robotics assistance in emergencies.

[101] Barbara Dunin-Keplicz, Anh Linh Nguyen and Andrzej Szalas. 2011.
Converse-PDL with Regular Inclusion Axioms: A Framework for MAS Logics.
Journal of Applied Non-Classical Logics, 21(1):61–81. Lavoisier.
DOI: 10.3166/jancl.21.61-91.

<em>In this paper we study automated reasoning in the modal logic CPDLreg which is a combination of CPDL (Propositional Dynamic Logic with Converse) and REGc (Regular Grammar Logic with Converse). The logic CPDL is widely used in many areas, including program verification, theory of action and change, and knowledge representation. On the other hand, the logic REGc is applicable in reasoning about epistemic states and ontologies (via Description Logics). The modal logic CPDLreg can serve as a technical foundation for reasoning about agency. Even very rich multi-agent logics can be embedded into CPDLreg via a suitable translation. Therefore, CPDLreg can serve as a test bed to implement and possibly verify new ideas without providing specific automated reasoning techniques for the logic in question. This process can to a large extent be automated. The idea of embedding various logics into CPDLreg is illustrated on a rather advanced logic TEAMLOGK designed to specify teamwork in multi-agent systems. Apart from defining informational and motivational attitudes of groups of agents, TEAMLOGK allows for grading agents' beliefs, goals and intentions. The current paper is a companion to our paper (Dunin-Kęplicz et al., 2010a). The main contribution are proofs of soundness and completeness of the tableau calculus for CPDLreg provided in (Dunin-Kęplicz et al., 2010a).</em>

[100] Linh Anh Nguyen and Andrzej Szalas. 2011.
ExpTime Tableau Decision Procedures for Regular Grammar Logics with Converse.
Studia Logica: An International Journal for Symbolic Logic, 98(3):387–428. Springer Berlin/Heidelberg.
DOI: 10.1007/s11225-011-9341-3.

Grammar logics were introduced by Fariñas del Cerro and Penttonen in 1988 and have been widely studied. In this paper we consider regular grammar logics with converse (<em>REG</em> <sup><em>c</em> </sup>logics) and present sound and complete tableau calculi for the general satisfiability problem of <em>REG</em> <sup><em>c</em> </sup>logics and the problem of checking consistency of an ABox w.r.t. a TBox in a <em>REG</em> <sup><em>c</em> </sup>logic. Using our calculi we develop ExpTime (optimal) tableau decision procedures for the mentioned problems, to which various optimization techniques can be applied. We also prove a new result that the data complexity of the instance checking problem in <em>REG</em> <sup><em>c</em></sup>logics is coNP-complete.

[99] Jan Maluszynski and Andrzej Szalas. 2011.
Logical Foundations and Complexity of 4QL, a Query Language with Unrestricted Negation.
Journal of Applied Non-Classical Logics, 21(2):211–232. Lavoisier.
DOI: 10.3166/jancl.21.211-232.

The paper discusses properties of 4QL, a DATALOG¬¬-like query language, originally outlined by Małuszy´nski and Szałas (Małuszy´nski &amp; Szałas, 2011). 4QL allows one to use rules with negation in heads and bodies of rules. It is based on a simple and intuitive semantics and provides uniform tools for “lightweight” versions of known forms of nonmonotonic reasoning. Negated literals in heads of rules may naturally lead to inconsistencies. On the other hand, rules do not have to attach meaning to some literals. Therefore 4QL is founded on a four-valued semantics, employing the logic introduced in (Małuszy´nski et al., 2008; Vitória et al., 2009) with truth values: ‘true’, ‘false’, ‘inconsistent’ and ‘unknown’. In addition, 4QL is tractable w.r.t. data complexity and captures PTIME queries. Even though DATALOG¬¬ is known as a concept for the last 30 years, to our best knowledge no existing approach enjoys these properties. In the current paper we:<ul><li>investigate properties of well-supported models of 4QL</li><li>prove the correctness of the algorithm for computing well-supported models</li><li>show that 4QL has PTIME data complexity and captures PTIME.</li></ul>

2010
[98] Barbara Dunin-Keplicz, Anh Linh Nguyen and Andrzej Szalas. 2010.
Graded Beliefs, Goals and Intentions.
In Proceedings of the 3rd Workshop on Logical Aspects of Multi-Agent Systems (LAMAS), pages 1–15. AAAI Press.

[97] Anh Linh Nguyen and Andrzej Szalas. 2010.
Three-Valued Paraconsistent Reasoning for Semantic Web Agents.
In Proceedings of the 4th International KES Symposium on Agents and Multi-agent Systems – Technologies and Applications (KES-AMSTA), pages 152–162. In series: Lecture Notes in Artificial Intelligence #6070. Springer. ISBN: 978-3-642-13479-1.
DOI: 10.1007/978-3-642-13480-7_17.

Description logics [1] refer to a family of formalisms concentrated around concepts, roles and individuals. They are used in many multiagent and semantic web applications as a foundation for specifying knowledge bases and reasoning about them. One of widely applied description logics is <em>SHIQ</em><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char53.png\" /><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char48.png\" /><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char49.png\" /><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char51.png\" /> [7,8]. In the current paper we address the problem of inconsistent knowledge. Inconsistencies may naturally appear in the considered application domains, for example as a result of fusing knowledge from distributed sources. We define three three-valued paraconsistent semantics for <em>SHIQ</em><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char53.png\" /><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char48.png\" /><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char49.png\" /><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char51.png\" />, reflecting different meanings of concept inclusion of practical importance. We also provide a quite general syntactic condition of safeness guaranteeing satisfiability of a knowledge base w.r.t. three-valued semantics and define a faithful translation of our formalism into a suitable version of a two-valued description logic. Such a translation allows one to use existing tools and <em>SHIQ</em><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char53.png\" /><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char48.png\" /><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char49.png\" /><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char51.png\" /> reasoners to deal with inconsistent knowledge.

[96] Anh Linh Nguyen and Andrzej Szalas. 2010.
Tableaux with Global Caching for Checking Satisfiability of a Knowledge Base in the Description Logic SH.
Transactions on Computational Collective Intelligence, 1(1):21–38. Springer. ISBN: 978-3-642-15033-3.
DOI: 10.1007/978-3-642-15034-0_2.

Description logics (DLs) are a family of knowledge representation languages which can be used to represent the terminological knowledge of an application domain in a structured and formally well-understood way. DLs can be used, for example, for conceptual modeling or as ontology languages. In fact, OWL (Web Ontology Language), recommended by W3C, is based on description logics. In the current paper we give the first direct ExpTime (optimal) tableau decision procedure, which is not based on transformation or on the pre-completion technique, for checking satisfiability of a knowledge base in the description logic <em>SH</em><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char53.png\" /><img src=\"http://www.springerlink.com/jsMath/fonts/cmsy10/alpha/120/char48.png\" />. Our procedure uses sound global caching and can be implemented as an extension of the highly optimized tableau prover TGC to obtain an efficient program for the mentioned satisfiability problem.

[95] Linh Anh Nguyen and Andrzej Szalas. 2010.
Checking Consistency of an ABox w.r.t. Global Assumptions in PDL.
Fundamenta Informaticae, 102(1):97–113. IOS Press.
DOI: 10.3233/FI-2010-299.

We reformulate Pratts tableau decision procedure of checking satisfiability of a set of formulas in PDL. Our formulation is simpler and its implementation is more direct. Extending the method we give the first Ex PT m E (optimal) tableau decision procedure not based on transformation for checking consistency of an ABox w.r.t. a TBox in PDL (here, PDL is treated as a description logic). We also prove a new result that the data complexity of the instance checking problem in PDL is coNP-complete.

[94] Patrick Doherty and Andrzej Szalas. 2010.
On the Correctness of Rough-Set Based Approximate Reasoning.
In M. Szczuka, M. Kryszkiewicz, S. Ramanna, R. Jensen, Q. Hu, editors, Proceedings of the 7th International Conference on Rough Sets and Current Trends in Computing (RSCTC), pages 327–336. In series: Lecture Notes in Computer Science #6086. Springer. ISBN: 978-3-642-13528-6.
DOI: 10.1007/978-3-642-13529-3_35.

There is a natural generalization of an indiscernibility relation used in rough set theory, where rather than partitioning the universe of discourse into indiscernibility classes, one can consider a covering of the universe by similarity-based neighborhoods with lower and upper approximations of relations defined via the neighborhoods. When taking this step, there is a need to tune approximate reasoning to the desired accuracy. We provide a framework for analyzing self-adaptive knowledge structures. We focus on studying the interaction between inputs and output concepts in approximate reasoning. The problems we address are: -given similarity relations modeling approximate concepts, what are similarity relations for the output concepts that guarantee correctness of reasoning? -assuming that output similarity relations lead to concepts which are not accurate enough, how can one tune input similarities?

[93] Barbara Dunin-Keplicz, Linh Anh Nguyen and Andrzej Szalas. 2010.
A Framework for Graded Beliefs, Goals and Intentions.
Fundamenta Informaticae, 100(1-4):53–76. IOS Press.
DOI: 10.3233/FI-2010-263.

In natural language we often use graded concepts, reflecting different intensity degrees of certain features. Whenever such concepts appear in a given real-life context, they need to be appropriately expressed in its models. In this paper, we provide a framework which allows for extending the BGI model of agency by grading beliefs, goals and intentions. We concentrate on TEAMLOG [6, 7, 8, 9, 12] and provide a complexity-optimal decision method for its graded version TEAMLOG(K) by translating it into CPDLreg (propositional dynamic logic with converse and \"inclusion axioms\" characterized by regular languages). We also develop a tableau calculus which leads to the first EXPTIME (optimal) tableau decision procedure for CPDLreg. As CPDLreg is suitable for expressing complex properties of graded operators, the procedure can also be used as a decision tool for other multiagent formalisms.

[92] Barbara Dunin-Keplicz, Linh Anh Nguyen and Andrzej Szalas. 2010.
A Layered Rule-Based Architecture for Approximate Knowledge Fusion.
COMPUTER SCIENCE AND INFORMATION SYSTEMS, 7(3):617–642. COMSIS CONSORTIUM.
DOI: 10.2298/CSIS100209015D.

In this paper we present a framework for fusing approximate knowledge obtained from various distributed, heterogenous knowledge sources. This issue is substantial in modeling multi-agent systems, where a group of loosely coupled heterogeneous agents cooperate in achieving a common goal. In paper [5] we have focused on defining general mechanism for knowledge fusion. Next, the techniques ensuring tractability of fusing knowledge expressed as a Horn subset of propositional dynamic logic were developed in [13,16]. Propositional logics may seem too weak to be useful in real-world applications. On the other hand, propositional languages may be viewed as sublanguages of first-order logics which serve as a natural tool to define concepts in the spirit of description logics [2]. These notions may be further used to define various ontologies, like e. g. those applicable in the Semantic Web. Taking this step, we propose a framework, in which our Horn subset of dynamic logic is combined with deductive database technology. This synthesis is formally implemented in the framework of HSPDL architecture. The resulting knowledge fusion rules are naturally applicable to real-world data.

[91] Barbara Dunin-Keplicz, Linh Anh Nguyen and Andrzej Szalas. 2010.
Tractable approximate knowledge fusion using the Horn fragment of serial propositional dynamic logic.
International Journal of Approximate Reasoning, 51(3):346–362. Elsevier.
DOI: 10.1016/j.ijar.2009.11.002.

In this paper we investigate a technique for fusing approximate knowledge obtained from distributed, heterogeneous information sources. This issue is substantial, e.g., in modeling multiagent systems, where a group of loosely coupled heterogeneous agents cooperate in achieving a common goal. Information exchange, leading ultimately to knowledge fusion, is a natural and vital ingredient of this process. We use a generalization of rough sets and relations [30], which depends on allowing arbitrary similarity relations. The starting point of this research is [6], where a framework for knowledge fusion in multiagent systems is introduced. Agents individual perceptual capabilities are represented by similarity relations, further aggregated to express joint capabilities of teams, This aggregation, expressing a shift from individual to social level of agents activity, has been formalized by means of dynamic logic. The approach of Doherty et al. (2007) [6] uses the full propositional dynamic logic, which does not guarantee tractability of reasoning. Our idea is to adapt the techniques of Nguyen [26-28] to provide an engine for tractable approximate database querying restricted to a Horn fragment of serial dynamic logic. We also show that the obtained formalism is quite powerful in applications.

2009
[90] Barbara Dunin-Keplicz, Linh Anh Nguyen and Andrzej Szalas. 2009.
Fusing Approximate Knowledge from Distributed Sources.
In Proceedings of the 3rd International Symposium on Intelligent Distributed Computing (IDC), pages 75–86. In series: Studies in Computational Intelligence #237. Springer Berlin/Heidelberg. ISBN: 978-3-642-03213-4, 978-3-642-26930-1.
DOI: 10.1007/978-3-642-03214-1_8.

In this paper we investigate a technique for fusing approximate knowledge obtained from distributed, heterogeneous information sources. We use a generalization of rough sets and relations [14], which depends on allowing arbitrary similarity relations. The starting point of this research is [2], where a framework for knowledge fusion in multi-agent systems is introduced. Agent’s individual perceptual capabilities are represented by similarity relations, further aggregated to express joint capabilities of teams. This aggregation, allowing a shift from individual to social level, has been formalized by means of dynamic logic. The approach of [2] uses the full propositional dynamic logic, not guaranteeing the tractability of reasoning. Therefore the results of [11, 12, 13] are adapted to provide a technical engine for tractable approximate database querying restricted to a Horn fragment of serial PDL. We also show that the obtained formalism is quite powerful in applications.

[89] Linh Anh Nguyen and Andrzej Szalas. 2009.
Checking Consistency of an ABox w.r.t. Global Assumptions in PDL*.
In Proceedings of the 18th Concurrency, Specification and Programming Workshop (CS&P), pages 431–442.

[88] Linh Anh Nguyen and Andrzej Szalas. 2009.
An Optimal Tableau Decision Procedure for Converse-PDL.
In Proceedings of the 1st International Conference on Knowlegde and Systems Engineering (KSE), pages 207–214. IEEE Computer Society. ISBN: 978-1-4244-5086-2.
DOI: 10.1109/KSE.2009.12.

We give a novel tableau calculus and an optimal (EXPTIME) tableau decision procedure based on the calculus for the satisfiability problem of propositional dynamic logic with converse. Our decision procedure is formulated with global caching and can be implemented together with useful optimization techniques.

[87] Dov Gabbay and Andrzej Szalas. 2009.
Annotation Theories over Finite Graphs.
Studia Logica: An International Journal for Symbolic Logic, 93(2-3):147–180. Springer.
DOI: 10.1007/s11225-009-9220-3.

In the current paper we consider theories with vocabulary containing a number of binary and unary relation symbols. Binary relation symbols represent labeled edges of a graph and unary relations represent unique annotations of the graph’s nodes. Such theories, which we call <em>annotation theories</em>, can be used in many applications, including the formalization of argumentation, approximate reasoning, semantics of logic programs, graph coloring, etc. We address a number of problems related to annotation theories over finite models, including satisfiability, querying problem, specification of preferred models and model checking problem. We show that most of considered problems are NPTime- or co-NPTime-complete. In order to reduce the complexity for particular theories, we use second-order quantifier elimination. To our best knowledge none of existing methods works in the case of annotation theories. We then provide a new second-order quantifier elimination method for stratified theories, which is successful in the considered cases. The new result subsumes many other results, including those of [2, 28, 21].

[86] Andrzej Szalas and Alicja Szalas. 2009.
Paraconsistent Reasoning with Words.
In Aspects of Natural Language Processing: Essays Dedicated to Leonard Bolc on the Occasion of His 75th Birthday, pages 43–58. In series: Lecture Notes in Computer Science #5070. Springer. ISBN: 978-3-642-04734-3.
DOI: 10.1007/978-3-642-04735-0_2.
find book at a swedish library/hitta boken i ett svenskt bibliotek: http://libris.kb.se/bib/11741557

Fuzzy logics are one of the most frequent approaches to model uncertainty and vagueness. In the case of fuzzy modeling, degrees of belief and disbelief sum up to 1, which causes problems in modeling the lack of knowledge and inconsistency. Therefore, so called paraconsistent intuitionistic fuzzy sets have been introduced, where the degrees of belief and disbelief are not required to sum up to 1. The situation when this sum is smaller than 1 reflects the lack of knowledge and its value greater than 1 models inconsistency. In many applications there is a strong need to guide and interpret fuzzy-like reasoning using qualitative approaches. To achieve this goal in the presence of uncertainty, lack of knowledge and inconsistency, we provide a framework for qualitative interpretation of the results of fuzzy-like reasoning by labeling numbers with words, like <em>true, false, inconsistent, unknown</em>, reflecting truth values of a suitable, usually finitely valued logical formalism.

[85] Andrzej Szalas and Dov Gabbay. 2009.
Voting by Eliminating Quantifiers.
Studia Logica: An International Journal for Symbolic Logic, 92(3):365–379. Springer.
DOI: 10.1007/s11225-009-9200-7.

Mathematical theory of voting and social choice has attracted much attention. In the general setting one can view social choice as a method of aggregating individual, often conflicting preferences and making a choice that is the best compromise. How preferences are expressed and what is the “best compromise” varies and heavily depends on a particular situation. The method we propose in this paper depends on expressing individual preferences of voters and specifying properties of the resulting ranking by means of first-order formulas. Then, as a technical tool, we use methods of second-order quantifier elimination to analyze and compute results of voting. We show how to specify voting, how to compute resulting rankings and how to verify voting protocols.

[84] Andrzej Szalas and Linh Anh Nguyen. 2009.
EXPTIME Tableaux for Checking Satisfiability of a Knowledge Base in the Description Logic ALC.
In Ngoc Thanh; Kowalczyk, Ryszard; Chen, Shyi-Ming, editors, Proceedings of the 1st International Conference on Computational Collective Intelligence - Semantic Web, Social Networks & Multiagent Systems (ICCCI), pages 437–448. In series: Lecture Notes in Artificial Intelligence #5796. Springer. ISBN: 978-3-642-04440-3 (print), 978-3-642-04441-0 (online).
DOI: 10.1007/978-3-642-04441-0_38.

We give the first ExpTime (optimal) tableau decision procedure for checking satisfiability of a knowledge base in the description logic ALC, not based on transformation that encodes ABoxes by nominals or terminology axioms. Our procedure can be implemented as an extension of the highly optimized tableau prover TGC [12] to obtain an efficient program for the mentioned satisfiability problem.

[83] Linh Anh Nguyen and Andrzej Szalas. 2009.
A tableau calculus for regular grammar logics with converse.
In Proceedings of the 22nd International Conference on Automated Deduction (CADE), pages 421–436. In series: Lecture Notes in Artificial Intelligence #5663. Springer. ISBN: 978-364202958-5.
DOI: 10.1007/978-3-642-02959-2_31.

We give a sound and complete tableau calculus for deciding the general satisfiability problem of regular grammar logics with converse (REG c logics). Tableaux of our calculus are defined as \"and-or\" graphs with global caching. Our calculus extends the tableau calculus for regular grammar logics given by Goré and Nguyen [11] by using a cut rule and existential automaton-modal operators to deal with converse. We use it to develop an ExpTime (optimal) tableau decision procedure for the general satisfiability problem of REG c logics. We also briefly discuss optimizations for the procedure.

2008
[82] Andrzej Szalas. 2008.
Towards Incorporating Background Theories into Quantifier Elimination.
Journal of applied non-classical logics, 18(2-3):325–340. Éditions Hermès-Lavoisier.
DOI: 10.3166/jancl.18.325-340.

In the paper we present a technique for eliminating quantifiers of arbitrary order, in particular of first-order. Such a uniform treatment of the elimination problem has been problematic up to now, since techniques for eliminating first-order quantifiers do not scale up to higher-order contexts and those for eliminating higher-order quantifiers are usually based on a form of monotonicity w.r.t implication (set inclusion) and are not applicable to the first-order case. We make a shift to arbitrary relations \"ordering\" the underlying universe. This allows us to incorporate background theories into higher-order quantifier elimination methods which, up to now, has not been achieved. The technique we propose subsumes many other results, including the Ackermann's lemma and various forms of fixpoint approaches when the \"ordering\" relations are interpreted as implication and reveals the common principle behind these approaches.

[81] Patrick Doherty and Andrzej Szalas. 2008.
Reasoning with Qualitative Preferences and Cardinalities Using Generalized Circumscription.
In Gerhard Brewka, Jérôme Lang, editors, Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR), pages 560–570. AAAI Press. ISBN: 978-1-57735-384-3.

The topic of preference modeling has recently attracted the interest of a number of sub-disciplines in artificial intelligence such as the nonmonotonic reasoning and action and change communities. The approach in these communities focuses on qualitative preferences and preference models which provide more natural representations from a~commonsense perspective. In this paper, we show how generalized circumscription can be used as a highly expressive framework for qualitative preference modeling. Generalized circumscription proposed by Lifschitz allows for predicates (and thus formulas) to be minimized relative to arbitrary pre-orders (reflexive and transitive). Although it has received little attention, we show how it may be used to model and reason about elaborate qualitative preference relations. One of the perceived weaknesses with any type of circumscription is the 2nd-order nature of the representation. The paper shows how a large variety of preference theories represented using generalized circumscription can in fact be reduced to logically equivalent first-order theories in a constructive way. Finally, we also show how preference relations represented using general circumscription can be extended with cardinality constraints and when these extensions can also be reduced to logically equivalent first-order theories.

[80] Dov M. Gabbay, Renate A. Schmidt and Andrzej Szalas. 2008.
Second-Order Quantifier Elimination. Foundations, Computational Aspects and Applications.
Book. In series: Studies in Logics #12. College Publications. 308 pages. ISBN: 978-1-904987-56-7, 1-904-98-756-7.
link: http://www.amazon.com/Second-Order-Quant...

In recent years there has been an increasing use of logical methods and significant new developments have been spawned in several areas of computer science, ranging from artificial intelligence and software engineering to agent-based systems and the semantic web. In the investigation and application of logical methods there is a tension between: * the need for a representational language strong enough to express domain knowledge of a particular application, and the need for a logical formalism general enough to unify several reasoning facilities relevant to the application, on the one hand, and * the need to enable computationally feasible reasoning facilities, on the other hand. Second-order logics are very expressive and allow us to represent domain knowledge with ease, but there is a high price to pay for the expressiveness. Most second-order logics are incomplete and highly undecidable. It is the quantifiers which bind relation symbols that make second-order logics computationally unfriendly. It is therefore desirable to eliminate these second-order quantifiers, when this is mathematically possible; and often it is. If second-order quantifiers are eliminable we want to know under which conditions, we want to understand the principles and we want to develop methods for second-order quantifier elimination. This book provides the first comprehensive, systematic and uniform account of the state-of-the-art of second-order quantifier elimination in classical and non-classical logics. It covers the foundations, it discusses in detail existing second-order quantifier elimination methods, and it presents numerous examples of applications and non-standard uses in different areas. These include: * classical and non-classical logics, * correspondence and duality theory, * knowledge representation and description logics, * commonsense reasoning and approximate reasoning, * relational and deductive databases, and * complexity theory. The book is intended for anyone interested in the theory and application of logics in computer science and artificial intelligence.

[79] Full text  Aida Vitoria, Andrzej Szalas and Jan Maluszynski. 2008.
Four-valued Extension of Rough Sets.
In Proceedings of the 3rd International Conference Rough Sets and Knowledge Technology (RSKT), pages 106–114. In series: Lecture Notes in Computer Science #5009. Springer. ISBN: 978-3-540-79720-3.
DOI: 10.1007/978-3-540-79721-0_19.

Rough set approximations of Pawlak [15] are sometimes generalized by using similarities between objects rather than elementary sets. In practical applications, both knowledge about properties of objects and knowledge of similarity between objects can be incomplete and inconsistent. The aim of this paper is to define set approximations when all sets, and their approximations, as well as similarity relations are four-valued. A set is four-valued in the sense that its membership function can have one of the four logical values: unknown (<strong>u</strong>), false (<strong>f</strong>), inconsistent (<strong>i</strong>), or true (<strong>t</strong>). To this end, a new implication operator and set-theoretical operations on four-valued sets, such as set containment, are introduced. Several properties of lower and upper approximations of four-valued sets are also presented.

[78] Jan Maluszynski, Aida Vitoria and Andrzej Szalas. 2008.
Paraconsistent Logic Programs with Four-valued Rough Sets.
In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pages 41–51. In series: Lecture Notes in Computer Science #5306. Springer. ISBN: 978-3-540-88423-1 (print), 978-3-540-88425-5 (online).
DOI: 10.1007/978-3-540-88425-5_5.

This paper presents a language for defining four-valued rough sets and to reason about them. Our framework brings together two major fields: rough sets and paraconsistent logic programming. On the one hand it provides a paraconsistent approach, based on four-valued rough sets, for integrating knowledge from different sources and reasoning in the presence of inconsistencies. On the other hand, it also caters for a specific type of uncertainty that originates from the fact that an agent may perceive different objects of the universe as being indiscernible. This paper extends the ideas presented in [9]. Our language allows the user to define similarity relations and use the approximations induced by them in the definition of other four-valued sets. A positive aspect is that it allows users to tune the level of uncertainty or the source of uncertainty that best suits applications.

2007
[77] Barbara Dunin-Keplicz and Andrzej Szalas. 2007.
Towards Approximate BGI Systems.
In Proceedings of the 5th International Central and Eastern European Conference on Multi-Agent Systems (CEEMAS), pages 277–287. In series: Lecture Notes in Artificial Intelligence #4696. Springer Berlin/Heidelberg. ISBN: 9783540752530.
DOI: 10.1007/978-3-540-75254-7_28.

This paper focuses on modelling perception and vague concepts in the context of multiagent Bgi (<em>Beliefs, Goals</em> and <em>Intentions</em>) systems. The starting point is the multimodal formalization of such systems. Then we make a shift from Kripke structures to similarity structures, allowing us to model perception and vagueness in an uniform way, “compatible” with the multimodal approach. As a result we introduce and discuss <em>approximate B</em> <em>gi</em> <em>systems</em>, which can also be viewed as a way to implement multimodal specifications of Bgi systems in the context of perception.

[76] Full text  Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 2007.
Communication between agents with heterogeneous perceptual capabilities.
Information Fusion, 8(1):56–69. Elsevier.
DOI: 10.1016/j.inffus.2005.05.006.

In real world applications robots and software agents often have to be equipped with higher level cognitive functions that enable them to reason, act and perceive in changing, incompletely known and unpredictable environments. One of the major tasks in such circumstances is to fuse information from various data sources. There are many levels of information fusion, ranging from the fusing of low level sensor signals to the fusing of high level, complex knowledge structures. In a dynamically changing environment even a single agent may have varying abilities to perceive its environment which are dependent on particular conditions. The situation becomes even more complex when different agents have different perceptual capabilities and need to communicate with each other. In this paper, we propose a framework that provides agents with the ability to fuse both low and high level approximate knowledge in the context of dynamically changing environments while taking account of heterogeneous and contextually limited perceptual capabilities. To model limitations on an agent's perceptual capabilities we introduce the idea of partial tolerance spaces. We assume that each agent has one or more approximate databases where approximate relations are represented using lower and upper approximations on sets. Approximate relations are generalizations of rough sets. It is shown how sensory and other limitations can be taken into account when constructing and querying approximate databases for each respective agent. Complex relations inherit the approximativeness of primitive relations used in their definitions. Agents then query these databases and receive answers through the filters of their perceptual limitations as represented by (partial) tolerance spaces and approximate queries. The techniques used are all tractable. © 2005 Elsevier B.V. All rights reserved.

[75] Full text  D.M. Gabbay and Andrzej Szalas. 2007.
Second-order quantifier elimination in higher-order contexts with applications to the semantical analysis of conditionals.
Studia Logica: An International Journal for Symbolic Logic, 87(1):37–50. Springer.
DOI: 10.1007/s11225-007-9075-4.

Second-order quantifier elimination in the context of classical logic emerged as a powerful technique in many applications, including the correspondence theory, relational databases, deductive and knowledge databases, knowledge representation, commonsense reasoning and approximate reasoning. In the current paper we first generalize the result of Nonnengart and Szalas [17] by allowing second-order variables to appear within higher-order contexts. Then we focus on a semantical analysis of conditionals, using the introduced technique and Gabbay's semantics provided in [10] and substantially using a third-order accessibility relation. The analysis is done via finding correspondences between axioms involving conditionals and properties of the underlying third-order relation. © 2007 Springer Science+Business Media B.V.

[74] Full text  Patrick Doherty and Andrzej Szalas. 2007.
A correspondence framework between three-valued logics and similarity-based approximate reasoning.
Fundamenta Informaticae, 75(1-4):179–193. IOS Press.

This paper focuses on approximate reasoning based on the use of similarity spaces. Similarity spaces and the approximated relations induced by them are a generalization of the rough set-based approximations of Pawlak [17, 18]. Similarity spaces are used to define neighborhoods around individuals and these in turn are used to define approximate sets and relations. In any of the approaches, one would like to embed such relations in an appropriate logic which can be used as a reasoning engine for specific applications with specific constraints. We propose a framework which permits a formal study of the relationship between approximate relations, similarity spaces and three-valued logics. Using ideas from correspondence theory for modal logics and constraints on an accessibility relation, we develop an analogous framework for three-valued logics and constraints on similarity relations. In this manner, we can provide a tool which helps in determining the proper three-valued logical reasoning engine to use for different classes of approximate relations generated via specific types of similarity spaces. Additionally, by choosing a three-valued logic first, the framework determines what constraints would be required on a similarity relation and the approximate relations induced by it. Such information would guide the generation of approximate relations for specific applications.

[73] Patrick Doherty, Barbara Dunin-Keplicz and Andrzej Szalas. 2007.
Dynamics of approximate information fusion.
In Proceedings of the International Conference on Rough Sets and Emerging Intelligent Systems Paradigms (RSEISP), pages 668–677. In series: Lecture Notes in Artificial Intelligence #4585. Springer Berlin/Heidelberg. ISBN: 978-3-540-73450-5.
DOI: 10.1007/978-3-540-73451-2_70.

The multi-agent system paradigm has proven to be a useful means of abstraction when considering distributed systems with interacting components. It is often the case that each component may be viewed as an intelligent agent with specific and often limited perceptual capabilities. It is also the case that these agent components may be used as information sources and such sources may be aggregated to provide global information about particular states, situations or activities in the embedding environment. This paper investigates a framework for information fusion based on the use of generalizations of rough set theory and the use of dynamic logic as a basis for aggregating similarity relations among objects where the similarity relations represent individual agents perceptual capabilities or limitations. As an added benefit, it is shown how this idea may also be integrated into description logics.

[72] Jan Maluszynski, Andrzej Szalas and Aida Vitoria. 2007.
A Four-Valued Logic for Rough Set-Like Approximate Reasoning.
In James F. Peters, Andrzej Skowron, Ivo Düntsch, Jerzy Grzymala-Busse, Ewa Orlowska and Lech Polkowski, editors, Transactions on Rough Sets VI, pages 176–190. In series: Lecture Notes in Computer Science #4374/2007. Springer. ISBN: 3-540-71198-8, 978-3-540-71198-8.
DOI: 10.1007/978-3-540-71200-8_11.
find book at a swedish library/hitta boken i ett svenskt bibliotek: http://libris.kb.se/bib/11381912

Annotation The LNCS journal Transactions on Rough Sets is devoted to the entire spectrum of rough sets related issues, from logical and mathematical foundations, through all aspects of rough set theory and its applications, such as data mining, knowledge discovery, and intelligent information processing, to relations between rough sets and other approaches to uncertainty, vagueness, and incompleteness, such as fuzzy sets and theory of evidence. Volume VI of the Transactions on Rough Sets (TRS) commemorates the life and work of Zdzislaw Pawlak (1926-2006). His legacy is rich and varied. Prof. Pawlak's research contributions have had far-reaching implications inasmuch as his works are fundamental in establishing new perspectives for scientific research in a wide spectrum of fields. This volume of the TRS presents papers that reflect the profound influence of a number of research initiatives by Professor Pawlak. In particular, this volume introduces a number of new advances in the foundations and applications of artificial intelligence, engineering, logic, mathematics, and science. These advances have significant implications in a number of research areas such as the foundations of rough sets, approximate reasoning, bioinformatics, computational intelligence, cognitive science, data mining, information systems, intelligent systems, machine intelligence, and security.

2006
[71] Ewa Orlowska, Alberto Policriti and Andrzej Szalas. 2006.
Algebraic and Relational Deductive Tools.
Conference Proceedings. In series: Journal of Applied Non-Classical Logics #??. Éditions Hermès-Lavoisier.
Note: Special Issue

[70] Full text  Andrzej Szalas and Jerzy Tyszkiewicz. 2006.
On the fixpoint theory of equality and its applications.
In Proceedings of the 9th International Conference on Relational Methods in Computer Science and 4th International Workshop on Applications of Kleene Algebra (RelMiCS/AKA), pages 388–401. In series: Lecture Notes in Computer Science #4136. Springer.
DOI: 10.1007/11828563_26.

In the current paper we first show that the fixpoint theory of equality is decidable. The motivation behind considering this theory is that second-order quantifier elimination techniques based on a theorem given in [16], when successful, often result in such formulas. This opens many applications, including automated theorem. proving, static verification of integrity constraints in databases as well as reasoning with weakest sufficient and strongest necessary conditions.

[69] Andrzej Szalas. 2006.
Second-order Reasoning in Description Logics.
Journal of applied non-classical logics, 16(3 - 4):517–530. Éditions Hermès-Lavoisier.
DOI: 10.3166/jancl.16.517-530.

Description logics refer to a family of formalisms concentrated around concepts, roles and individuals. They belong to the most frequently used knowledge representation formalisms and provide a logical basis to a variety of well known paradigms. The main reasoning tasks considered in the area of description logics are those reducible to subsumption. On the other hand, any knowledge representation system should be equipped with a more advanced reasoning machinery. Therefore in the current paper we make a step towards integrating description logics with second-order reasoning. One of the important motivations behind introducing second-order formalism follows from the fact that many forms of commonsense and nonmonotonic reasoning used in AI can be modelled within the second-order logic. To achieve our goal we first extend description logics with a possibility to quantify over concepts. Since one of the main criticisms against the use of second-order formalisms is their complexity, we next propose second-order quantifier elimination techniques applicable to a large class of description logic formulas. Finally we show applications of the techniques, in particular in reasoning with circumscribed concepts and approximated terminological formulas.

[68] Ewa Orlowska and Andrzej Szalas. 2006.
Quantifier Elimination in Elementary Set Theory.
In W. MacCaull, I. Duentsch, M. Winter, editors, Proceedings of the 8th International Conference on Relational Methods in Computer Science (RelMiCS), pages 237–248. In series: Lecture Notes in Computer Science #3929. Springer Berlin/Heidelberg.
DOI: 10.1007/11734673_19.

In the current paper we provide two methods for quantifier elimination applicable to a large class of formulas of the elementary set theory. The first one adapts the Ackermann method [1] and the second one adapts the fixpoint method of [20]. We show applications of the proposed techniques in the theory of correspondence between modal logics and elementary set theory. The proposed techniques can also be applied in an automated generation of proof rules based on the semantic-based translation of axioms of a given logic into the elementary set theory.

[67] Patrick Doherty, Witold Lukaszewicz, Andrzej Skowron and Andrzej Szalas. 2006.
Knowledge Representation Techniques.: a rough set approach.
Book. In series: Studies in Fuzziness and Soft Computing #202. Springer. 342 pages. ISBN: 978-3-540-33518-4, 3-540-33518-8.
DOI: 10.1007/3-540-33519-6.
find book at a swedish library/hitta boken i ett svenskt bibliotek: http://libris.kb.se/hitlist?d=libris&q=9...

The basis for the material in this book centers around a long term research project with autonomous unmanned aerial vehicle systems. One of the main research topics in the project is knowledge representation and reasoning. The focus of the research has been on the development of tractable combinations of approximate and nonmonotonic reasoning systems. The techniques developed are based on intuitions from rough set theory. Efforts have been made to take theory into practice by instantiating research results in the context of traditional relational database or deductive database systems. This book contains a cohesive, self-contained collection of many of the theoretical and applied research results that have been achieved in this project and for the most part pertain to nonmonotonic and approximate reasoning systems developed for an experimental unmanned aerial vehicle system used in the project. This book should be of interest to the theoretician and applied researcher alike and to autonomous system developers and software agent and intelligent system developers.

[66] Full text  Patrick Doherty, Martin Magnusson and Andrzej Szalas. 2006.
Approximate Databases: A support tool for approximate reasoning.
Journal of applied non-classical logics, 16(1-2):87–118. Éditions Hermès-Lavoisier.
DOI: 10.3166/jancl.16.87-117.
Note: Special issue on implementation of logics

This paper describes an experimental platform for approximate knowledge databases called the Approximate Knowledge Database (AKDB), based on a semantics inspired by rough sets. The implementation is based upon the use of a standard SQL database to store logical facts, augmented with several query interface layers implemented in JAVA through which extensional, intensional and local closed world nonmonotonic queries in the form of crisp or approximate logical formulas can be evaluated tractably. A graphical database design user interface is also provided which simplifies the design of databases, the entering of data and the construction of queries. The theory and semantics for AKDBs is presented in addition to application examples and details concerning the database implementation.

2005
[65] Full text  Patrick Doherty, Andrzej Szalas and Witold Lukaszewicz. 2005.
Similarity, approximations and vagueness.
In Dominik Slezak, Guoyin Wang, Marcin S. Szczuka, Ivo Düntsch, Yiyu Yao, editors, Proceedings of the 10th International Conference on Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing (RSFDGrC), pages 541–550. In series: Lecture Notes in Artificial Intelligence #3641. Springer. ISBN: 3-540-28653-5.
DOI: 10.1007/11548669_56.

The relation of similarity is essential in understanding and developing frameworks for reasoning with vague and approximate concepts. There is a wide spectrum of choice as to what properties we associate with similarity and such choices determine the nature of vague and approximate concepts defined in terms of these relations. Additionally, robotic systems naturally have to deal with vague and approximate concepts due to the limitations in reasoning and sensor capabilities. Halpern [1] introduces the use of subjective and objective states in a modal logic formalizing vagueness and distinctions in transitivity when an agent reasons in the context of sensory and other limitations. He also relates these ideas to a solution to the Sorities and other paradoxes. In this paper, we generalize and apply the idea of similarity and tolerance spaces [2,3,4,5], a means of constructing approximate and vague concepts from such spaces and an explicit way to distinguish between an agent’s objective and subjective states. We also show how some of the intuitions from Halpern can be used with similarity spaces to formalize the above-mentioned Sorities and other paradoxes.

[64] Michali Grabowski and Andrzej Szalas. 2005.
A Technique for Learning Similarities on Complex Structures with Applications to Extracting Ontologies.
In Proceedings of the 3rd Atlantic Web Intelligence Conference (AWIC), pages 991–995. In series: Lecture Notes in Computer Science #3528. Springer.
DOI: 10.1007/11495772_29.

A general similarity-based algorithm for extracting ontologies from data has been provided in [1]. The algorithm works over arbitrary approximation spaces, modeling notions of similarity and mereological part-of relations (see, e.g., [2, 3, 4, 5]). In the current paper we propose a novel technique of machine learning similarity on tuples on the basis of similarities on attribute domains. The technique reflects intuitions behind tolerance spaces of [6] and similarity spaces of [7]. We illustrate the use of the technique in extracting ontologies from data.

[63] Full text  Martin Magnusson, Patrick Doherty and Andrzej Szalas. 2005.
An Experimental Platform for Approximate Databases.
In 3rd joint SAIS-SSL event on Artificial Intelligence and Learning Systems,2005.

2004
[62] Full text  Patrick Doherty, Steven Kertes, Martin Magnusson and Andrzej Szalas. 2004.
Towards a logical analysis of biochemical pathways.
In José Júlio Alferes and João Alexandre Leite, editors, Proceedings of the 9th European Conference on Logics in Artificial Intelligence (JELIA), pages 667–679. In series: Lecture Notes in Computer Science #3229. Springer. ISBN: 978-3-540-23242-1.
DOI: 10.1007/978-3-540-30227-8_55.

Biochemical pathways or networks are generic representations used to model many different types of complex functional and physical interactions in biological systems. Models based on experimental results are often incomplete, e.g., reactions may be missing and only some products are observed. In such cases, one would like to reason about incomplete network representations and propose candidate hypotheses, which when represented as additional reactions, substrates, products, would complete the network and provide causal explanations for the existing observations. In this paper, we provide a logical model of biochemical pathways and show how abductive hypothesis generation may be used to provide additional information about incomplete pathways. Hypothesis generation is achieved using weakest and strongest necessary conditions which represent these incomplete biochemical pathways and explain observations about the functional and physical interactions being modeled. The techniques are demonstrated using metabolism and molecular synthesis examples.

[61] Full text  Patrick Doherty, Steven Kertes, Martin Magnusson and Andrzej Szalas. 2004.
Towards a Logical Analysis of Biochemical Reactions (Extended abstract).
In Ramon López de Mántaras, Lorenza Saitta, editors, Proceedings of the 16th European Conference on Artificial Intelligence (ECAI), pages 997–998. IOS Press. ISBN: 1-58603-452-9.

We provide a logical model of biochemical reactions and show how hypothesis generation using weakest sufficient and strongest necessary conditions may be used to provide additional information in the context of an incomplete model of metabolic pathways.

[60] Full text  Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 2004.
Approximate Databases and Query Techniques for Agents with Heterogenous Perceptual Capabilities.
In Proceedings of the 7th International Conference on Information Fusion, pages 175–182. ISIF. ISBN: 91-7056-115-X.

In this paper, we propose a framework that provides software and robotic agents with the ability to ask approximate questions to each other in the context of heterogeneous and contextually limited perceptual capabilities. The framework focuses on situations where agents have varying ability to perceive their environments. These limitations on perceptual capability are formalized using the idea of tolerance spaces. It is assumed that each agent has one or more approximate databases where approximate relations are represented using intuitions from rough set theory. It is shown how sensory and other limitations can be taken into account when constructing approximate databases for each respective agent. Complex relations inherit the approximativeness inherent in the sensors and primitive relations used in their definitions. Agents then query these databases and receive answers through the filters of their perceptual limitations as represented by tolerance spaces and approximate queries. The techniques used are all tractable.

[59] Full text  Patrick Doherty and Andrzej Szalas. 2004.
On the Correspondence between Approximations and Similarity.
In Shusaku Tsumoto, Roman Slowinski, Jan Komorowski and Jerzy W. Grzymala-Busse, editors, Proceedings of the International Conference on Rough Sets and Current Trends in Computing (RSCTC), pages 143–152. In series: Lecture Notes in Computer Science #3066. Springer.
DOI: 10.1007/978-3-540-25929-9_16.

This paper focuses on the use and interpretation of approximate databases where both rough sets and indiscernibility partitions are generalized and replaced by approximate relations and similarity spaces. Similarity spaces are used to define neighborhoods around individuals and these in turn are used to define approximate sets and relations. There is a wide spectrum of choice as to what properties the similarity relation should have and how this affects the properties of approximate relations in the database. In order to make this interaction precise, we propose a technique which permits specification of both approximation and similarity constraints on approximate databases and automatic translation between them. This technique provides great insight into the relation between similarity and approximation and is similar to that used in modal correspondence theory. In order to automate the translations, quantifier elimination techniques are used.

[58] Full text  Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 2004.
Approximative Query Techniques for Agents with Heterogeneous Ontologies and Perceptive Capabilities.
In Didier Dubois, Christopher A. Welty, Mary-Anne Williams, editors, Proceedings of the 9th International Conference on the Principles of Knowledge Representation and Reasoning, pages 459–468. AAAI Press. ISBN: 978-1-57735-199-3.

In this paper, we propose a framework that provides software and robotic agents with the ability to ask approximate questions to each other in the context of heterogeneous ontologies and heterogeneous perceptive capabilities.The framework combines the use of logic-based techniques with ideas from approximate reasoning. Initial queries by an agent are transformed into approximate queries using weakest sufficient and strongest necessary conditions on the query and are interpreted as lower and upper approximations on the query. Once the base communication ability is provided, the framework is extended to situations where there is not only a mismatch between agent ontologies, but the agents have varying ability to perceive their environments. This will affect each agent’s ability to ask and interpret results of queries. Limitations on perceptive capability are formalized using the idea of tolerance spaces.

[57] Patrick Doherty, Jaroslaw Kachniarz and Andrzej Szalas. 2004.
Using Contextually Closed Queries for Local Closed-World Reasoning in Rough Knowledge Databases.
In Andrzej Skowron,Lech Polkowski ,Sankar K Pal, editors, Rough-Neural Computing: Techniques for Computing with Words, pages 219–250. In series: Cognitive Technologies #??. Springer. ISBN: 978-3-540-43059-9, 35-4043-059-8.
find book at a swedish library/hitta boken i ett svenskt bibliotek: http://libris.kb.se/bib/14144444
find book in another country/hitta boken i ett annat land: http://www.worldcat.org/title/rough-neur...

Soft computing comprises various paradigms dedicated to approximately solving real-world problems, e.g., in decision making, classification or learning; among these paradigms are fuzzy sets, rough sets, neural networks, and genetic algorithms.It is well understood now in the soft computing community that hybrid approaches combining various paradigms provide very promising attempts to solving complex problems. Exploiting the potential and strength of both neural networks and rough sets, this book is devoted to rough-neurocomputing which is also related to the novel aspect of computing based on information granulation, in particular to computing with words. It provides foundational and methodological issues as well as applications in various fields.

[56] Patrick Doherty, Witold Lukaszewicz, Andrzej Skowron and Andrzej Szalas. 2004.
Approximation Transducers and Trees: A Technique for Combining Rough and Crisp Knowledge.
In Andrzej Skowron,Lech Polkowski ,Sankar K Pal, editors, Rough-Neural Computing: Techniques for Computing with Words, pages 189–218. In series: Cognitive Technologies #??. Springer. ISBN: 978-3-540-43059-9, 35-4043-059-8.
find book at a swedish library/hitta boken i ett svenskt bibliotek: http://libris.kb.se/bib/14144444
find book in another country/hitta boken i ett annat land: http://www.worldcat.org/search?qt=worldc...

Soft computing comprises various paradigms dedicated to approximately solving real-world problems, e.g., in decision making, classification or learning; among these paradigms are fuzzy sets, rough sets, neural networks, and genetic algorithms.It is well understood now in the soft computing community that hybrid approaches combining various paradigms provide very promising attempts to solving complex problems. Exploiting the potential and strength of both neural networks and rough sets, this book is devoted to rough-neurocomputing which is also related to the novel aspect of computing based on information granulation, in particular to computing with words. It provides foundational and methodological issues as well as applications in various fields.

2003
[55] Patrick Doherty, W. Lukaszewicz, Skowron Andrzej and Andrzej Szalas. 2003.
Knowledge Representation and Approximate Reasoning.
Conference Proceedings. In series: Fundamenta Informaticae #2003(57):2-4. IOS Press.
Note: Special Issue

[54] Andrzej Szalas. 2003.
On a logical approach to estimating computational complexity of potentially intractable problems.
In G. Goos, J. Hartmanis, and J. van Leeuwen, editors, Proceedings of the 14th International Symposium on Fundamentals of Computation Theory (FCT), pages 423–431. In series: Lecture Notes in Computer Science #2751. Springer.
DOI: 10.1007/978-3-540-45077-1_39.

In the paper we present a purely logical approach to estimating computational complexity of potentially intractable problems. The approach is based on descriptive complexity and second-order quantifier elimination techniques. We illustrate the approach on the case of the transversal hypergraph problem, TRANSHYP, which has attracted a great deal of attention. The complexity of the problem remains unsolved for over twenty years. Given two hypergraphs, G and H, TRANSHYP depends on checking whether G = H-d, where H-d is the transversal hypergraph of H. In the paper we provide a logical characterization of minimal transversals of a given hypergraph and prove that checking whether G subset of or equal to H-d is tractable. For the opposite inclusion the Problem still remains open. However, we interpret the resulting quantifier sequences in terms of determinism and bounded nondeterminism. The results give better upper bounds than those known from the literature, e.g., in the case when hypergraph H, has a sub-logarithmic number of hyperedges and (for the deterministic case) all hyperedges have the cardinality bounded by a function sub-linear wrt maximum of sizes of G and H.

[53] Patrick Doherty, A Skowron, Witold Lukaszewicz and Andrzej Szalas. 2003.
1st International Workshop on Knowledge Representation and Approximate Reasoning (KR&AR).

[52] Full text  Patrick Doherty, M Grabowski, Witold Lukaszewicz and Andrzej Szalas. 2003.
Towards a framework for approximate ontologies.
Fundamenta Informaticae, 57(2-4):147–165. IOS Press.

Currently, there is a great deal of interest in developing tools for the generation and use of ontologies on the WWW. These knowledge structures are considered essential to the success of the semantic web, the next phase in the evolution of the WWW. Much recent work with ontologies assumes that the concepts used as building blocks are crisp as opposed to approximate. It is a premise of this paper that approximate concepts and ontologies will become increasingly more important as the semantic web becomes a reality. We propose a framework for specifying, generating and using approximate ontologies. More specifically, (1) a formal framework for defining approximate concepts, ontologies and operations on approximate concepts and ontologies is presented. The framework is based on intuitions from rough set theory, (2) algorithms for automatically generating approximate ontologies from traditional crisp ontologies or from large data sets together with additional knowledge are presented. The knowledge will generally be related to similarity measurements between individual objects in the data sets, or constraints of a logical nature which rule out particular constellations of concepts and dependencies in generated ontologies. The techniques for generating approximate ontologies are parameterizable. The paper provides specific instantiations and examples.

[51] Full text  Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 2003.
On mutual understanding among communicating agents.
In B. Dunin-Keplicz and R. Verbrugge, editors, Proceedings of the International Workshop on Formal Approaches to Multi-Agent Systems (FAMAS), pages 83–97.

[50] Full text  Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 2003.
Tolerance Spaces and Approximative Representational Structures.
In Proceedings of the 26th German Conference on Artificial Intelligence (KI), pages 475–489. In series: Lecture Notes in Computer Science #2821. Springer.
DOI: 10.1007/978-3-540-39451-8_35.

In traditional approaches to knowledge representation, notions such as tolerance measures on data, distance between objects or individuals, and similarity measures between primitive and complex data structures are rarely considered. There is often a need to use tolerance and similarity measures in processes of data and knowledge abstraction because many complex systems which have knowledge representation components such as robots or software agents receive and process data which is incomplete, noisy, approximative and uncertain. This paper presents a framework for recursively constructing arbitrarily complex knowledge structures which may be compared for similarity, distance and approximativeness. It integrates nicely with more traditional knowledge representation techniques and attempts to bridge a gap between approximate and crisp knowledge representation. It can be viewed in part as a generalization of approximate reasoning techniques used in rough set theory. The strategy that will be used is to define tolerance and distance measures on the value sets associated with attributes or primitive data domains associated with particular applications. These tolerance and distance measures will be induced through the different levels of data and knowledge abstraction in complex representational structures. Once the tolerance and similarity measures are in place, an important structuring generalization can be made where the idea of a tolerance space is introduced. Use of these ideas is exemplified using two application domains related to sensor modeling and communication between agents.

[49] Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 2003.
Information Granules for Intelligent Knowledge Structures.
In Guoyin Wang, Qing Liu, Yiyu Yao, Andrzej Skowron, editors, Proceedings of the 9th International Conference on Rough Sets, Fuzzy Sets, Data Mining and Granular Computing (RSFDGrC), pages 405–412. In series: Lecture Notes in Computer Science #2639. Springer. ISBN: 978-3-540-14040-5.
DOI: 10.1007/3-540-39205-X_68.

The premise of this paper is that the acquisition, aggregation, merging and use of information requires some new ideas, tools and techniques which can simplify the construction, analysis and use of what we call ephemeral knowledge structures. Ephemeral knowledge structures are used and constructed by granular agents. Each agent contains its own granular information structure and granular information structures of agents can be combined together. The main concept considered in this paper is an information granule. An information granule is a concise conceptual unit that can be integrated into a larger information infrastructure consisting of other information granules and dependencies between them. The novelty of this paper is that it provides a concise and formal definition of a particular view of information granule and its associated operators, as required in advanced knowledge representation applications.

2002
[48] Andrzej Szalas. 2002.
Second-order quantifier elimination in modal contexts.
In Sergio Flesca, Sergio Greco, Nicola Leone, Giovambattista Ianni, editors, Proceedings of the 8th European Conference on Logics in Artificial Intelligence (JELIA), pages 223–232. In series: Lecture Notes in Computer Science #2424. Springer. ISBN: 978-354044190-8.
DOI: 10.1007/3-540-45757-7_19.

Second-order quantifier elimination in the context of classical logic emerged as a powerful technique in many applications, including the correspondence theory, relational databases, deductive and knowledge databases, knowledge representation, commonsense reasoning and approximate reasoning. In the current paper we generalize the result of [19] by allowing modal operators. This allows us to provide a unifying framework for many applications, that require the use of intensional concepts. Examples of applications of the technique in AI are also provided.

[47] Full text  Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 2002.
CAKE: A computer aided knowledge engineering technique.
In Frank van Harmelen, editor, Proceedings of the 15th European Conference on Artificial Intelligence,2002, pages 220–224. IOS Press.

Introduction: Logic engineering often involves the development of modeling tools and inference mechanisms (both standard and non-standard) which are targeted for use in practical applications where expressiveness in representation must be traded off for efficiency in use. Some representative examples of such applications would be the structuring and querying of knowledge on the semantic web, or the representation and querying of epistemic states used with softbots, robots or smart devices. In these application areas, declarative representations of knowledge enhance the functionality of such systems and also provide a basis for insuring the pragmatic properties of modularity and incremental composition. In addition, the mechanisms developed should be tractable, but at the same time, expressive enough to represent such aspects as default reasoning, or approximate or incomplete representations of the environments in which the entities in question are embedded or used, be they virtual or actual. [...]

2001
[46] Jaroslaw Kachniarz and Andrzej Szalas. 2001.
On a Static Approach to Verification of Integrity Constraints in Relational Databases.
In Eva Orlowska, Andrzej Szalas, editors, Relational Methods for Computer Science Applications, pages 97–109. In series: Studies in Fuzziness and Soft Computing #65. Springer Physica-Verlag. ISBN: 3-7908-1365-6.
Find book at a Swedish library/Hitta boken i ett svenskt bibliotek: http://libris.kb.se/hitlist?d=libris&q=3...
Find book in another country/Hitta boken i ett annat land: http://www.worldcat.org/search?q=3-7908-...

[45] Ewa Orlowska and Andrzej Szalas. 2001.
Relational Methods for Computer Science Applications.
In series: Studies in Fuziness and Soft Computing #??. Springer Physica Verlag. 297 pages. ISBN: 37-9081-365-6, 978-37-9081-365-4.
Find book in another country/Hitta boken i ett annat land: http://www.worldcat.org/search?q=37-9081...

This volume addresses all current aspects of relational methods and their applications in computer science. It presents a broad variety of fields and issues in which theories of relations provide conceptual or technical tools. The contributions address such subjects as relational methods in programming, relational constraints, relational methods in linguistics and spatial reasoning, relational modelling of uncertainty. All contributions provide the readers with new and original developments in the respective fields.The reader thus gets an interdisciplinary spectrum of the state of the art of relational methods and implementation-oriented solutions of problems related to these areas

[44] Full text  Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 2001.
Computing strongest necessary and weakest sufficient conditions of first-order formulas.
In 17th International Joint Conference on Artificial Intelligence,2001. Morgan Kaufmann.

2000
[43] Jaroslaw Kachniarz and Andrzej Szalas. 2000.
Algorithms based on Symbolic Transformations of Logical Formulas in the RDL Language.
In Proceedings of the 2nd Conference on Applications of Computer Science in Mathematics and Economy, pages 101–115. WSIiE, Olsztyn, Poland.

[42] Jaroslaw Kachniarz and Andrzej Szalas. 2000.
On Rule-Based Approach to the Construction of Logical Transformers.
In Proceedings of the 1st International Workshop on Rule-Based Programming (RULE), pages 57–71. Springer Physica-Verlag.

[41] Full text  Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 2000.
Efficient reasoning using the local closed-world assumption.
In Proceedings of the 9th International Conference on Artificial Intelligence: Methodology, Systems and Applications (AIMSA), pages 49–58. In series: Lecture Notes in Computer Science #1904. Springer. ISBN: 3-540-41044-9.
DOI: 10.1007/3-540-45331-8_5.

We present a sound and complete, tractable inference method for reasoning with localized closed world assumptions (LCWA’s) which can be used in applications where a reasoning or planning agent can not assume complete information about planning or reasoning states. This <em>Open World Assumption</em> is generally necessary in most realistic robotics applications. The inference procedure subsumes that described in Etzioni et al [9], and others. In addition, it provides a great deal more expressivity, permitting limited use of negation and disjunction in the representation of LCWA’s, while still retaining tractability. The ap- proach is based on the use of circumscription and quantifier elimination techniques and inference is viewed as querying a deductive database. Both the preprocessing of the database using circumscription and quan- tifier elimination, and the inference method itself, have polynomial time and space complexity.

1999
[40] Andreas Nonnengart, Hans-Jürgen Ohlbach and Andrzej Szalas. 1999.
Elimination of Predicate Quantifiers.
In Logic, Language and Reasoning. Essays in Honor of Dov Gabbay, Part I, pages 159–181. Kluwer Academic Publishers.

[39] Full text  Patrick Doherty, Jaroslaw Kachniarz and Andrzej Szalas. 1999.
Meta-queries on deductive databases.
Fundamenta Informaticae, 40(1):17–30. IOS Press.
DOI: 10.3233/FI-1999-40102.

We introduce the notion of a meta-query on relational databases and a technique which can be used to represent and solve a number of interesting problems from the area of knowledge representation using logic. The technique is based on the use of quantifier elimination and may also be used to query relational databases using a declarative query language called SHQL (Semi-Horn Query Language), introduced in [6]. SHQL is a fragment of classical first-order predicate logic and allows us to define a query without supplying its explicit definition. All SHQL queries to the database can be processed in polynomial time (both on the size of the input query and the size of the database). We demonstrate the use of the technique in problem solving by structuring logical puzzles from the Knights and Knaves domain as SHQL meta-queries on relational databases. We also provide additional examples demonstrating the flexibility of the technique. We conclude with a description of a newly developed software tool, The Logic Engineer, which aids in the description of algorithms using transformation and reduction techniques such as those applied in the meta-querying approach.

[38] Full text  Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1999.
Declarative PTIME queries for relational databases using quantifier elimination.
Journal of logic and computation (Print), 9(5):737–758. Oxford University Press.
DOI: 10.1093/logcom/9.5.737.

In this paper, we consider the problem of expressing and computing queries on relational deductive databases in a purely declarative query language, called SHQL (Semi-Horn Query Language). Assuming the relational databases in question are ordered, we show that all SHQL queries are computable in PTIME (polynomial time) and the whole class of PTIME queries is expressible in SHQL. Although similar results have been proven for fixpoint languages and extensions to datalog, the claim is that SHQL has the advantage of being purely declarative, where the negation operator is interpreted as classical negation, mixed quantifiers may be used and a query is simply a restricted first-order theory not limited by the rule-based syntactic restrictions associated with logic programs in general. We describe the PTIME algorithm used to compute queries in SHQL which is based in part on quantifier elimination techniques and also consider extending the method to incomplete relational databases using intuitions related to circumscription techniques.

1998
[37] Leonard Bolc, Krzysztof Dziewicki, Piotr Rychlik and Andrzej Szalas. 1998.
Wnioskowanie w logikach nieklasycznych: Automatyzacja wnioskowania.
Book. Academic Pub. PLJ (Akademicka Oficyna Wydawnicza PLJ). 159 pages. ISBN: 83-7101-403-1, 978-83-7101-403-1.
Find book in another country/Hitta boken i ett annat land: http://www.worldcat.org/search?q=83-7101...

[36] Andreas Nonnengart and Andrzej Szalas. 1998.
A Fixpoint Approach to Second-Order Quantifier Elimination with Applications to Correspondence Theory.
In Ewa Orlowska, editor, Logic at work: essays dedicated to the memory of Helena Rasiowa, pages 307–328. In series: Studies in Fuzziness and Soft Computing #24. Physica Verlag. ISBN: 3-7908-1164-5.
Find book at a Swedish library/Hitta boken i ett svenskt bibliotek: http://libris.kb.se/hitlist?d=libris&q=3...
Find book in another country/Hitta boken i ett annat land: http://www.worldcat.org/search?q=3-7908-...

[35] Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1998.
General domain circumscription and its effective reductions.
Fundamenta Informaticae, 36(1):23–55. IOS Press.
DOI: 10.3233/FI-1998-3612.

We first define general domain circumscription (GDC) and provide it with a semantics. GDC subsumes existing domain circumscription proposals in that it allows varying of arbitrary predicates, functions, or constants, to maximize the minimization of the domain of a theory. We then show that for the class of semi-universal theories without function symbols, that the domain circumscription of such theories can be constructively reduced to logically equivalent first-order theories by using an extension of the DLS algorithm, previously proposed by the authors for reducing second-order formulas. We also show that for a certain class of domain circumscribed theories, that any arbitrary second-order circumscription policy applied to these theories is guaranteed to be reducible to a logically equivalent first-order theory. In the case of semi-universal theories with functions and arbitrary theories which are not separated, we provide additional results, which although not guaranteed to provide reductions in all cases, do provide reductions in some cases. These results are based on the use of fixpoint reductions.

1997
[34] Full text  Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1997.
Computing circumscription revisited: A reduction algorithm.
Journal of automated reasoning, 18(3):297–336. Kluwer Academic Publishers.
DOI: 10.1023/A:1005722130532.

In recent years, a great deal of attention has been devoted to logics of common-sense reasoning. Among the candidates proposed, circumscription has been perceived as an elegant mathematical technique for modeling nonmonotonic reasoning, but difficult to apply in practice. The major reason for this is the second-order nature of circumscription axioms and the difficulty in finding proper substitutions of predicate expressions for predicate variables. One solution to this problem is to compile, where possible, second-order formulas into equivalent first-order formulas. Although some progress has been made using this approach, the results are not as strong as one might desire and they are isolated in nature. In this article, we provide a general method that can be used in an algorithmic manner to reduce certain circumscription axioms to first-order formulas. The algorithm takes as input an arbitrary second-order formula and either returns as output an equivalent first-order formula, or terminates with failure. The class of second-order formulas, and analogously the class of circumscriptive theories that can be reduced, provably subsumes those covered by existing results. We demonstrate the generality of the algorithm using circumscriptive theories with mixed quantifiers (some involving Skolemization), variable constants, nonseparated formulas, and formulas with n-ary predicate variables. In addition, we analyze the strength of the algorithm, compare it with existing approaches, and provide formal subsumption results.

1996
[33] Andrzej Szalas. 1996.
On Natural Deduction in First-Order Fixpoint Logics.
Fundamenta Informaticae, 26(1):81–94. IOS Press.
DOI: 10.3233/FI-1996-2616.

In the current paper we present a powerful technique of obtaining natural deduction proof systems for first-order fixpoint logics. The term fixpoint logics refers collectively to a class of logics consisting of modal logics with modalities definable at meta-level by fixpoint equations on formulas. The class was found very interesting as it contains most logics of programs with e.g. dynamic logic, temporal logic and the ¯-calculus among them. In this paper we present a technique that allows us to derive automatically natural deduction systems for modal logics from fixpoint equations defining the modalities

[32] Wojciech Penczek and Andrzej Szalas. 1996.
Proceedings of the 21st International Symposium on Mathematical Foundations of Computer Science (MFCS).
Conference Proceedings. In series: Lecture Notes in Computer Science #1113. Springer Verlag. ISBN: 978-3-540-61550-7.
Link: http://www.springer.com/computer/foundat...

[31] Full text  Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1996.
Declarative ptime queries to relational databases.
Technical Report. In series: LITH-IDA-R #34. Department of Computer and Information Science, Linköping University.

[30] Full text  Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1996.
General domain circumscription and its first-order reduction.
Technical Report. In series: LITH-IDA-R #1. Department of Computer and Information Science, Linköping University.

[29] Full text  Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1996.
A reduction result for circumscribed semi-horn formulas.
Fundamenta Informaticae, 28(3,4):261–272. IOS Press.
DOI: 10.3233/FI-1996-283404.

Circumscription has been perceived as an elegant mathematical technique for modeling nonmonotonic and commonsense reasoning, but difficult to apply in practice due to the use of second-order formulas. One proposal for dealing with the computational problems is to identify classes of first-order formulas whose circumscription can be shown to be equivalent to a first-order formula. In previous work, we presented an algorithm which reduces certain classes of second-order circumscription axioms to logically equivalent first-order formulas. The basis for the algorithm is an elimination lemma due to Ackermann. In this paper, we capitalize on the use of a generalization of Ackermann's Lemma in order to deal with a subclass of universal formulas called <em>semi-Horn formulas</em>. Our results subsume previous results by Kolaitis and Papadimitriou regarding a characterization of circumscribed definite logic programs which are first-order expressible. The method for distinguishing which formulas are reducible is based on a boundedness criterion. The approach we use is to first reduce a circumscribed semi-Horn formula to a fixpoint formula which is reducible if the formula is bounded, otherwise not. In addition to a number of other extensions, we also present a fixpoint calculus which is shown to be sound and complete for bounded fixpoint formulas.

[28] Full text  Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1996.
Explaining explanation closure.
In Zbigniew W. Ras, Maciek Michalewicz, editors, Proceedings of the 9th International Symposium on Methodologies for Intelligent Systems,1996, pages 521–530. In series: Lecture Notes in Computer Science #1079. Springer Berlin/Heidelberg. ISBN: 3-540-61286-6.
DOI: 10.1007/3-540-61286-6_176.

Recently, Haas, Schubert, and Reiter, have developed an alternative approach to the frame problem which is based on the idea of using <em>explanation closure axioms</em>. The claim is that there is a monotonic solution for characterizing nonchange in serial worlds with fully specified actions, where one can have both a succinct representation of frame axioms and an effective proof theory for the characterization. In the paper, we propose a circumscriptive version of explanation closure, PMON, that has an effective proof theory and works for both context dependent and nondeterministic actions. The approach retains representational succinctness and a large degree of elaboration tolerance, since the process of generating closure axioms is fully automated and is of no concern to the knowledge engineer. In addition, we argue that the monotonic/nonmonotonic dichotomy proposed by others is not as sharp as previously claimed and is not fully justified.

[27] Full text  Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1996.
General domain circumscription and its first-order reduction.
In Dov Gabbay, Hans Olbach, editors, Proceedings of the 1st International Conference on Formal and Applied Practical Reasoning (FAPR), pages 93–109. In series: Lecture Notes in Computer Science #1085. Springer Berlin/Heidelberg. ISBN: 978-3-540-61313-8.
DOI: 10.1007/3-540-61313-7_65.

We first define general domain circumscription (GDC) and provide it with a semantics. GDC subsumes existing domain circumscription proposals in that it allows varying of arbitrary predicates, functions, or constants, to maximize the minimization of the domain of a theory We then show that for the class of semi-universal theories without function symbols, that the domain circumscription of such theories can be constructively reduced to logically equivalent first-order theories by using an extension of the DLS algorithm, previously proposed by the authors for reducing second-order formulas. We also isolate a class of domain circumscribed theories, such that any arbitrary second-order circumscription policy applied to these theories is guaranteed to be reducible to a logically equivalent first-order theory. In the case of semi-universal theories with functions and arbitrary theories which are not separated, we provide additional results, which although not guaranteed to provide reductions in all cases, do provide reductions in some cases. These results are based on the use of fixpoint reductions.

1995
[26] Leonard Bolc and Andrzej Szalas. 1995.
Time and Logic: A Computational Approach.
CRC Press. 325 pages. ISBN: 1-85728-233-7, 978-18-5728-233-7.
Find book at a Swedish library/Hitta boken i ett svenskt bibliotek: http://libris.kb.se/hitlist?d=libris&q= ...
Find book in another country/Hitta boken i ett annat land: http://www.worldcat.org/search?q= 978-18...

Time and logic are central driving concepts in science and technology. In this book, some of the major current developments in our understanding and application of temporal logic are presented in computational terms. \"Time and Logic: A Computational Approach\" should be a useful sourcebook for those within the specific field of temporal logic, as well as providing valuable introductory material for those seeking an entry into this increasingly important area of theoretical computing.; The emphasis of the book is on presenting a broad range of approaches to computational applications. The techniques used will also be applicable in many cases to formalize beyond temporal logic alone, and it is hoped that adaptation to many different logics of programmes will be facilitated. Throughout, the authors have kept implementation-oriented solutions in mind.; The book begins with an introduction to the basic ideas of temporal logic. Successive chapters then examine particular aspects of the temporal theoretical computing domain, relating their applications to familiar areas of research, such as stochastic process theory, automata theory, established proof systems, model checking, relational logic and classical predicate logic. This should be a useful addition to the library of all theoretical computer scientists, providing a synthesis of well established results in temporal logic with the most up-to-date findings of some of the world's leading theoreticians.

[25] Andrzej Szalas. 1995.
Temporal Logic: A Standard Approach.
In Leonard Bolc, Andrzej Szalas, editors, Time And Logic: A Computational Approach, pages 1–50. UCL Press Ltd.. ISBN: 1-85728-233-7, 978-1857282337.
Find book at a Swedish library/Hitta boken i ett svenskt bibliotek: http://libris.kb.se/hitlist?d=libris&q=1...
Find book in another country/Hitta boken i ett annat land: http://www.worldcat.org/search?q=978-185...

[24] Leonard Bolc, Krzysztof Dziewicki, Piotr Rychlik and Andrzej Szalas. 1995.
Wnioskowanie w logikach nieklasycznych: Podstawy teoretyczne.
Book. Academic Pub. PLJ (Akademicka Oficyna Wydawnicza PLJ). 247 pages. ISBN: 9788371012884.
Find book in another country/Hitta boken i ett annat land: http://www.worldcat.org/search?q=9788371...

Prezentowana książka stanowi drugi tom dwutomowej monografii poświeconej wnioskowaniu w logikach nieklasycznych. Opracowanie to obejmuje takie formalizmy jak logiki modalne, logiki wielowartościowe i mechanizmy wnioskowania niemonotonicznego. W pierwszym tomie przedstawione zostały podstawy teoretyczne wnioskowania w wybranych logikach nieklasycznych. Tom drugi poświęcony jest zagadnieniom automatyzacji procesu wnioskowania.

[23] Full text  Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1995.
A characterization result for circumscribed normal logic programs. Revised version accepted for publication: Special issue of honor of H. Rasiowa, Fundamenta Informaticae.
Technical Report. In series: LITH-IDA-R #20. Department of Computer and Information Science, Linköping University.

[22] Full text  Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1995.
Computing circumscription revisited.
In Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI), pages 1502–1508. ISBN: 978-1558603639.
Note: Volume 2. Preliminary report

1994
[21] Andrzej Szalas. 1994.
On an Automated Translation of Modal Proof Rules into Formulas of the Classical Logic.
Journal of Applied Non-Classical Logics, 4(2):119–127. Éditions Hermès-Lavoisier.

In this paper we study correspondences between modal proof rules and the classical logic. The method we apply is based on an Ackermann's technique of eliminating second-order quantifiers from formulas. We show that the process of finding suitable correspondences can be reduced to a few simple steps. Moreover, the whole technique can be fully mechanized. We thus provide the reader with a powerful tool, useful in automated translations between modal logics and the classical logic.

[20] Andrzej Szalas. 1994.
Genetic Algorithms for Decision Problems.
In Proceedings of the 6th International Conference on Artificial Intelligence and Information-Control Systems of Robots (AIICSR), pages 383–390. World Scientific. ISBN: 981-02-1877-X.

[19] Full text  Patrick Doherty, Witold Lukaszewicz and Andrzej Szalas. 1994.
Computing circumscription revisited: A reduction algorithm.
Technical Report. In series: LITH-IDA-R #94-42. Department of Computer and Information Science, Linköping University.

In recent years, a great deal of attention has been devoted to logics of \"commonsense\" reasoning. Among the candidates proposed, circumscription has been perceived as an elegant mathematical technique for modeling nonmonotonic reasoning, but difficult to apply in practice. The major reason for this is the nd-order nature of circumscription axioms and the difficulty in finding proper substitutions of predicate expressions for predicate variables. One solution to this problem is to compile, where possible, nd-order formulas into equivalent 1st-order formulas. Although some progress has been made using this approach, the results are not as strong as one might desire and they are isolated in nature. In this article, we provide a general method which can be used in an algorithmic manner to reduce circumscription axioms to 1st-order formulas. The algorithm takes as input an arbitrary 2nd-order formula and either returns as output an equivalent 1st-order formula, or terminates with failure. The class of 2nd-order formulas, and analogously the class of circumscriptive theories which can be reduced, provably subsumes those covered by existing results. We demonstrate the generality of the algorithm using circumscriptive theories with mixed quantifiers (some involving Skolemization), variable constants, non-separated formulas, and formulas with n-ary predicate variables. In addition, we analyze the strength of the algorithm and compare it with existing approaches providing formal subsumption results.

1993
[18] Andrzej Szalas. 1993.
On the Correspondence between Modal and Classical Logic: An Automated Approach.
Journal of logic and computation (Print), 3(6):605–620. Oxford University Press.
DOI: 10.1093/logcom/3.6.605.

The current paper is devoted to automated techniques in the correspondence theory. The theory we deal with concerns the problem of finding classical first-order axioms corresponding to propositional modal schemas. Given a modal schema and a semantics base method of translating propositional modal formulae into classical first-order ones, we try to derive automatically classica first-order formulae characterizing precisely the class of frames validating the schema. The technique we consider can, in many cases, be easily applied even without computer support. Although we mainly concentrate on Kripke semantics, the technique we apply is much more general, as it is based on elimination of second-order quantifiers from formulae. We show many examples of application of the method. These can also serve as new, automated proofs of considered correspondences.

1992
[17] Andrzej Szalas. 1992.
Axiomatizing Fixpoint Logics.
Information Processing Letters, 41(4):175–180. Elsevier.
DOI: 10.1016/0020-0190(92)90175-U.

[16] Andrzej Szalas. 1992.
Zarys dedukcyjnych metod automatycznego wnioskowania.
Book. Academic Pub. RM (Akademicka Oficyna Wydawnicza RM). 120 pages. ISBN: 83-9004-517-6, 978-83-9004-517-7.

1991
[15] Andrzej Szalas. 1991.
On Strictly Arithmetical Completeness in Logics of Programs.
Theoretical Computer Science, 79(2):341–355. Elsevier.
DOI: 10.1016/0304-3975(91)90336-Z.

We introduce and discuss a notion of strictly arithmetical completeness related to relative completeness of Cook (1978) and arithmetical completeness of Harel (1978). We present a powerful technique of obtaining strictly arithmetical axiomatizations of logics of programs. Given a model-theoretic semantics of a logic and a set of formulae defining (in a metalanguage) its nonclassical connectives, we automatically derive strictly arithmetically complete and sound proof systems for this logic. As examples of application of the technique we obtain new axiomatizations of algorithmic logic, (concurrent) dynamic logic and temporal logic.

[14] Andrzej Szalas and Jolanta Warpechowska. 1991.
Loglan.
Book. Wydawnictwa Naukowo-Techniczne WNT. 172 pages. ISBN: 83-2041-295-1, 978-83-2041-295-6.
Note: In Polish; Volume 78, Biblioteka Inżynierii Oprogramowania
Find book in another country/Hitta boken i ett annat land: http://www.worldcat.org/search?q=83-2041...

1989
[13] Uwe Petermann and Andrzej Szalas. 1989.
On Temporal Logic for Distributed Systems and its Application to Processes Communicating by Interrupts.
Fundamenta Informaticae, 12(2):191–204. IOS Press.

1988
[12] Andrzej Szalas. 1988.
Towards the Temporal Approach to Abstract Data Types.
Fundamenta Informaticae, 11(1):49–64. IOS Press.

[11] Andrzej Szalas. 1988.
An Incompleteness Result in Process Algebra.
Information Processing Letters, 29(2):67–70. Elsevier.
DOI: 10.1016/0020-0190(88)90030-0.

[10] Leszek Holenderski and Andrzej Szalas. 1988.
Propositional Description of Finite Cause-Effect Structures.
Information Processing Letters, 27(3):111–117. Elsevier.
DOI: 10.1016/0020-0190(88)90064-6.

An alternative method of describing semantics of cause-effect structures is presented. It is based on a model of discrete dynamic systems. The model is similar to a condition-event Petri net, differing in the way restrictions on the alterability of actions are imposed.

[9] Andrzej Szalas and Leszek Holenderski. 1988.
Incompleteness of First-Order Temporal Logic with Until.
Theoretical Computer Science, 57(2-3):317–325. Elsevier.
DOI: 10.1016/0304-3975(88)90045-X.

The results presented in this paper concern the axiomatizability problem of first-order temporal logic with linear and discrete time. We show that the logic is incomplete, i.e., it cannot be provided with a finitistic and complete proof system. We show two incompleteness theorems. Although the first one is weaker (it assumes some first-order signature), we decided to present it, for its proof is much simpler and contains an interesting fact that finite sets are characterizable by means of temporal formulas. The second theorem shows that the logic is incomplete independently of any particular signature.

1987
[8] Andrzej Szalas. 1987.
A Complete Axiomatic Characterization of First-Order Temporal Logic of Linear Time.
Theoretical Computer Science, 54(2-3):199–214. Elsevier.
DOI: 10.1016/0304-3975(87)90129-0.

As shown in (Szalas, 1986, 1986, 1987) there is no finitistic and complete axiomatization of First-Order Temporal Logic of linear and discrete time. In this paper we give an infinitary proof system for the logic. We prove that the proof system is sound and complete. We also show that any syntactically consistent temporal theory has a model. As a corollary we obtain that the Downward Theorem of Skolem, Lowenheim and Tarski holds in the case of considered logic.

[7] Andrzej Szalas. 1987.
Arithmetical Axiomatization of First-Order Temporal Logic.
Information Processing Letters, 26(3):111–116. Elsevier.
DOI: 10.1016/0020-0190(87)90047-0.

[6] R. J. Cunningham, Andreas Nonnengart and Andrzej Szalas. 1987.
A Compositional Method for the Design and Proof of Asynchronous Processes.
In Proceedings of the 4th Annual ESPRIT Conference (ESPRIT), pages 566–580. North-Holland. ISBN: 0-444-70333-0.

1986
[5] Andrzej Szalas. 1986.
Concerning the Semantic Consequence Relation in First-Order Temporal Logic.
Theoretical Computer Science, 47(3):329–334. Elsevier.
DOI: 10.1016/0304-3975(86)90157-X.

In this paper we consider the first-order temporal logic with linear and discrete time. We prove that the set of tautologies of this logic is not arithmetical (i.e., it is neither <em>Σ</em><sup>0</sup><sub><em>n</em></sub> nor <em>Π</em><sup>0</sup><sub><em>n</em></sub> for any natural number <em>n</em>). Thus we show that there is no finitistic and complete axiomatization of the considered logic.

1985
[4] Uwe Petermann and Andrzej Szalas. 1985.
A Note on PCI: Distributed Processes Communicating by Interrupts.
SIGPLAN notices, 20(3):37–46. ACM Press.
DOI: 10.1145/382284.382390.

[3] Andrzej Szalas and Danuta Szczepaska. 1985.
Exception Handling in Parallel Computations.
SIGPLAN notices, 20(10):95–104. ACM Press.
DOI: 10.1145/382286.382385.

1984
[2] Andrzej Szalas. 1984.
On an Application of Algorithmic Theory of Stacks.
Fundamenta Informaticae, 7(3):378–388. IOS Press.

1981
[1] Andrzej Szalas. 1981.
Algorithmic Logic with Recursive Functions.
Fundamenta Informaticae, 4(4):975–995. IOS Press.