We introduce combinatorial principles that characterize strong compactness and supercompactness for inaccessible cardinals but also make sense for successor cardinals. Their consistency is established from what is supposedly optimal. Utilizing the failure of a weak version of a square, we show that the best currently known lower bounds for the consistency strength of these principles can be applied.

Merging logic and mathematics in deductive inference-an innovative, cutting-edge approach. Optimization methods for logical inference? Absolutely, say Vijay Chandru and John Hooker, two major contributors to this rapidly expanding field. And even though "solving logical inference problems with optimization methods may seem a bit like eating sauerkraut with chopsticks... it is the mathematical structure of a problem that determines whether an optimization model can help solve it, not the context in which the problem occurs." Presenting powerful, proven (...) optimization techniques for logic inference problems, Chandru and Hooker show how optimization models can be used not only to solve problems in artificial intelligence and mathematical programming, but also have tremendous application in complex systems in general. They survey most of the recent research from the past decade in logic/optimization interfaces, incorporate some of their own results, and emphasize the types of logic most receptive to optimization methods-propositional logic, first order predicate logic, probabilistic and related logics, logics that combine evidence such as Dempster-Shafer theory, rule systems with confidence factors, and constraint logic programming systems. Requiring no background in logic and clearly explaining all topics from the ground up, Optimization Methods for Logical Inference is an invaluable guide for scientists and students in diverse fields, including operations research, computer science, artificial intelligence, decision support systems, and engineering. (shrink)

Mental representations have continuous as well as discrete, combinatorial properties. For example, while predominantly discrete, phonological representations also vary continuously; this is reflected by gradient effects in instrumental studies of speech production. Can an integrated theoretical framework address both aspects of structure? The framework we introduce here, Gradient Symbol Processing, characterizes the emergence of grammatical macrostructure from the Parallel Distributed Processing microstructure (McClelland, Rumelhart, & The PDP Research Group, 1986) of language processing. The mental representations that emerge, Distributed Symbol (...) Systems, have both combinatorial and gradient structure. They are processed through Subsymbolic Optimization–Quantization, in which an optimization process favoring representations that satisfy well-formedness constraints operates in parallel with a distributed quantization process favoring discrete symbolic structures. We apply a particular instantiation of this framework, λ-Diffusion Theory, to phonological production. Simulations of the resulting model suggest that Gradient Symbol Processing offers a way to unify accounts of grammatical competence with both discrete and continuous patterns in language performance. (shrink)

The regulation of glucose dehydrogenase (GLD) in Drosophila illustrates the combinatorial aspects of gene regulation in development. Furthermore, the findings serve to point up a general question about cukaryotic structural gene control: is regulation of expression always optimal?

Combinatorial network optimization appears to fit well as a model of brain structure: connections in the brain are a critically constrained resource, hence their deployment in a wide range of cases is finely optimized to “‘save wire". This review focuses on minimization of large-scale costs, such as total volume for mammal dendrite and axon arbors and total wirelength for positioning of connected neural components such as roundworm ganglia (and also mammal cortex areas). Phenomena of good optimization raise (...) questions about mechanisms for their achievement: the examples of optimized neuroanatomy here turn out to include candidates for some of the most complex biological structures known to be derivable purely from simple physical energy minimization processes. Part of the functional role of such fine-tuned wiring optimization may be as a compact strategy for generating self-organizing complex neuroanatomical.. (shrink)

The International Workshop on Combinatorial Algorithms was established in 1989 as the Australasian Workshop on Combinatorial Algorithms. As a consequence of the workshop's success in attracting mathematicians and computer scientists from around the world, it was decided at the 2006 meeting to go global, to change the workshop's name, and to hold it in appropriate venues around the world. The workshop supports basic research on the interface between mathematics and computing, specifically * Algorithms & Data Structures * Complexity (...) Theory * Algorithms on Graphs & Strings * Combinatorial Optimization * Cryptography & Information Security * Computational Biology * Communications Networks and many other related areas. This is Volume 1 in the series of IWOCA proceedings. See http: //www.iwoca.org/. (shrink)

This paper addresses the job shop scheduling problem including time lag constraints. This is an extension of the job shop scheduling problem with many applications in real production environments, where extra delays can be introduced between successive operations of the same job. It belongs to a category of problems known as NP-hard problem due to large solution space. Biogeography-based optimization is an evolutionary algorithm which is inspired by the migration of species between habitats, recently proposed by Simon in 2008 (...) to optimize hard combinatorial optimization problems. We propose a hybrid biogeography-based optimization algorithm for solving the job shop scheduling problem with additional time lag constraints with minimization of total completion time. In the proposed HBBO, the effective greedy constructive heuristic is adapted to generate the initial population of habitat. Moreover, a local search metaheuristic is investigated in the mutation step in order to ameliorate the solution quality and enhance the diversity of the population. To assess the performance of HBBO, a series of experiments on well-known benchmark instances for job shop scheduling problem with time lag constraints is performed. (shrink)

