Fundamenta Informaticae - Volume 113, issue 1

Authors: Osorio, Mauricio | Marek, Victor W.

Article Type: Research Article

DOI: 10.3233/FI-2011-595

Citation: Fundamenta Informaticae, vol. 113, no. 1, pp. v-vi, 2011

Authors: Chávez-Bosquez, Oscar | Pozos-Parra, Pilar | Lengyel, Florian

Article Type: Research Article

Abstract: The Course Timetabling Problem consists of the weekly scheduling of lectures of a collection of university courses, subject to certain constraints. The International Timetabling Competitions, ITC-2002 and ITC-2007, have been organized with the aim of creating a common formulation for comparison of solution proposals. This paper discusses the design and implementation of an extendable family of sorting-based mechanisms, called Sort Then Fix (STF) algorithms. ITC-2002 and ITC-2007 Post Enrolment based Course Timetabling problem instances were used in this study. The STF approach is deterministic, and does not require swapping or backtracking. Almost all solutions run in less than 10% of …the ITC-2002 and less than 2% of the ITC-2007 benchmark times, respectively. Show more

Keywords: Course Timetabling Problem, International Timetabling Competition, STF Algorithm, Scheduling Problem, Deterministic Search

DOI: 10.3233/FI-2011-596

Citation: Fundamenta Informaticae, vol. 113, no. 1, pp. 1-18, 2011

Authors: Confalonieri, Roberto | Nieves, Juan Carlos

Article Type: Research Article

Abstract: In this paper, we define a class of nested logic programs, called Nested Logic Programs with Ordered Disjunction (LPODs+ ), which makes it possible to specify conditional (qualitative) preferences by means of nested preference statements. To this end, we augment the syntax of Logic Programs with Ordered Disjunction (LPODs) to capture more general expressions. We define the LPODs+ semantics in a simple way and we extend most of the results of LPODs showing how our approach generalizes the LPODs framework in a proper way. We also show how the LPODs+ semantics can be computed in terms of a …translation procedure that maps a nested ordered disjunction program (OD+ -program) into a disjunctive logic program. Show more

Keywords: Answer Set Programming, Preference Handling, Nested Preferences

DOI: 10.3233/FI-2011-597

Citation: Fundamenta Informaticae, vol. 113, no. 1, pp. 19-39, 2011

Authors: Nieves, Juan Carlos | Confalonieri, Roberto

Article Type: Research Article

Abstract: In this paper, we introduce a possibilistic argumentation-based decision making framework which is able to capture uncertain information and exceptions/defaults. In particular, we define the concept of a possibilistic decision making framework which is based on a possibilistic default theory, a set of decisions and a set of prioritized goals. This set of goals captures user preferences related to the achievement of a particular state in a decision making problem. By considering the inference of the possibilistic well-founded semantics, the concept of argument with respect to a decision is defined. This argument captures the feasibility of reaching a goal by …applying a decision in a given context. The inference in the argumentation decision making framework is based on basic argumentation semantics. Since some basic argumentation semantics can infer more than one possible scenario of a possibilistic decision making problem, we define some criteria for selecting potential solutions of the problem. Show more

Keywords: Argumentation Theory, Well-Founded Semantics, Decision Making

DOI: 10.3233/FI-2011-598

Citation: Fundamenta Informaticae, vol. 113, no. 1, pp. 41-61, 2011

Authors: De Ita, Guillermo | Marcial-Romero, J. Raymundo | Hernández, José Antonio

Article Type: Research Article

Abstract: The #SAT problem is a classical #P-complete problem even for monotone, Horn and two conjunctive formulas (the last known as #2SAT). We present a novel branch and bound algorithm to solve the #2SAT problem exactly. Our procedure establishes a new threshold where #2SAT can be computed in polynomial time. We show that for any 2-CF formula F with n variables where #2SAT(F) ≤ p(n), for some polynomial p, #2SAT(F) is computed in polynomial time. This is a new way to measure the degree of difficulty for solving #2SAT and, according to such measure our algorithm allows to determine a boundary …between ‘hard’ and ‘easy’ instances of the #2SAT problem. Show more

Keywords: #2SAT Problem, Branch-Bound Algorithm, Polynomial Thresholds, Efficient Counting

DOI: 10.3233/FI-2011-599

Citation: Fundamenta Informaticae, vol. 113, no. 1, pp. 63-77, 2011

Authors: Everardo Pérez, Flavio Omar | Aguilera Ramírez, Fernando Antonio

Article Type: Research Article

Abstract: The Artificial Intelligence (AI) has taken a leading role in many activities which used to be made “by hand”; one of them is the musical composition. Such task now has another alternative implementation, through the support of software that can compose different musical genres to the point where a computer can compose pieces with some autonomy. This paper proposes Armin, a system dedicated to the electronic trance music composition. Armins aim is to provide a trance music composition to serve as a template or a base audio file, ready to add more instruments in a mastering (remastering) production Additionally, it …seeks to enable greater collaboration between a machine and a human, both seen as musical composers. Show more

Keywords: Armin, Automatic Music Composition, Algorithmic Composition, Answer Set Programming, Trance Music, Artificial Intelligence

DOI: 10.3233/FI-2011-600

Citation: Fundamenta Informaticae, vol. 113, no. 1, pp. 79-96, 2011