Relevant bibliographies by topics / Combinatorial set theory

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers
  6. Reports

Academic literature on the topic 'Combinatorial set theory'

Author: Grafiati
Published: 4 June 2021
Last updated: 1 August 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Combinatorial set theory.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Combinatorial set theory"

1

Todorcevic, Stevo. "Combinatorial Dichotomies in Set Theory." Bulletin of Symbolic Logic 17, no. 1 (2011): 1–72. http://dx.doi.org/10.2178/bsl/1294186662.

Full text
Abstract:
AbstractWe give an overview of a research line concentrated on finding to which extent compactness fails at the level of first uncountable cardinal and to which extent it could be recovered on some other perhaps not so large cardinal. While this is of great interest to set theorists, one of the main motivations behind this line of research is in its applicability to other areas of mathematics. We give some details about this and we expose some possible directions for further research.
APA, Harvard, Vancouver, ISO, and other styles
2

Schindler, Ralf. "Lorenz J. Halbeisen: “Combinatorial Set Theory”." Jahresbericht der Deutschen Mathematiker-Vereinigung 115, no. 2 (2013): 119–21. http://dx.doi.org/10.1365/s13291-013-0063-5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Mileti, Joseph R. "Partition Theorems and Computability Theory." Bulletin of Symbolic Logic 11, no. 3 (2005): 411–27. http://dx.doi.org/10.2178/bsl/1122038995.

Full text
Abstract:
The connections between mathematical logic and combinatorics have a rich history. This paper focuses on one aspect of this relationship: understanding the strength, measured using the tools of computability theory and reverse mathematics, of various partition theorems. To set the stage, recall two of the most fundamental combinatorial principles, König's Lemma and Ramsey's Theorem. We denote the set of natural numbers by ω and the set of finite sequences of natural numbers by ω<ω. We also identify each n ∈ ω with its set of predecessors, so n = {0, 1, 2, …, n − 1}.
APA, Harvard, Vancouver, ISO, and other styles
4

Williams, Neil H., Paul Erdos, Andras Hajnal, Attila Mate, and Richard Rado. "Combinatorial Set Theory: Partition Relations for Cardinals." Journal of Symbolic Logic 53, no. 1 (1988): 310. http://dx.doi.org/10.2307/2274453.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Hodel, R. E. "Combinatorial set theory and cardinal function inequalities." Proceedings of the American Mathematical Society 111, no. 2 (1991): 567. http://dx.doi.org/10.1090/s0002-9939-1991-1039531-7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Hajnal, A., and P. Komjáth. "Some higher-gap examples in combinatorial set theory." Annals of Pure and Applied Logic 33 (1987): 283–96. http://dx.doi.org/10.1016/0168-0072(87)90084-4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Shablya, Yuriy, Dmitry Kruchinin, and Vladimir Kruchinin. "Method for Developing Combinatorial Generation Algorithms Based on AND/OR Trees and Its Application." Mathematics 8, no. 6 (2020): 962. http://dx.doi.org/10.3390/math8060962.

Full text
Abstract:
In this paper, we study the problem of developing new combinatorial generation algorithms. The main purpose of our research is to derive and improve general methods for developing combinatorial generation algorithms. We present basic general methods for solving this task and consider one of these methods, which is based on AND/OR trees. This method is extended by using the mathematical apparatus of the theory of generating functions since it is one of the basic approaches in combinatorics (we propose to use the method of compositae for obtaining explicit expression of the coefficients of generating functions). As a result, we also apply this method and develop new ranking and unranking algorithms for the following combinatorial sets: permutations, permutations with ascents, combinations, Dyck paths with return steps, labeled Dyck paths with ascents on return steps. For each of them, we construct an AND/OR tree structure, find a bijection between the elements of the combinatorial set and the set of variants of the AND/OR tree, and develop algorithms for ranking and unranking the variants of the AND/OR tree.
APA, Harvard, Vancouver, ISO, and other styles
8

BUCCI, MICHELANGELO, SVETLANA PUZYNINA, and LUCA Q. ZAMBONI. "Central sets generated by uniformly recurrent words." Ergodic Theory and Dynamical Systems 35, no. 3 (2013): 714–36. http://dx.doi.org/10.1017/etds.2013.69.

Full text
Abstract:
AbstractA subset $A$ of $ \mathbb{N} $ is called an IP-set if $A$ contains all finite sums of distinct terms of some infinite sequence $\mathop{({x}_{n} )}\nolimits_{n\in \mathbb{N} } $ of natural numbers. Central sets, first introduced by Furstenberg using notions from topological dynamics, constitute a special class of IP-sets possessing rich combinatorial properties: each central set contains arbitrarily long arithmetic progressions and solutions to all partition regular systems of homogeneous linear equations. In this paper we investigate central sets in the framework of combinatorics on words. Using various families of uniformly recurrent words, including Sturmian words, the Thue–Morse word and fixed points of weak mixing substitutions, we generate an assortment of central sets which reflect the rich combinatorial structure of the underlying words. The results in this paper rely on interactions between different areas of mathematics, some of which have not previously been directly linked. They include the general theory of combinatorics on words, abstract numeration systems, and the beautiful theory, developed by Hindman, Strauss and others, linking IP-sets and central sets to the algebraic/topological properties of the Stone-Čech compactification of $ \mathbb{N} $.
APA, Harvard, Vancouver, ISO, and other styles
9