The travelling salesman problem is one of the most popular problems in combinatorial optimization. It has been frequently used as a benchmark of the performance of evolutionary algorithms. For this reason, nowadays practitioners request new and more difficult instances of this problem. This leads to investigate how to evaluate the intrinsic difficulty of the instances and how to separate ease and difficult instances. By developing methodologies for separating easy- from difficult-to-solve instances, researchers can fairly test the performance of (...) their combinatorial optimizers. In this work, a methodology for evaluating the difficulty of instances of the travelling salesman problem near the optimal solution is proposed. The question is if the fitness landscape near the optimal solution encodes enough information to separate instances in function of their intrinsic difficulty. This methodology is based on the use of a random walk to explore the closeness of the optimal solution. The optimal solution is modified by altering one connection between two cities at each step, at the same time that the fitness of the altered solution is evaluated. This permits evaluating the slope of the fitness landscape. Later, and using the previous information, the difficulty of the instance is evaluated with random forests and artificial neural networks. In this work, this methodology is confronted with a wide set of instances. As a consequence, a methodology to separate the instances of the travelling salesman problem by their degree of difficulty is proposed and evaluated. (shrink)

Due to the difficulty in solving combinatorial optimization problems, it is necessary to improve the performance of the algorithms by improving techniques to deal with complex optimizations. This research addresses the metaheuristics of marriage in honey-bees optimization based on the behavior of bees. The current study proposes a technique for solving combinatorial optimization problems within proper computation times. The purpose of this study focuses on the travelling salesperson problem and the application of chaotic methods in (...) important sections of the MBO metaheuristic. Three experiments were conducted to measure the efficiency and quality of the solutions: MBO with chaos to generate initial solutions ; MBO with chaos in the workers ; and MBO with chaos to generate initial solutions and the workers. The application of chaotic functions in MBO was significantly better at solving the travelling salesperson problem. (shrink)

A large number of modern communication technologies and sensing technologies are incorporated into the smart grid, which makes its structure unique. The centralized optimized dispatch method of traditional power grids is difficult to achieve effective dispatch of smart grids. Based on the analysis of power generation plan and maintenance plan optimization model, this paper establishes a smart grid power generation and maintenance collaborative optimization model with distributed renewable energy. The objective function of this collaborative optimization problem is (...) the operating cost of conventional units, the cost of wind power generation, and the cost of overhauling units; the constraints considered mainly include system constraints and overhaul constraints. The solution method of combinatorial optimization is analyzed, and the genetic optimization algorithm adopted in this paper is selected and discussed. According to the characteristics of the system, various loads are modeled, and power supply constraints are considered. By establishing an effective objective function, the adjustable load scheduling problem is transformed into a solvable optimal control problem. Taking into account the uncertain factors in the system, the advantage of the real-time control system is that it can realize the dynamic update scheduling of the load, so it is more in line with the requirements of the actual system. The real-time algorithm proposed in the paper is based on a distributed control strategy, which can not only realize dynamic compensation for random fluctuations in renewable energy power generation but also satisfy the load curve optimization under the premise of making full use of power supply resources. In addition, simulation experiments compare the load dispatching capabilities of the proposed algorithm with the existing algorithms, thereby verifying the performance of the proposed method. (shrink)

In the study of automatic summarization, the main research topic was `important sentence extraction' but nowadays `sentence compression' is a hot research topic. Conventional sentence compression methods usually transform a given sentence into a parse tree or a dependency tree, and modify them to get a shorter sentence. However, this method is sometimes too rigid. In this paper, we regard sentence compression as an combinatorial optimization problem that extracts an optimal subsequence of words. Hori et al. also proposed (...) a similar method, but they used only a small number of features and their weights were tuned by hand. We introduce a large number of features such as part-of-speech bigrams and word position in the sentence. Furthermore, we train the system by discriminative learning. According to our experiments, our method obtained better score than other methods with statistical significance. (shrink)

With the advent of the cloud computing model allowing a shared access to massive computing facilities, a surging demand emerges for the protection of the intellectual property tied to the programs executed on these uncontrolled systems. If novel paradigm as confidential computing aims at protecting the data manipulated during the execution, obfuscating techniques (in particular at the source code level) remain a popular solution to conceal the purpose of a program or its logic without altering its functionality, thus preventing reverse-engineering (...) on the program even with the help of computing resources. The many advantages of code obfuscation, together with its low cost, makes it a popular technique. This paper proposes a novel methodology for source code obfuscation that can be used together with other traditional obfuscation techniques, making the code more robust against reverse engineering attacks. Three program complexity metrics are used to define three different single-objective combinatorial optimization versions of the problem, which are solved and analysed. Additionally, three multi-objective problems are defined, those considering each of the selected metrics together with the program execution time, in order to avoid strong obfuscations penalizing the performance. The goal of the defined problems is to find sequences of LLVM optimizations that lead to highly obfuscated versions of the original code. These transformations are applied to the back-end pseudo-assembly code (i.e., LLVM Intermediate Representation), thus avoiding any further optimizations by the compiler. Classical genetic algorithms (GAs) are used to solve the studied problems, namely a basic cellular GA for the single-objective problems and the popular NSGA-II for the multi-objective ones. The promising results show the potential of the proposed technique. (shrink)

