Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Purchase individual online access for 1 year to this journal.
Price: EUR 410.00Impact Factor 2024: 0.4
Fundamenta Informaticae is an international journal publishing original research results in all areas of theoretical computer science. Papers are encouraged contributing:
- solutions by mathematical methods of problems emerging in computer science
- solutions of mathematical problems inspired by computer science.
Topics of interest include (but are not restricted to): theory of computing, complexity theory, algorithms and data structures, computational aspects of combinatorics and graph theory, programming language theory, theoretical aspects of programming languages, computer-aided verification, computer science logic, database theory, logic programming, automated deduction, formal languages and automata theory, concurrency and distributed computing, cryptography and security, theoretical issues in artificial intelligence, machine learning, pattern recognition, algorithmic game theory, bioinformatics and computational biology, quantum computing, probabilistic methods, & algebraic and categorical methods.
Authors: Maratea, Marco | Serina, Ivan | Torroni, Paolo
Article Type: Other
DOI: 10.3233/FI-2019-1807
Citation: Fundamenta Informaticae, vol. 167, no. 1-2, pp. v-vii, 2019
Authors: Alviano, Mario
Article Type: Research Article
Abstract: The fundamental mechanism that humans use in argumentation can be formalized in abstract argumentation frameworks. Many semantics are associated with abstract argumentation frameworks, each one consisting of a set of extensions, that is, a set of sets of arguments. Some of these semantics are based on preference relations that essentially impose to maximize or minimize some property. This paper presents the argumentation reasoner PYGLAF , which provides a uniform view of many semantics for abstract argumentation frameworks in terms of circumscription. Specifically, several computational problems of abstract argumentation frameworks are reduced to circumscription by means of linear encodings, and a …few others are solved by means of a sequence of calls to an oracle for circumscription. Finally, grounded extensions are obtained in polynomial time by unit propagation, and acceptance problems are addressed by first checking cardinality optimal models of circumscribed theories, so that the naive extension enumeration is possibly avoided. Show more
Keywords: abstract argumentation frameworks, propositional circumscription, minimal model enumeration, incremental solving
DOI: 10.3233/FI-2019-1808
Citation: Fundamenta Informaticae, vol. 167, no. 1-2, pp. 1-30, 2019
Authors: Alviano, Mario | Dodaro, Carmine
Article Type: Research Article
Abstract: Modern, efficient Answer Set Programming solvers implement answer set search via non-chronological backtracking algorithms. The extension of these algorithms to answer set enumeration is nontrivial. In fact, adding blocking constraints to discard already computed answer sets is inadequate because the introduced constraints may not fit in memory or deteriorate the efficiency of the solver. On the other hand, the algorithm implemented by CLASP , which can run in polynomial space, requires to modify the answer set search procedure. The algorithm is revised in this paper so as to make it almost independent from the underlying answer set search procedure, provided …that the procedure accepts as input a logic program and a list of assumption literals, and returns an answer set (and associated branching literals). In fact, thanks to an alternative view in terms of transition systems, the revised algorithm is suitable to easily accommodate the enumerate of models of other Boolean languages, among them classical models of propositional theories. On a pragmatic level, the paper presents two implementations of the enumeration algorithm, in WASP for answer set enumeration, and in GLUCOSE for classical models enumeration. The implemented systems are compared empirically to the state of the art solver CLASP . Show more
Keywords: Answer Set Programming, Enumeration, Assumption Literals
DOI: 10.3233/FI-2019-1809
Citation: Fundamenta Informaticae, vol. 167, no. 1-2, pp. 31-58, 2019
Authors: Charwat, Günther | Woltran, Stefan
Article Type: Research Article
Abstract: In recent years various approaches for quantified Boolean formula (QBF) solving have been developed, including methods based on expansion, skolemization and search. Here, we present a novel expansion-based solving technique that is motivated by concepts from the area of parameterized complexity. Our approach relies on dynamic programming over the tree decomposition of QBFs in prenex conjunctive normal form (PCNF). Hereby, binary decision diagrams (BDDs) are used for compactly storing partial solutions. Towards efficiency in practice, we integrate dependency schemes and develop dedicated heuristic strategies. Our experimental evaluation reveals that our implementation is competitive to state-of-the-art solvers on instances with …one quantifier alternation. Furthermore, it performs particularly well on instances up to a treewidth of approximately 80, even for more quantifier alternations. Results indicate that our approach is orthogonal to existing techniques, with a large number of uniquely solved instances. Show more
Keywords: QBF, expansion, dynamic programming, QSAT, treewidth
DOI: 10.3233/FI-2019-1810
Citation: Fundamenta Informaticae, vol. 167, no. 1-2, pp. 59-92, 2019
Authors: González, Miguel A. | Oddi, Angelo | Rasconi, Riccardo
Article Type: Research Article
Abstract: One of the most recent and interesting trends in intelligent scheduling is trying to reduce the energy consumption in order to obtain lower production costs and smaller carbon footprint. In this work we consider the energy-aware job shop scheduling problem, where we have to minimize at the same time an efficiency-based objective, as is the total weighted tardiness, and also the overall energy consumption. We experimentally show that we can reduce the energy consumption of a given schedule by delaying some operations, and to this end we design a heuristic procedure to improve a given schedule. As the problem is …computationally complex, we design three approaches to solve it: a Pareto-based multiobjective evolutionary algorithm, which is hybridized with a multiobjective local search method and a linear programming step, a decomposition-based multiobjective evolutionary algorithm hybridized with a single-objective local search method, and finally a constraint programming approach. We perform an extensive experimental study to analyze our algorithms and to compare them with the state of the art. Show more
Keywords: Multiobjective optimization, job shop, energy, metaheuristics
DOI: 10.3233/FI-2019-1811
Citation: Fundamenta Informaticae, vol. 167, no. 1-2, pp. 93-132, 2019
Authors: Santucci, Valentino | Baioletti, Marco | Milani, Alfredo
Article Type: Research Article
Abstract: Particle Swarm Optimization (PSO), though originally introduced for continuous search spaces, has been increasingly applied to combinatorial optimization problems. In this paper, we focus on the PSO applications to permutation-based problems. As far as we know, the most popular and general PSO schemes for permutation solutions are those based on random key techniques. After highlighting the main criticalities of the random key approach, we introduce a discrete PSO variant for permutation-based optimization problems. By simulating search moves through a vector space, the proposed algorithm, Algebraic PSO (APSO), allows the original PSO design to be applied to the permutation search space. …APSO directly represents both particle positions and velocities as permutations. The APSO search scheme is based on a general algebraic framework for combinatorial optimization based on strong mathematical foundations. However, in order to make this new scheme viable, some challenges have to be overcome: the choice of the order of the velocity terms, and the rationale behind the PSO inertial move. Design solutions have been proposed for both the issues. Furthermore, an alternative geometric interpretation of classical PSO dynamics allows to introduce a major APSO variant based on a novel concept of convex combination between permutation objects. In total, four APSO schemes have been introduced. Experiments have been held to compare the performances of the APSO schemes with respect to the random key based PSO schemes in literature. Widely adopted benchmark instances of four popular permutation problems have been considered. The experimental results clearly show that, with high statistical evidence, APSO outperforms its competitors and it reaches results comparable with state-of-the-art on most of the instances considered. Show more
Keywords: Algebraic Particle Swarm Optimization, Permutation Problems, Permutation Search Space
DOI: 10.3233/FI-2019-1812
Citation: Fundamenta Informaticae, vol. 167, no. 1-2, pp. 133-158, 2019
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
[email protected]
For editorial issues, like the status of your submitted paper or proposals, write to [email protected]
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
[email protected]
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office [email protected]
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
[email protected]
For editorial issues, like the status of your submitted paper or proposals, write to [email protected]
如果您在出版方面需要帮助或有任何建, 件至: [email protected]