Chen, Herman Z. Q., and Sergey Kitaev. "On universal partial words for word-patterns and set partitions." RAIRO - Theoretical Informatics and Applications 54 (2020): 5. http://dx.doi.org/10.1051/ita/2020004.

Full text
Abstract:
Universal words are words containing exactly once each element from a given set of combinatorial structures admitting encoding by words. Universal partial words (u-p-words) contain, in addition to the letters from the alphabet in question, any number of occurrences of a special “joker” symbol. We initiate the study of u-p-words for word-patterns (essentially, surjective functions) and (2-)set partitions by proving a number of existence/non-existence results and thus extending the results in the literature on u-p-words and u-p-cycles for words and permutations. We apply methods of graph theory and combinatorics on words to obtain our results.
APA, Harvard, Vancouver, ISO, and other styles
10

Akihiro Kanamori. "Zermelo and Set Theory." Bulletin of Symbolic Logic 10, no. 4 (2004): 487–553. http://dx.doi.org/10.2178/bsl/1102083759.

Full text
Abstract:
Ernst Friedrich Ferdinand Zermelo (1871–1953) transformed the set theory of Cantor and Dedekind in the first decade of the 20th century by incorporating the Axiom of Choice and providing a simple and workable axiomatization setting out generative set-existence principles. Zermelo thereby tempered the ontological thrust of early set theory, initiated the delineation of what is to be regarded as set-theoretic, drawing out the combinatorial aspects from the logical, and established the basic conceptual framework for the development of modern set theory. Two decades later Zermelo promoted a distinctive cumulative hierarchy view of models of set theory and championed the use of infinitary logic, anticipating broad modern developments. In this paper Zermelo's published mathematical work in set theory is described and analyzed in its historical context, with the hindsight afforded by the awareness of what has endured in the subsequent development of set theory. Elaborating formulations and results are provided, and special emphasis is placed on the to and fro surrounding the Schröder-Bernstein Theorem and the correspondence and comparative approaches of Zermelo and Gödel. Much can be and has been written about philosophical and biographical issues and about the reception of the Axiom of Choice, and we will refer and defer to others, staying the course through the decidedly mathematical themes and details.
APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic "Combinatorial set theory"

1

Ahmed, Shehzad. "Progressive Ideals in Combinatorial Set Theory." Ohio University / OhioLINK, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1554379497651916.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Walker, D. J. "Combinatorial applications of the core model." Thesis, University of Oxford, 1985. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.355807.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Gutekunst, Todd M. "Subsets of finite groups exhibiting additive regularity." Access to citation, abstract and download form provided by ProQuest Information and Learning Company; downloadable PDF file, 128 p, 2008. http://proquest.umi.com/pqdweb?did=1605136271&sid=5&Fmt=2&clientId=8331&RQT=309&VName=PQD.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Choi, Sul-young. "Maximal (0,1,2,...t)-cliques of some association schemes /." The Ohio State University, 1985. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487261553059595.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Phillips, Linzy. "Erasure-correcting codes derived from Sudoku & related combinatorial structures." Thesis, University of South Wales, 2013. https://pure.southwales.ac.uk/en/studentthesis/erasurecorrecting-codes-derived-from-sudoku--related-combinatorial-structures(b359130e-bfc2-4df0-a6f5-55879212010d).html.

Full text
Abstract:
This thesis presents the results of an investigation into the use of puzzle-based combinatorial structures for erasure correction purposes. The research encompasses two main combinatorial structures: the well-known number placement puzzle Sudoku and a novel three component construction designed specifically with puzzle-based erasure correction in mind. The thesis describes the construction of outline erasure correction schemes incorporating each of the two structures. The research identifies that both of the structures contain a number of smaller sub-structures, the removal of which results in a grid with more than one potential solution - a detrimental property for erasure correction purposes. Extensive investigation into the properties of these sub-structures is carried out for each of the two outline erasure correction schemes, and results are determined that indicate that, although the schemes are theoretically feasible, the prevalence of sub-structures results in practically infeasible schemes. The thesis presents detailed classifications for the different cases of sub-structures observed in each of the outline erasure correction schemes. The anticipated similarities in the sub-structures of Sudoku and sub-structures of Latin Squares, an established area of combinatorial research, are observed and investigated, the proportion of Sudoku puzzles free of small sub-structures is calculated and a simulation comparing the recovery rates of small sub-structure free Sudoku and standard Sudoku is carried out. The analysis of sub-structures for the second erasure correction scheme involves detailed classification of a variety of small sub-structures; the thesis also derives probabilistic lower bounds for the expected numbers of case-specific sub-structures within the puzzle structure, indicating that specific types of sub-structure hinder recovery to such an extent that the scheme is infeasible for practical erasure correction. The consequences of complex cell inter-relationships and wider issues with puzzle-based erasure correction, beyond the structures investigated in the thesis are also discussed, concluding that while there are suggestions in the literature that Sudoku and other puzzle-based combinatorial structures may be useful for erasure correction, the work of this thesis suggests that this is not the case.
APA, Harvard, Vancouver, ISO, and other styles
6