Formalising deontic concepts, such as obligation, prohibition and permission, is normally carried out in a modal logic with a possible world semantics, in which some worlds are better than others. The main focus in these logics is on inferring logical consequences, for example inferring that the obligation O q is a logical consequence of the obligations O p and O. In this paper we propose a non-modal approach in which obligations are preferred ways of satisfying goals expressed in first-order logic. (...) To say that p is obligatory, but may be violated, resulting in a less than ideal situation s, means that the task is to satisfy the goal p ∨ s, and that models in which p is true are preferred to models in which s is true. Whereas, in modal logic, the preference relation between possible worlds is part of the semantics of the logic, in this non-modal approach, the preference relation between first-order models is external to the logic. Although our main focus is on satisfying goals, we also formulate a notion of logical consequence, which is comparable to the notion of logical consequence in modal deontic logic. In this formalisation, an obligation O p is a logical consequence of goals G, when p is true in all best models of G. We show how this non-modal approach to the treatment of deontic concepts deals with problems of contrary-to-duty obligations and normative conflicts, and argue that the approach is useful for many other applications, including abductive explanations, defeasible reasoning, combinatorial optimisation, and reactive systems of the production system variety. (shrink)

We consider a deterministic rewrite system for combinatory logic over combinators , and . Terms will be represented by graphs so that reduction of a duplicator will cause the duplicated expression to be "shared" rather than copied. To each normalizing term we assign a weighting which is the number of reduction steps necessary to reduce the expression to normal form. A lambda-expression may be represented by several distinct expressions in combinatory logic, and two combinatory logic expressions are considered equivalent if (...) they represent the same lambda-expression (up to --equivalence). The problem of minimizing the number of reduction steps over equivalent combinator expressions (i.e., the problem of finding the "fastest running" combinator representation for a specific lambda-expression) is proved to be NP-complete by reduction from the "Hitting Set" problem. (shrink)

We analyze the Gale-Shapley matching problem within the context of Rawlsian justice. Defining a fair matching algorithm by a set of 4 axioms (Gender Indifference, Peer Indifference, Maximin Optimality, and Stability), we show that not all preference profiles admit a fair matching algorithm, the reason being that even this set of minimal axioms is too strong in a sense. Because of conflict between Stability and Maximin Optimality, even the algorithm which generates the mutual agreement match, paradoxically, has no chance to (...) be fair.We then relax the definition of fairness (by giving preference to Stability over Maximin Optimality) and again find that some preference profiles admit a fair matching algorithm, while others still do not, but the mutual agreement algorithm now is fair under this definition.The paper then develops a test, which determines, for a given preference profile, whether a fair algorithm exists or not. (shrink)

The problem of combinatorial optimization is considered in relation to the choice of the location of the location of power supplies when solving the problem of the development of urban distribution networks of power supply. Two methods have been developed for placing power supplies and assigning consumers to them to solve this problem. The first developed method consists in placing power supplies of the same standard sizes, and the second - of different standard sizes. The fundamental difference between (...) the created methods and the existing ones is that the proposed methods take into account all the material of the problem and have specialized methods for coding possible solutions, modified operators of crossing and selection. The proposed methods effectively solve the problem of low inheritance, topological unfeasibility of the found solutions, as a result of which the execution time is significantly reduced and the accuracy of calculations is increased. In the developed methods, the lack of taking into account the restrictions on the placement of new power supplies is realized, which made it possible to solve the problem of applying the methods for a narrow range of problems. A comparative analysis of the results obtained by placing power supplies of the same standard sizes and known methods was carried out, and it was found that the developed method works faster than the known methods. It is shown that the proposed approach ensures stable convergence of the search process by an acceptable number of steps without artificial limitation of the search space and the use of additional expert information on the feasibility of possible solutions. The results obtained allow us to propose effective methods to improve the quality of decisions made on the choice of the location of power supply facilities in the design of urban electrical. (shrink)

The Next Release Problem (NRP) is a combinatorial optimization problem that aims to find a subset of software requirements to be delivered in the next software release, which maximize the satisfaction of a list of clients and minimize the effort required by developers to implement them. Previous studies have applied various metaheuristics, mostly genetic algorithms. Estimation of Distribution Algorithms (EDA), based on probabilistic modelling, have been proved to obtain good results in problems where genetic algorithms struggle. In this (...) paper we propose to adapt three EDAs to tackle the multi-objective NRP in a fast and effective way. Results show that EDAs can be applicable to solve the NRP with rather good quality of solutions. Furthermore, we prove that their execution time can be significantly reduced using a per-iteration solution subset selection method while maintaining the overall quality of the solutions obtained, and they perform the best when limiting the search time as in an interactive tool that requires fast responsiveness. The experimental framework, code and datasets have been made public in a code repository. (shrink)