Miller, Sam. "Combinatorial Polynomial Hirsch Conjecture." Scholarship @ Claremont, 2017. https://scholarship.claremont.edu/hmc_theses/109.

Full text
Abstract:
The Hirsch Conjecture states that for a d-dimensional polytope with n facets, the diameter of the graph of the polytope is at most n-d. This conjecture was disproven in 2010 by Francisco Santos Leal. However, a polynomial bound in n and d on the diameter of a polytope may still exist. Finding a polynomial bound would provide a worst-case scenario runtime for the Simplex Method of Linear Programming. However working only with polytopes in higher dimensions can prove challenging, so other approaches are welcome. There are many equivalent formulations of the Hirsch Conjecture, one of which is the Combinatorial Polynomial Hirsch Conjecture, which turns the problem into a matter of counting sets. This thesis explores the Combinatorial Polynomial Hirsch Conjecture.
APA, Harvard, Vancouver, ISO, and other styles
7

Lambie-Hanson, Christopher. "Covering Matrices, Squares, Scales, and Stationary Reflection." Research Showcase @ CMU, 2014. http://repository.cmu.edu/dissertations/368.

Full text
Abstract:
In this thesis, we present a number of results in set theory, particularly in the areas of forcing, large cardinals, and combinatorial set theory. Chapter 2 concerns covering matrices, combinatorial structures introduced by Viale in his proof that the Singular Cardinals Hypothesis follows from the Proper Forcing Axiom. In the course of this proof and subsequent work with Sharon, Viale isolated two reflection principles, CP and S, which can hold of covering matrices. We investigate covering matrices for which CP and S fail and prove some results about the connections between such covering matrices and various square principles. In Chapter 3, motivated by the results of Chapter 2, we introduce a number of square principles intermediate between the classical and (+). We provide a detailed picture of the implications and independence results which exist between these principles when is regular. In Chapter 4, we address three questions raised by Cummings and Foreman regarding a model of Gitik and Sharon. We first analyze the PCF-theoretic structure of the Gitik-Sharon model, determining the extent of good and bad scales. We then classify the bad points of the bad scales existing in both the Gitik-Sharon model and various other models containing bad scales. Finally, we investigate the ideal of subsets of singular cardinals of countable cofinality carrying good scales. In Chapter 5, we prove that, assuming large cardinals, it is consistent that there are many singular cardinals such that every stationary subset of + reflects but there are stationary subsets of + that do not reflect at ordinals of arbitrarily high cofinality. This answers a question raised by Todd Eisworth and is joint work with James Cummings. In Chapter 6, we extend a result of Gitik, Kanovei, and Koepke regarding intermediate models of Prikry-generic forcing extensions to Radin generic forcing extensions. Specifically, we characterize intermediate models of forcing extensions by Radin forcing at a large cardinal using measure sequences of length less than. In the final brief chapter, we prove some results about iterations of w1-Cohen forcing with w1-support, answering a question of Justin Moore.
APA, Harvard, Vancouver, ISO, and other styles
8

Wang, Ruidong. "Combinatorial problems for graphs and partially ordered sets." Diss., Georgia Institute of Technology, 2015. http://hdl.handle.net/1853/54483.

Full text
Abstract:
This dissertation has three principal components. The first component is about the connections between the dimension of posets and the size of matchings in comparability and incomparability graphs. In 1951, Hiraguchi proved that for any finite poset P, the dimension of P is at most half of the number of points in P. We develop some new inequalities for the dimension of finite posets. These inequalities are then used to bound dimension in terms of the maximum size of matchings. We prove that if the dimension of P is d and d is at least 3, then there is a matching of size d in the comparability graph of P, and a matching of size d in the incomparability graph of P. The bounds in above theorems are best possible, and either result has Hiraguchi's theorem as an immediate corollary. In the second component, we focus on an extremal graph theory problem whose solution relied on the construction of a special kind of posets. In 1959, Paul Erdos, in a landmark paper, proved the existence of graphs with arbitrarily large girth and arbitrarily large chromatic number using probabilistic method. In a 1991 paper of Kriz and Nesetril, they introduced a new graph parameter eye(G). They show that there are graphs with large girth and large chromatic number among the class of graphs having eye parameter at most three. Answering a question of Kriz and Nesetril, we were able to strengthen their results and show that there are graphs with large girth and large chromatic number among the class of graphs having eye parameter at most two. The last component is about random posets--the poset version of the Erdos-Renyi random graphs. In 1991, Erdos, Kierstead and Trotter (EKT) investigated random height 2 posets and obtained several upper and lower bounds on the dimension of the random posets. Motivated by some extremal problems involving conditions which force a poset to contain a large standard example, we were compelled to revisit this subject. Our sharpened analysis allows us to conclude that as p approaches 1, the expected value of dimension first increases and then decreases, a subtlety not identified in EKT. Along the way, we establish connections with classical topics in analysis as well as with latin rectangles. Also, using structural insights drawn from this research, we are able to make progress on the motivating extremal problem with an application of the asymmetric form of the Lovasz Local Lemma.
APA, Harvard, Vancouver, ISO, and other styles
9