Learning equivalence classes of acyclic models with latent and selection variables from multiple datasets with overlapping variables is discussed. The problem of inferring the presence of latent variables, their relation to the observables, and the relation among themselves, is considered. A different approach for identifying causal structures, one that results in much simpler equivalence classes, is provided. It is found that the computational cost is much higher than the procedure implemented, but if datasets are individually of modest dimensionality, it might (...) be doable in practice. From the point of view of search algorithms for optimizing structure, much of the machinery of combinatorial optimization could optimize the penalized composite likelihood score by enforcing constraints such that the independence models over different subsets of variables agree on the overlapping sets. (shrink)

The bin-packing problem (BPP) is an age-old NP-hard combinatorial optimization problem, which is defined as the placement of a set of different-sized items into identical bins such that the number of containers used is optimally minimized. Besides, different variations of the problem do exist in practice depending on the bins dimension, placement constraints, and priority. More so, there are several important real-world applications of the BPP, especially in cutting industries, transportation, warehousing, and supply chain management. Due to the (...) practical relevance of this problem, researchers are consistently investigating new and improved techniques to solve the problem optimally. Nature-inspired metaheuristics are powerful algorithms that have proven their incredible capability of solving challenging and complex optimization problems, including several variants of BPPs. However, no comprehensive literature review exists on the applications of the metaheuristic approaches to solve the BPPs. Therefore, to fill this gap, this article presents a survey of the recent advances achieved for the one-dimensional BPP, with specific emphasis on population-based metaheuristic algorithms. We believe that this article can serve as a reference guide for researchers to explore and develop more robust state-of-the-art metaheuristics algorithms for solving the emerging variants of the bin-parking problems. (shrink)

The multilinear extension of a cooperative game was introduced by Owen in 1972. In this contribution we study the Lovász extension for cooperative games by using the marginal worth vectors and the dividends. First, we prove a formula for the marginal worth vectors with respect to compatible orderings. Next, we consider the direct market generated by a game. This model of utility function, proposed by Shapley and Shubik in 1969, is the concave biconjugate extension of the game. Then we obtain (...) the following characterization: The utility function of a market game is the Lovász extension of the game if and only if the market game is supermodular. Finally, we present some preliminary problems about the relationship between cooperative games and combinatorial optimization. (shrink)

This article presents a Hybrid Artificial Bee Colony for uncapacitated examination timetabling. The ABC algorithm is a recent metaheuristic population-based algorithm that belongs to the Swarm Intelligence technique. Examination timetabling is a hard combinatorial optimization problem of assigning examinations to timeslots based on the given hard and soft constraints. The proposed hybridization comes in two phases: the first phase hybridized a simple local search technique as a local refinement process within the employed bee operator of the original ABC, (...) while the second phase involves the replacement of the scout bee operator with the random consideration concept of harmony search algorithm. The former is to empower the exploitation capability of ABC, whereas the latter is used to control the diversity of the solution search space. The HABC is evaluated using a benchmark dataset defined by Carter, including 12 problem instances. The results show that the HABC is better than exiting ABC techniques and competes well with other techniques from the literature. (shrink)

The notion of efficient proof-checking has always been central to complexity theory, and it gave rise to the definition of the class NP. In the last 15 years there has been a number of exciting, unexpected and deep developments in complexity theory that exploited the notion of randomized and interactive proof-checking. Results developed along this line of research have diverse and powerful applications in complexity theory, cryptography, and the theory of approximation algorithms for combinatorial optimization problems. In this (...) paper we survey the main lines of developments in interactive and probabilistic proof-checking, with an emphasis on open questions. (shrink)

The traveling salesman problem is one of the most important issues in combinatorial optimization problems that are used in many engineering sciences and has attracted the attention of many scientists and researchers. In this issue, a salesman starts to move from a desired node called warehouse and returns to the starting place after meeting n customers provided that each customer is only met once. The aim of this issue is to determine a cycle with a minimum cost for (...) this salesman. One of the major weaknesses of the PSO algorithm in the classical version is that it gets stuck in local optimizations. Therefore, in the proposed algorithm, called MPSO, the best solution in the current iteration is also used in the movement step. In addition, a variety of local search algorithms are provided that are used when better answers are generated than before. Also, a new method for moving the particle towards the best particle is presented, which, in addition to probably increasing the quality of the new answer, prevents the premature convergence of the algorithm due to consideration of the concept of random. The results evaluated with the results of several metaheuristic algorithms in the literature show the efficiency of the MPSO algorithm because it has been able to achieve excellent solutions in most of these instances. (shrink)

Local deterministic string-to-string transductions arise in natural language processing (NLP) tasks such as letter-to-sound translation or pronunciation modeling. This class of transductions is a simple generalization of morphisms of free monoids; learning local transductions is essentially the same as inference of certain monoid morphisms. However, learning even a highly restricted class of morphisms, the so-called fine morphisms, leads to intractable problems: deciding whether a hypothesized fine morphism is consistent with observations is an NP-complete problem; and maximizing classification accuracy of the (...) even smaller class of alphabetic substitution morphisms is APX-hard. These theoretical results provide some justification for using the kinds of heuristics that are commonly used for this learning task. (shrink)