Williams, Elizabeth C. "A study of Polya's enumeration theorem." Auburn, Ala., 2005. http://repo.lib.auburn.edu/2005%20Summer/master's/WILLIAMS_ELIZABETH_6.pdf.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Krohne, Edward. "Continuous Combinatorics of a Lattice Graph in the Cantor Space." Thesis, University of North Texas, 2016. https://digital.library.unt.edu/ark:/67531/metadc849680/.

Full text
Abstract:
We present a novel theorem of Borel Combinatorics that sheds light on the types of continuous functions that can be defined on the Cantor space. We specifically consider the part X=F(2ᴳ) from the Cantor space, where the group G is the additive group of integer pairs ℤ². That is, X is the set of aperiodic {0,1} labelings of the two-dimensional infinite lattice graph. We give X the Bernoulli shift action, and this action induces a graph on X in which each connected component is again a two-dimensional lattice graph. It is folklore that no continuous (indeed, Borel) function provides a two-coloring of the graph on X, despite the fact that any finite subgraph of X is bipartite. Our main result offers a much more complete analysis of continuous functions on this space. We construct a countable collection of finite graphs, each consisting of twelve "tiles", such that for any property P (such as "two-coloring") that is locally recognizable in the proper sense, a continuous function with property P exists on X if and only if a function with a corresponding property P' exists on one of the graphs in the collection. We present the theorem, and give several applications.
APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "Combinatorial set theory"

1

Halbeisen, Lorenz J. Combinatorial Set Theory. Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-60231-8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Halbeisen, Lorenz J. Combinatorial Set Theory. Springer London, 2012. http://dx.doi.org/10.1007/978-1-4471-2173-2.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Farah, Ilijas. Combinatorial Set Theory of C*-algebras. Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-27093-3.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Anderson, Ian. Combinatorics of finite sets. Clarendon, 1987.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
5

Richard, Warren. The structure of k-CS-transitive cycle-free partial orders. American Mathematical Society, 1997.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
6

Sargsyan, Grigor. Hod mice and the mouse set conjecture. American Mathematical Society, 2015.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
7

service), SpringerLink (Online, ed. Combinatorial Set Theory: With a Gentle Introduction to Forcing. Springer-Verlag London Limited, 2012.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
8

Ian, Anderson. Combinatorics of finite sets. Clarendon Press, 1987.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
9

Ian, Anderson. Combinatorics of finite sets. Dover Publications, 2002.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
10

Trotter, William T. Combinatorics And Partially Ordered Sets: Dimension Theory. The Johns Hopkins University Press, 1992.

Find full text
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Combinatorial set theory"

1

Schimmerling, E. "Combinatorial Set Theory and Inner Models." In Set Theory. Springer Netherlands, 1998. http://dx.doi.org/10.1007/978-94-015-8988-8_14.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Baumgartner, James. "Hajnal’s contributions to combinatorial set theory and the partition calculus." In Set Theory. American Mathematical Society, 2002. http://dx.doi.org/10.1090/dimacs/058/02.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Blass, Andreas. "Combinatorial Cardinal Characteristics of the Continuum." In Handbook of Set Theory. Springer Netherlands, 2009. http://dx.doi.org/10.1007/978-1-4020-5764-9_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Hosono, Kiyoshi, Ferran Hurtado, Masatsugu Urabe, and Jorge Urrutia. "On a Triangle with the Maximum Area in a Planar Point Set." In Combinatorial Geometry and Graph Theory. Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/978-3-540-30540-8_11.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Dasgupta, Anirban, Ravi Kumar, and D. Sivakumar. "Sparse and Lopsided Set Disjointness via Information Theory." In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-32512-0_44.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Uiterwijk, Jos W. H. M., and Lianne V. Hufkens. "Solving Impartial SET Using Knowledge and Combinatorial Game Theory." In Computers and Games. Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-34017-8_9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Cervante, Liam, Bing Xue, Lin Shang, and Mengjie Zhang. "A Multi-objective Feature Selection Approach Based on Binary PSO and Rough Set Theory." In Evolutionary Computation in Combinatorial Optimization. Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-37198-1_3.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Harzheim, E. "A Combinatorial Theorem Which is Related to the Invariance of the Separating Set for the Plane." In Topics in Combinatorics and Graph Theory. Physica-Verlag HD, 1990. http://dx.doi.org/10.1007/978-3-642-46908-4_39.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Dasgupta, Abhijit. "Postscript II: Infinitary Combinatorics." In Set Theory. Springer New York, 2013. http://dx.doi.org/10.1007/978-1-4614-8854-5_12.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Hajnal, András. "Paul Erdős’ Set Theory." In Algorithms and Combinatorics. Springer Berlin Heidelberg, 1997. http://dx.doi.org/10.1007/978-3-642-60406-5_33.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Combinatorial set theory"

1

Shai, Offer, and Andreas Müller. "A Novel Combinatorial Algorithm for Determining the Generic/Topological Mobility of Planar and Spherical Mechanisms." In ASME 2013 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2013. http://dx.doi.org/10.1115/detc2013-13364.

Full text
Abstract:
Structural mobility criteria, such as the well-known Chebychev-Kutzbach-Grübler (CKG) formula, give the correct generic mobility of a linkage (possibly of a certain class, e.g. planar, spherical, spatial) provided that it is not topologically overconstrained. As a matter of fact all known structural mobility criteria are prone to topological redundancies. In this paper a combinatorial algorithm is introduced that determines the correct generic/topological mobility of any planar and spherical mechanism. The algorithm also yields a set of independent links that can be used as input, as well as the redundantly constrained sub-linkages. A mathematical proof of the algorithm and the underlying mathematical concept is presented. The proposed method relies on an established algorithm developed within combinatorial rigidity theory, called pebble game, originally developed for checking the rigidity/immobility of constraint graphs. A novel theorem is introduced and later proved in the paper which in turn enables applying the algorithm to any holonomic planar or spherical mechanism with higher and lower kinematic pairs and multiple joints. A further important result of applying this algorithm is that it gives rise to a decomposition into Assur graphs, which is briefly discussed in this paper.
APA, Harvard, Vancouver, ISO, and other styles
2

Jurewicz, Mateusz, and Leon Derczynski. "Set Interdependence Transformer: Set-to-Sequence Neural Networks for Permutation Learning and Structure Prediction." In Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}. International Joint Conferences on Artificial Intelligence Organization, 2022. http://dx.doi.org/10.24963/ijcai.2022/434.

Full text
Abstract:
The task of learning to map an input set onto a permuted sequence of its elements is challenging for neural networks. Set-to-sequence problems occur in natural language processing, computer vision and structure prediction, where interactions between elements of large sets define the optimal output. Models must exhibit relational reasoning, handle varying cardinalities and manage combinatorial complexity. Previous attention-based methods require n layers of their set transformations to explicitly represent n-th order relations. Our aim is to enhance their ability to efficiently model higher-order interactions through an additional interdependence component. We propose a novel neural set encoding method called the Set Interdependence Transformer, capable of relating the set's permutation invariant representation to its elements within sets of any cardinality. We combine it with a permutation learning module into a complete, 3-part set-to-sequence model and demonstrate its state-of-the-art performance on a number of tasks. These range from combinatorial optimization problems, through permutation learning challenges on both synthetic and established NLP datasets for sentence ordering, to a novel domain of product catalog structure prediction. Additionally, the network's ability to generalize to unseen sequence lengths is investigated and a comparative empirical analysis of the existing methods' ability to learn higher-order interactions is provided.
APA, Harvard, Vancouver, ISO, and other styles
3

Lima, Ana Y. F. de, Briza M. D. de Sousa, Daniel P. Cardeal, et al. "LUNCH: an Answer Set Programming System for Course Scheduling." In Encontro Nacional de Inteligência Artificial e Computacional. Sociedade Brasileira de Computação - SBC, 2023. http://dx.doi.org/10.5753/eniac.2023.234540.

Full text
Abstract:
Timetable scheduling is a known NP-hard problem; despite this, there have been many efforts to enable fast and efficient algorithms and heuristics for such a challenging task. Within the realm of timetable scheduling lies the particularly complex problem of Course Scheduling (CS). The goal in CS is to find an optimal timetable configuration of courses within the constraints set by faculty, course requirements and departmental functions. Answer Set Programming (ASP) is a declarative logic programming paradigm for solving combinatorial search tasks; instead of explicitly writing the solution to the problem, ASP programs define the problem’s constraints and knowledge in a high-level language, leaving the model search to a highly optimized solver. In this work, we construct and showcase LUNCH, an easily extensible, free and open-source system for course scheduling. Notably, we study the use of ASP for course scheduling within the specific context of the Computer Science Department at the University of São Paulo, showing how LUNCH fares against the manual scheduling done in previous years.
APA, Harvard, Vancouver, ISO, and other styles
4

Berg, Jeremias, Fahiem Bacchus, and Alex Poole. "Abstract Cores in Implicit Hitting Set MaxSat Solving (Extended Abstract)." In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/643.