A fixed-parameter is an algorithm that provides an optimal solution to a combinatorial problem. This research-level text is an application-oriented introduction to the growing and highly topical area of the development and analysis of efficient fixed-parameter algorithms for hard problems. The book is divided into three parts: a broad introduction that provides the general philosophy and motivation; followed by coverage of algorithmic methods developed over the years in fixed-parameter algorithmics forming the core of the book; and a discussion of (...) the essential from parameterized hardness theory with a focus on W [1]-hardness, which parallels NP-hardness, then stating some relations to polynomial-time approximation algorithms, and finishing up with a list of selected case studies to show the wide range of applicability of the presented methodology. Aimed at graduate and research mathematicians, programmers, algorithm designers and computer scientists, the book introduces the basic techniques and results and provides a fresh view on this highly innovative field of algorithmic research. (shrink)

Research in anthropology has shown that kin terminologies have a complex combinatorial structure and vary systematically across cultures. This article argues that universals and variation in kin terminology result from the interaction of (1) an innate conceptual structure of kinship, homologous with conceptual structure in other domains, and (2) principles of optimal, “grammatical” communication active in language in general. Kin terms from two languages, English and Seneca, show how terminologies that look very different on the surface may result from (...) variation in the rankings of a universal set of constraints. Constraints on kin terms form a system: some are concerned with absolute features of kin (sex), others with the position (distance and direction) of kin in “kinship space,” others with groups and group boundaries (matrilines, patrilines, generations, etc.). Also, kin terms sometimes extend indefinitely via recursion, and recursion in kin terminology has parallels with recursion in other areas of language. Thus the study of kinship sheds light on two areas of cognition, and their phylogeny. The conceptual structure of kinship seems to borrow its organization from the conceptual structure of space, while being specialized for representing genealogy. And the grammar of kinship looks like the product of an evolved grammar faculty, opportunistically active across traditional domains of semantics, syntax, and phonology. Grammar is best understood as an offshoot of a uniquely human capacity for playing coordination games. (shrink)

This paper discusses DNA-based stochastic optimizations under the constraint that the search starts from a given point in a search space. Generally speaking, a stochastic optimization method explores a search space and finds out the optimum or a sub-optimum after many cycles of trials and errors. This search process could be implemented efficiently by ``molecular computing'', which processes DNA molecules by the techniques of molecular biology to generate and evaluate a vast number of solution candidates at a time. We (...) assume the exploration starting from a single point, and propose a method to embody DNA-based optimization under this constraint, because this method has a promising application in the research field of protein engineering. In this application, a string of nucleotide bases encodes a protein possessing a specific activity, which could be given as a value of an objective function. Thus, a problem of obtaining a protein with the optimum or a sub-optimum about the desired activity corresponds to a combinatorial problem of obtaining a base sequence giving the optimum or a sub-optimum in the sequence space. Biologists usually modify a base sequence corresponding to a naturally occurring protein into another sequence giving a desired activity. In other words, they explore the space in the proximity of a natural protein as a start point. We first examined if the optimization methods that involve a single start point, such as simulated annealing, Gibbs sampler, and MH algorithms, can be implemented by DNA-based operations. Then, we proposed an application of genetic algorithm, and examined the performance of this application on a model fitness landscape by computer experiments. These experiments gave helpful guidelines in the embodiments of DNA-based stochastic optimization, including a better design of crossover operator. (shrink)

Solution searching that accompanies combinatorial explosion is one of the most important issues in the age of artificial intelligence. Natural intelligence, which exploits natural processes for intelligent functions, is expected to help resolve or alleviate the difficulties of conventional computing paradigms and technologies. In fact, we have shown that a single-celled organism such as an amoeba can solve constraint satisfaction problems and related optimization problems as well as demonstrate experimental systems based on non-organic systems such as optical energy (...) transfer involving near-field interactions. However, the fundamental mechanisms and limitations behind solution searching based on natural processes have not yet been understood. Herein, we present a theoretical background of solution searching based on optical excitation transfer from a category-theoretic standpoint. One important indication inspired by the category theory is that the satisfaction of short exact sequences is critical for an adequate computational operation that determines the flow of time for the system and is termed as “short-exact-sequence-based time.” In addition, the octahedral and braid structures known in triangulated categories provide a clear understanding of the underlying mechanisms, including a quantitative indication of the difficulties of obtaining solutions based on homology dimension. This study contributes to providing a fundamental background of natural intelligence. (shrink)

The third volume of “Advancing Uncertain Combinatorics through Graphization, Hyperization, and Uncertainization: Fuzzy, Neutrosophic, Soft, Rough, and Beyond” presents an in-depth exploration of the cutting-edge developments in uncertain combinatorics and set theory. This comprehensive collection highlights innovative methodologies such as graphization, hyperization, and uncertainization, which enhance combinatorics by incorporating foundational concepts from fuzzy, neutrosophic, soft, and rough set theories. These advancements open new mathematical horizons, offering novel approaches to managing uncertainty within complex systems. Combinatorics, a discipline focused on counting, arrangement, (...) and structure, often faces challenges when uncertainty is present. Set theory, which underpins combinatorial problems, has evolved to tackle these challenges. The introduction of fuzzy and neutrosophic sets has expanded the toolkit for modeling uncertainty by incorporating elements of truth, indeterminacy, and falsehood into decision-making processes. These innovations seamlessly intersect with graph theory, providing new ways to represent uncertain structures through "graphized" forms such as hypergraphs and superhypergraphs. This volume also introduces advanced concepts like Neutrosophic Oversets, Undersets, and Offsets, which push the boundaries of classical graph theory and offer deeper insights into the mathematical and practical challenges posed by real-world systems. By blending combinatorics, set theory, and graph theory, the authors have created a robust framework for addressing uncertainty in both mathematical systems and their real-world applications. This foundation sets the stage for future breakthroughs in combinatorics, set theory, and related fields. Each chapter in this volume contributes both theoretical foundations and practical applications, demonstrating the power of integrating graph theory, set theory, and uncertainty models. The new ideas, algorithms, and mathematical tools presented here will drive the future of combinatorial research and its applications in uncertain environments. In the first chapter, “Introduction to Upside-Down Logic: Its Deep Relation to Neutrosophic Logic and Applications”, the authors present Upside-Down Logic, a novel logical framework that systematically transforms truths into falsehoods and vice versa, based on contextual shifts. Introduced by F. Smarandache, this paper provides a mathematical definition of Upside-Down Logic, including applications related to the Japanese language. The chapter also introduces Contextual Upside-Down Logic, an extension that adjusts logical connectives alongside flipped truth values, as well as Indeterm-Upside-Down Logic and Certain Upside-Down Logic to address indeterminacy. A simple algorithm is also proposed to demonstrate the computational aspects of this logic. In the second chapter, “Local-Neutrosophic Logic and Local-Neutrosophic Sets: Incorporating Locality with Applications”, the authors introduce Local-Neutrosophic Logic and Local-Neutrosophic Sets, which integrate the concept of locality into Neutrosophic Logic. By defining locality as the influence of immediate surroundings on an object or system, this chapter explores how it affects indeterminacy in real-world problems. The paper also examines potential applications and provides mathematical definitions for these new concepts. The third chapter, “A Review of Fuzzy and Neutrosophic Offsets: Connections to Some Set Concepts and Normalization Function”, extends the concept of offsets in uncertain set-theoretic frameworks, such as Fuzzy Sets, Neutrosophic Sets, and Plithogenic Sets. This chapter introduces several advanced types of offsets, including Nonstationary Fuzzy Offset, Multi-valued Plithogenic Offset, and Subset-valued Neutrosophic Offset, offering deeper insights into handling uncertainty in mathematical models. In the fourth chapter, “Review of Plithogenic Directed, Mixed, Bidirected, and Pangene OffGraph”, the authors build upon Plithogenic Graphs to propose extensions such as Plithogenic Directed OffGraph, Plithogenic BiDirected OffGraph, and Plithogenic Mixed OffGraph. These new concepts, including the Plithogenic Pangene OffGraph, are explored in detail, with a focus on their mathematical properties and potential applications in uncertain graph theory. The fifth chapter, “Short Note on Neutrosophic Closure Matroids”, explores the extension of matroid concepts into Neutrosophic and Turiyam Neutrosophic set theories, introducing Neutrosophic closure matroids. This concept integrates uncertainty, indeterminacy, and liberal states into matroid theory, enhancing its applicability in optimization and combinatorial problems. In the sixth chapter, “Some Graph Parameters for Superhypertree-width and Neutrosophic Tree-width”, the authors discuss graph parameters such as Superhypertree-width and Neutrosophic tree-width. These parameters play a crucial role in the study of graph characteristics, particularly in algorithms and real-world applications. The chapter explores the generalization of hypergraphs to SuperHyperGraphs and examines how these concepts extend tree-width parameters within the context of Neutrosophic logic. (shrink)

We formulate the problem of permuting a matrix to block angular form as the combinatorial minimization of an objective function. We motivate the use of simulated annealing (SA) as an optimization tool. We then introduce a heuristic temperature dependent penalty function in the simulated annealing cost function, to be used instead of the real objective function being minimized. Finally we show that this temperature dependent penalty function version of simulated annealing consistently outperforms the standard simulated annealing approach, producing, (...) with smaller running times, better solutions. We believe that the use of a temperature dependent penalty function may be useful in developing SA algorithms for other combinatorial problems. -/- . (shrink)

We will apply the methods developed in the field of ‘proof mining’ to the Bolzano-Weierstraß theorem BW and calibrate the computational contribution of using this theorem in proofs of combinatorial statements. We provide an explicit solution of the Gödel functional interpretation as well as the monotone functional interpretation of BW for the product space Πi ∈ℕ[–ki, ki] . This results in optimal program and bound extraction theorems for proofs based on fixed instances of BW, i.e. for BW applied to (...) fixed sequences in Πi ∈ℕ[–ki, ki]. (shrink)