Full text
Abstract:
Maximum satisfiability (MaxSat) solving is an active area of research motivated by numerous successful applications to solving NP-hard combinatorial optimization problems. One of the most successful approaches for solving MaxSat instances from real world domains are the so called implicit hitting set (IHS) solvers. IHS solvers decouple MaxSat solving into separate core-extraction (i.e. reasoning) and optimization steps which are tackled by a Boolean satisfiability (SAT) and an integer linear programming (IP) solver, respectively. While the approach shows state-of-the-art performance on many industrial instances, it is known that there exists instances on which IHS solvers need to extract an exponential number of cores before terminating. Motivated by the simplest of these problematic instances, we propose abstract cores, a compact representation for a potentially exponential number of regular cores. We demonstrate how to incorporate abstract core reasoning into the IHS algorithm and report on an empirical evaluation demonstrating, that including abstract cores into a state-of-the-art IHS solver improves its performance enough to surpass the best performing solvers of the 2019 MaxSat Evaluation.
APA, Harvard, Vancouver, ISO, and other styles
5

I. Garmendia, Andoni, Quentin Cappart, Josu Ceberio, and Alexander Mendiburu. "MARCO: A Memory-Augmented Reinforcement Framework for Combinatorial Optimization." In Thirty-Third International Joint Conference on Artificial Intelligence {IJCAI-24}. International Joint Conferences on Artificial Intelligence Organization, 2024. http://dx.doi.org/10.24963/ijcai.2024/766.

Full text
Abstract:
Neural Combinatorial Optimization (NCO) is an emerging domain where deep learning techniques are employed to address combinatorial optimization problems as a standalone solver. Despite their potential, existing NCO methods often suffer from inefficient search space exploration, frequently leading to local optima entrapment or redundant exploration of previously visited states. This paper introduces a versatile framework, referred to as Memory-Augmented Reinforcement for Combinatorial Optimization (MARCO), that can be used to enhance both constructive and improvement methods in NCO through an innovative memory module. MARCO stores data collected throughout the optimization trajectory and retrieves contextually relevant information at each state. This way, the search is guided by two competing criteria: making the best decision in terms of the quality of the solution and avoiding revisiting already explored solutions. This approach promotes a more efficient use of the available optimization budget. Moreover, thanks to the parallel nature of NCO models, several search threads can run simultaneously, all sharing the same memory module, enabling an efficient collaborative exploration. Empirical evaluations, carried out on the maximum cut, maximum independent set and travelling salesman problems, reveal that the memory module effectively increases the exploration, enabling the model to discover diverse, higher-quality solutions. MARCO achieves good performance in a low computational cost, establishing a promising new direction in the field of NCO.
APA, Harvard, Vancouver, ISO, and other styles
6

Rosen, David W. "Design of Modular Product Architectures in Discrete Design Spaces Subject to Life Cycle Issues." In ASME 1996 Design Engineering Technical Conferences and Computers in Engineering Conference. American Society of Mechanical Engineers, 1996. http://dx.doi.org/10.1115/96-detc/dac-1485.

Full text
Abstract:
Abstract A product’s architecture affects the ability of a company to customize, assemble, service, and recycle the product. Much of the flexibility to address these issues is locked into the product’s design during the configuration design stage when the architecture is determined. The concepts of modules and modularity are central to the description of an architecture, where a module is a set of components that share some characteristic. Modularity is a measure of the correspondence between the modules of a product from different viewpoints, such as functionality and physical structure. The purpose of this paper is to investigate formal foundations for configuration design. Since product architectures are discrete structures, discrete mathematics, including set theory and combinatorics, is used for the investigation. A Product Module Reasoning System (PMRS) is developed to reason about sets of product architectures, to translate design requirements into constraints on these sets, to compare architecture modules from different viewpoints, and to directly enumerate all feasible modules without generate-and-test or heuristic search approaches. The PMRS is described mathematically and applied to the design of architectures for a hand-held tape recorder. Life cycle requirements are used as design criteria.
APA, Harvard, Vancouver, ISO, and other styles
7

Meel, Kuldeep S. "Counting, Sampling, and Synthesis: The Quest for Scalability." In Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}. International Joint Conferences on Artificial Intelligence Organization, 2022. http://dx.doi.org/10.24963/ijcai.2022/817.

Full text
Abstract:
The current generation of symbolic reasoning techniques excel at the qualitative tasks (i.e., when the answer is Yes or No); such techniques sufficed for traditional systems whose design sought to achieve deterministic behavior. In contrast, modern computing systems crucially rely on the statistical methods to account for the uncertainty in the environment, and to reason about behavior of these systems, there is need to look beyond qualitative symbolic reasoning techniques. We will discuss our work focused on the development of the next generation of automated reasoning techniques that can perform higher-order tasks such as quantitative measurement, sampling of representative behavior, and automated synthesis of systems. From a core technical perspective, our work builds on the SAT revolution, which refers to algorithmic advances in combinatorial solving techniques for the fundamental problem of satisfiability (SAT), i.e., whether it is possible to satisfy a given set of constraints. The SAT revolution offers the opportunity to develop scalable techniques for problems that lie beyond SAT from complexity perspective and, therefore, stand to benefit from the availability of powerful SAT engines. Our work seeks to enable a Beyond SAT revolution via design of scalable techniques for three fundamental problems that lie beyond SAT: constrained counting, constrained sampling, and automated synthesis.
APA, Harvard, Vancouver, ISO, and other styles
8

Souza, Uéverton, Fábio Protti, Maise Da Silva, and Dieter Rautenbach. "Multivariate Investigation of NP-Hard Problems: Boundaries Between Parameterized Tractability and Intractability." In XXVIII Concurso de Teses e Dissertações da SBC. Sociedade Brasileira de Computação - SBC, 2020. http://dx.doi.org/10.5753/ctd.2015.9996.

Full text
Abstract:
In this thesis we present a multivariate investigation of the complexity of some NP-hard problems, i.e., we first develop a systematic complexity analysis of these problems, defining its subproblems and mapping which one belongs to each side of an “imaginary boundary” between polynomial time solvability and intractability. After that, we analyze which sets of aspects of these problems are sources of their intractability, that is, subsets of aspects for which there exists an algorithm to solve the associated problem, whose non-polynomial time complexity is purely a function of those sets. Thus, we use classical and parameterized complexity in an alternate and complementary approach, to show which subproblems of the given problems are NP-hard and latter to diagnose for which sets of parameters the problems are fixed-parameter tractable, or in FPT. This thesis exhibits a classical and parameterized complexity analysis of different groups of NP-hard problems. The addressed problems are divided into four groups of distinct nature, in the context of data structures, combinatorial games, and graph theory: (I) and/or graph solution and its variants; (II) flooding-filling games; (III) problems on P3-convexity; (IV) problems on induced matchings.
APA, Harvard, Vancouver, ISO, and other styles
9

Shakarji, Craig M., and Vijay Srinivasan. "Convexity and Optimality Conditions for Constrained Least-Squares Fitting of Planes and Parallel Planes to Establish Datums." In ASME 2017 International Mechanical Engineering Congress and Exposition. American Society of Mechanical Engineers, 2017. http://dx.doi.org/10.1115/imece2017-70899.

Full text
Abstract:
This paper addresses some important theoretical issues for constrained least-squares fitting of planes and parallel planes to a set of input points. In particular, it addresses the convexity of the objective function and the combinatorial characterizations of the optimality conditions. These problems arise in establishing planar datums and systems of planar datums in digital manufacturing. It is shown that even when the input points are in general position: (1) a primary planar datum can contact 1, 2, or 3 input points, (2) a secondary planar datum can contact 1 or 2 input points, and (3) two parallel planes can each contact 1, 2, or 3 input points, but there are some constraints to these combinatorial counts. In addition, it is shown that the objective functions are convex over the domains of interest. The optimality conditions and convexity of objective functions proved in this paper will enable one to verify whether a given solution is a feasible solution, and to design efficient algorithms to find the global optimum solution.
APA, Harvard, Vancouver, ISO, and other styles
10

Corbett, Brian P., and David W. Rosen. "Platform Commonization With Discrete Design Spaces: Introduction of the Flow Design Space." In ASME 2003 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. ASMEDC, 2003. http://dx.doi.org/10.1115/detc2003/dtm-48678.

Full text
Abstract:
Many companies have adopted the usage of common platforms to support the development of product families. The problem addressed in this paper deals with the development of a common platform for an existing set of products that may or may not already form a product family. The common platform embodies the core function, form, and technology base shared across the product family. In this work, we focus on configuration aspects of the platform commonization problem to determine which components are in the platform and the relationships among these components. Configuration design spaces are discrete and combinatorial in nature, but not necessarily purely combinatorial, as certain combinations represent infeasible designs. By carefully forming discrete design spaces and applying constraints to them, feasible design regions can be found and their sizes predicted. The purpose of this paper is to outline our approach to defining configuration design spaces for engineering design, with an emphasis on the mathematics of the spaces and their combinations into larger spaces that more completely capture design requirements. A new design space that models flows among components is introduced. Other design spaces that model physical connectivity, functionality, and assembly considerations are summarized. An example of a family of rechargeable flashlights illustrates the application of the discrete design space approach to develop a common platform.
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Combinatorial set theory"

1

Altstein, Miriam, and Ronald J. Nachman. Rational Design of Insect Control Agent Prototypes Based on Pyrokinin/PBAN Neuropeptide Antagonists. United States Department of Agriculture, 2013. http://dx.doi.org/10.32747/2013.7593398.bard.