Beyond the predominant paradigm of an essentially rational human cognition, based on the classical binary logic, we want to propose some reflections that are organized around the intuition that the representations we have of the world are weighted with appreciations, for example affective ones. resulting from our integration into a social environment. We see these connotations as essentially ternary in nature, depending on the concepts underlying neutrosophy: either positive, negative or neutral. This form of representation would then influence the very (...) nature of the cognitive process, which in complex real-world situations, has to deal with problems of a combinatorial nature leading to a number of cases too large for our abilities. Forced to proceed by shortcuts on the basis of heuristics, cognition would use these assessments of the representations it manipulates to decide whether partial solutions are attractive for solving the problem or on the contrary are judged negative and are then quickly rejected. There is still the case of a neutral weighting that allows processing to continue. Thus a neutrosophical conception of our representations of the world explains how our cognition functions in its treatment of combinatorial problems in the form of producing processing accelerating heuristics, both in terms of partial solutions selection and processing optimization. (shrink)

In this paper I will present an analysis of the impact that the notion of “bounded rationality”, introduced by Herbert Simon in his book “Administrative Behavior”, produced in the field of Artificial Intelligence (AI). In particular, by focusing on the field of Automated Decision Making (ADM), I will show how the introduction of the cognitive dimension into the study of choice of a rational (natural) agent, indirectly determined - in the AI field - the development of a line of research (...) aiming at the realisation of artificial systems whose decisions are based on the adoption of powerful shortcut strategies (known as heuristics) based on “satisficing” - i.e. non optimal - solutions to problem solving. I will show how the “heuristic approach” to problem solving allowed, in AI, to face problems of combinatorial complexity in real-life situations and still represents an important strategy for the design and implementation of intelligent systems. (shrink)

We study human performance in two classical NP‐hard optimization problems: Set Cover and Maximum Coverage. We suggest that Set Cover and Max Coverage are related to means selection problems that arise in human problem‐solving and in pursuing multiple goals: The relationship between goals and means is expressed as a bipartite graph where edges between means and goals indicate which means can be used to achieve which goals. While these problems are believed to be computationally intractable in general, they become (...) more tractable when the structure of the network resembles a tree. Thus, our main prediction is that people should perform better with goal systems that are more tree‐like. We report three behavioral experiments which confirm this prediction. Our results suggest that combinatorial parameters that are instrumental to algorithm design can also be useful for understanding when and why people struggle to choose between multiple means to achieve multiple goals. (shrink)

The game of Go was the last great challenge for artificial intelligence in abstract board games. AlphaGo was the first system to reach supremacy, and subsequent implementations further improved the state of the art. As in chess, the fall of the human world champion did not lead to the end of the game. Now, we have renewed interest in the game due to new questions that emerged in this development. How far are we from perfect play? Can humans catch up? (...) How compressible is Go knowledge? What is the computational complexity of a perfect player? How much energy is really needed to play the game optimally? Here, we investigate these and related questions with respect to the special properties of Go (meaningful draws and extreme combinatorial complexity). Since traditional board games have an important role in human culture, our analysis is relevant in a broader context. What happens in the game world could forecast our relationship with AI entities, their explainability, and usefulness. (shrink)

Drug design methods have made significant new advances over the last ten years, mainly in the areas of molecular modelling. In more recent times important developments in theory have led to a different type of modelling becoming possible, the so‐called de novo or automated design algorithms. In this new method the programs perform much of the chemist's thinking, in finding appropriately sized chemical groups to fit into a target site. However this is a combinatoric problem which has no general analytical (...) solution; it is ripe for optimization. Other advances, such as combinatorial chemical synthesis and screening, will dramatically influence the search for new lead structures for target sites, which at present are poorly understood. Already these methods are being applied to peptide libraries. Peptides do not make good drug compounds because of their poor bioavailability; further, their flexibility reduces their affinity. In some cases peptide backbones can be removed and replaced with rigid non‐peptide scaffolds. (shrink)

The genetic code has evolved from its initial non-degenerate wobble version until reaching its present state of degeneracy. By using the stereochemical hypothesis, we revisit the problem of codon assignations to the synonymy classes of amino-acids. We obtain these classes with a simple classifier based on physico-chemical properties of nucleic bases, like hydrophobicity and molecular weight. Then we propose simple RNA ring structures that present, overlap included, one and only one codon by synonymy class as solutions of a combinatory variational (...) problem. We compare these solutions to sequences of present RNAs considered as relics, with a high interspecific invariance, like invariant parts of tRNAs and micro-RNAs. We conclude by emphasizing some optimal properties of the genetic code. (shrink)

In this article we will present the Conjoint Family Drawing, a graphic-interactive tool developed to evaluate family relationships. This tool allows an analytical and clinical evaluation of families and their relationships while facilitating the understanding of the overall family functioning through a synthetic coding system which distinguishes families from each other. First of all, a presentation of the analytical coding system is provided; such system consists of a grid, formed by two distinct levels of observation: the analysis of the product, (...) which, in turn focuses on two levels, the global-familiar one and the individual one, and the analysis of the drawing process, which is made up of the observations of family interactions at the individual and group level. Consistently with our objectives and the theoretical and methodological literature on family drawing in its various forms and ways of implementation, 10 indicators for product analysis and 9 indicators for process analysis have been identified. A sample of 117 Conjoint Family Drawings was analyzed in order to verify the coding system’s applicability and effectiveness. The sample was constituted according to a convenience criterion. Following, a computing system was developed to allow the investigation of the overall family functioning through three steps: the analysis of the frequency distribution of each indicator, in order to verify the non-determinability rates and the distribution of the different answer options; a two-step cluster analysis, to determine homogeneous groups of Conjoint Family Drawings and identify, within each cluster, the indicators and answer modalities that mostly affect the clusters’ aggregation itself; the development of a synthetic system to code the Conjoint Family Drawing, beginning with the indicators that define the typological profiles of the clusters obtained. The synthetic system was developed through a summative and logical-combinatorial method, merging the most discriminating and clinically significant coding items, that is, those that are best associable to specific ways of family functioning. Seven family types emerged from these analyses: families characterized by optimal functioning, families characterized by adequate functioning, families characterized by chaotic functioning, families characterized by fragile paternity, families characterized by separate functioning, families with multiproblematic functioning and residual families. The characteristics of these family types will be outlined in this article. (shrink)

Mobile health applications (‘health apps’) that promise the user to help her with some aspect of her health are very popular: for-profit apps such as MyFitnessPal, Fitbit, or Headspace have tens of millions of users each. For-profit health apps are designed and run as optimization systems. One would expect that these health apps aim to optimize the health of the user, but in reality they aim to optimize user engagement and, in effect, conversion. This is problematic, I argue, because (...) digital health environments that aim to optimize user engagement risk being manipulative. To develop this argument, I first provide a brief analysis of the underlying business models and the resulting designs of the digital environments provided by popular for-profit health apps. In a second step, I present a concept of manipulation that can help analyze digital environments such as health apps. In the last part of the article, I use my concept of manipulation to analyze the manipulative potential of for-profit health apps. Although for-profit health can certainly empower their users, the conditions for empowerment also largely overlap with the conditions for manipulation. As a result, we should be cautious when embracing the empowerment discourse surrounding health apps. An additional aim of this article is to contribute to the rapidly growing literature on digital choice architectures and the ethics of influencing behavior through such choice architectures. I take health apps to be a paradigmatic example of digital choice architectures that give rise to ethical questions, so my analysis of the manipulative potential of health apps can also inform the larger literature on digital choice architectures. (shrink)

CHAPTER Addenda to Pure Combinatory Logic This chapter will treat various additions to, and modifications of, the subject matter of Chapters-7....

Combinatorial behavior involves combining different elements into larger aggregates with meaning. It is generally contrasted with compositionality, which involves the combining of meaningful elements into larger constituents whose meaning is derived from its component parts. Combinatoriality is commonly considered a capacity found in primates and other animals, whereas compositionality often is considered uniquely human. Questioning the validity of this claim, this multidisciplinary special issue of the International Journal of Primatology unites papers that each study aspects of combinatoriality and compositionality (...) found in primate and bird communication systems, tool use, skills, and human language. The majority of authors conclude that compositionality is evolutionarily preceded by combinatoriality and that neither are uniquely human. This introduction briefly introduces readers to the major findings and issues raised by the contributors. -/- . (shrink)

Visual cryptography is a cryptographic technique that allows visual information to be encrypted so that the human optical system can perform the decryption without any cryptographic computation. The halftone visual cryptography scheme (HVCS) is a type of visual cryptography (VC) that encodes the secret image into halftone images to produce secure and meaningful shares. However, the HVC scheme has many unsolved problems, such as pixel expansion, low contrast, cross-interference problem, and difficulty in managing share images. This article aims to enhance (...) the visual quality and avoid the problems of cross-interference and pixel expansion of the share images. It introduces a novel optimization of color halftone visual cryptography (OCHVC) scheme by using two proposed techniques: hash codebook and construction techniques. The new techniques distribute the information pixels of a secret image into a halftone cover image randomly based on a bat optimization algorithm. The results show that these techniques have enhanced security levels and make the proposed OCHVC scheme more robust against different attacks. The OCHVC scheme achieves mean squared error (MSE) of 95.0%, peak signal-to-noise ratio (PSNR) of 28.3%, normalized cross correlation (NCC) of 99.4%, and universal quality index (UQI) of 99.3% on average for the six shares. Subsequently, the experiment results based on image quality metrics show improvement in size, visual quality, and security for retrieved secret images and meaningful share images of the OCHVC scheme. Comparing the proposed OCHVC with some related works shows that the OCHVC scheme is more effective and secure. (shrink)

Standard game theory struggles to explain cooperation and coordination in collective action problems where rational strategies often fail to yield mutually beneficial outcomes. One response to this is team reasoning, which introduces group agency. Another is Kantian optimization, which retains individual agency but assumes universalization-based optimization. Some have proposed that Kantian optimization is best understood as a subtype of team reasoning, a member of the same theoretical family. This paper disputes that. By demonstrating that Kantian-style team reasoning (...) does not necessarily lead to Kantian equilibrium, the paper concludes that Kantian universalization does not fit within the group agency framework. (shrink)