Full text
Abstract:
The general objective of this study was to develop rationally designed mimetic antagonists (and agonists) of the PK/PBAN Np class with enhanced bio-stability and bioavailability as prototypes for effective and environmentally friendly pest insect management agents. The PK/PBAN family is a multifunctional group of Nps that mediates key functions in insects (sex pheromone biosynthesis, cuticular melanization, myotropic activity, diapause and pupal development) and is, therefore, of high scientific and applied interest. The objectives of the current study were: (i) to identify an antagonist biophores (ii) to develop an arsenal of amphiphilic topically active PK/PBAN antagonists with an array of different time-release profiles based on the previously developed prototype analog; (iii) to develop rationally designed non-peptide SMLs based on the antagonist biophore determined in (i) and evaluate them in cloned receptor microplate binding assays and by pheromonotropic, melanotropic and pupariation in vivo assays. (iv) to clone PK/PBAN receptors (PK/PBAN-Rs) for further understanding of receptor-ligand interactions; (v) to develop microplate binding assays for screening the above SMLs. In the course of the granting period A series of amphiphilic PK/PBAN analogs based on a linear lead antagonist from the previous BARD grant was synthesized that incorporated a diverse array of hydrophobic groups (HR-Suc-A[dF]PRLa). Others were synthesized via the attachment of polyethylene glycol (PEG) polymers. A hydrophobic, biostablePK/PBAN/DH analog DH-2Abf-K prevented the onset of the protective state of diapause in H. zea pupae [EC50=7 pmol/larva] following injection into the preceding larval stage. It effectively induces the crop pest to commit a form of ‘ecological suicide’. Evaluation of a set of amphiphilic PK analogs with a diverse array of hydrophobic groups of the formula HR-Suc-FTPRLa led to the identification of analog T-63 (HR=Decyl) that increased the extent of diapause termination by a factor of 70% when applied topically to newly emerged pupae. Another biostablePK analog PK-Oic-1 featured anti-feedant and aphicidal properties that matched the potency of some commercial aphicides. Native PK showed no significant activity. The aphicidal effects were blocked by a new PEGylated PK antagonist analog PK-dF-PEG4, suggesting that the activity is mediated by a PK/PBAN receptor and therefore indicative of a novel and selective mode-of-action. Using a novel transPro mimetic motif (dihydroimidazole; ‘Jones’) developed in previous BARD-sponsored work, the first antagonist for the diapause hormone (DH), DH-Jo, was developed and shown to block over 50% of H. zea pupal diapause termination activity of native DH. This novel antagonist development strategy may be applicable to other invertebrate and vertebrate hormones that feature a transPro in the active core. The research identifies a critical component of the antagonist biophore for this PK/PBAN receptor subtype, i.e. a trans-oriented Pro. Additional work led to the molecular cloning and functional characterization of the DH receptor from H. zea, allowing for the discovery of three other DH antagonist analogs: Drosophila ETH, a β-AA analog, and a dF analog. The receptor experiments identified an agonist (DH-2Abf-dA) with a maximal response greater than native DH. ‘Deconvolution’ of a rationally-designed nonpeptide heterocyclic combinatorial library with a cyclic bis-guanidino (BG) scaffold led to discovery of several members that elicited activity in a pupariation acceleration assay, and one that also showed activity in an H. zea diapause termination assay, eliciting a maximal response of 90%. Molecular cloning and functional characterization of a CAP2b antidiuretic receptor from the kissing bug (R. prolixus) as well as the first CAP2b and PK receptors from a tick was also achieved. Notably, the PK/PBAN-like receptor from the cattle fever tick is unique among known PK/PBAN and CAP2b receptors in that it can interact with both ligand types, providing further evidence for an evolutionary relationship between these two NP families. In the course of the granting period we also managed to clone the PK/PBAN-R of H. peltigera, to express it and the S. littoralis-R Sf-9 cells and to evaluate their interaction with a variety of PK/PBAN ligands. In addition, three functional microplate assays in a HTS format have been developed: a cell-membrane competitive ligand binding assay; a Ca flux assay and a whole cell cAMP ELISA. The Ca flux assay has been used for receptor characterization due to its extremely high sensitivity. Computer homology studies were carried out to predict both receptor’s SAR and based on this analysis 8 mutants have been generated. The bioavailability of small linear antagonistic peptides has been evaluated and was found to be highly effective as sex pheromone biosynthesis inhibitors. The activity of 11 new amphiphilic analogs has also been evaluated. Unfortunately, due to a problem with the Heliothis moth colony we were unable to select those with pheromonotropic antagonistic activity and further check their bioavailability. Six peptides exhibited some melanotropic antagonistic activity but due to the low inhibitory effect the peptides were not further tested for bioavailability in S. littoralis larvae. Despite the fact that no new antagonistic peptides were discovered in the course of this granting period the results contribute to a better understanding of the interaction of the PK/PBAN family of Nps with their receptors, provided several HT assays for screening of libraries of various origin for presence of PK/PBAN-Ragonists and antagonists and provided important practical information for the further design of new, peptide-based insecticide prototypes aimed at the disruption of key neuroendocrine physiological functions in pest insects.
APA, Harvard, Vancouver, ISO, and other styles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography