Search

Stabbing Planes (also known as Branch and Cut) is a proof system introduced very recently which, informally speaking, extends the DPLL method by branching on integer linear inequalities instead of single variables. The techniques known so far to prove size and depth lower bounds for Stabbing Planes are generalizations of those used for the Cutting Planes proof system. For size lower bounds these are established by monotone circuit arguments, while for depth these are found via communication complexity and protection. As such these bounds apply for lifted versions of combinatorial statements. Rank lower bounds for Cutting Planes are also obtained by geometric arguments called protection lemmas. In this work we introduce two new geometric approaches to prove size/depth lower bounds in Stabbing Planes working for any formula: (1) the antichain method, relying on Sperner's Theorem and (2) the covering method which uses results on essential coverings of the boolean cube by linear polynomials, which in turn relies on Alon's combinatorial Nullenstellensatz. We demonstrate their use on classes of combinatorial principles such as the Pigeonhole principle, the Tseitin contradictions and the Linear Ordering Principle. By the first method we prove almost linear size lower bounds and optimal logarithmic depth lower bounds for the Pigeonhole principle and analogous lower bounds for the Tseitin contradictions over the complete graph and for the Linear Ordering Principle. By the covering method we obtain a superlinear size lower bound and a logarithmic depth lower bound for Stabbing Planes proof of Tseitin contradictions over a grid graph.

We consider proof complexity in light of the unusual binary encoding of certain combinatorial principles. We contrast this proof complexity with the normal unary encoding in several refutation systems, based on Resolution and Sherali--Adams. We first consider Res(s), which is an extension of Resolution working on s-DNFs (Disjunctive Normal Form formulas). We prove an exponential lower bound of n \Omega (k)/\mathrm{d}(s) for the size of refutations of the binary version of the k-Clique Principle in Res(s), where s=o((log log n) 1/3) and d(s) is a doubly exponential function. Our result improves that of Lauria et al., who proved a similar lower bound for Res(1), i.e., Resolution. For the k-Clique and other principles we study, we show how lower bounds in Resolution for the unary version follow from lower bounds in Res(log n) for the binary version, so we start a systematic study of the complexity of proofs in Resolution-based systems for families of contradictions given in the binary encoding. We go on to consider the binary version of the (weak) Pigeonhole Principle Bin PHPmn. We prove that for any \delta, \epsilon >0, Bin PHPmn requires refutations of size 2n1 \delta in Res(s) for s =O(log 1 2 \epsilon n). Our lower bound cannot be improved substantially with the same method since for m\geq 2 \surd n\mathrm{l}\mathrm{o}\mathrm{g} n we can prove there are 2O(\surd n\mathrm{l}\mathrm{o}\mathrm{g} n) size refutations of Bin PHPmn in Res(log n). This is a consequence of the same upper bound for the unary weak Pigeonhole Principle of Buss and Pitassi. We contrast unary versus binary encoding in the Sherali--Adams (SA) refutation system where we prove lower bounds for both rank and size. For the unary encoding of the Pigeonhole Principle and the Ordering Principle, it is known that linear rank is required for refutations in SA, although both admit refutations of polynomial size. We prove that the binary encoding of the (weak) Pigeonhole Principle Bin PHPmn requires exponentially sized (in n) SA refutations, whereas the binary encoding of the Ordering Principle admits logarithmic rank, polynomially sized SA refutations. We continue by considering a natural refutation system we call "SA+Squares," which is intermediate between SA and Lasserre (Sum-of-Squares). This has been studied under the name static-LS\infty + by Grigoriev et al. In this system, the unary encoding of the Linear Ordering Principle LOPn requires O(n) rank while the unary encoding of the Pigeonhole Principle becomes constant rank. Since Potechin has shown that the rank of LOPn in Lasserre is O(\surd nlog n), we uncover an almost quadratic separation between SA+Squares and Lasserre in terms of rank. Grigoriev et al. noted that the unary Pigeonhole Principle has rank 2 in SA+Squares and therefore polynomial size. Since we show the same applies to the binary Bin PHPn+1 n, we deduce an exponential separation for size between SA and SA+Squares. [ABSTRACT FROM AUTHOR]

Stabbing Planes (also known as Branch and Cut) is a proof system introduced very recently which, informally speaking, extends the DPLL method by branching on integer linear inequalities instead of single variables. The techniques known so far to prove size and depth lower bounds for Stabbing Planes are generalizations of those used for the Cutting Planes proof system. For size lower bounds these are established by monotone circuit arguments, while for depth these are found via communication complexity and protection. As such these bounds apply for lifted versions of combinatorial statements. Rank lower bounds for Cutting Planes are also obtained by geometric arguments called protection lemmas. In this work we introduce two new geometric approaches to prove size/depth lower bounds in Stabbing Planes working for any formula: (1) the antichain method, relying on Sperner's Theorem and (2) the covering method which uses results on essential coverings of the boolean cube by linear polynomials, which in turn relies on Alon's combinatorial Nullenstellensatz. We demonstrate their use on classes of combinatorial principles such as the Pigeonhole principle, the Tseitin contradictions and the Linear Ordering Principle. By the first method we prove almost linear size lower bounds and optimal logarithmic depth lower bounds for the Pigeonhole principle and analogous lower bounds for the Tseitin contradictions over the complete graph and for the Linear Ordering Principle. By the covering method we obtain a superlinear size lower bound and a logarithmic depth lower bound for Stabbing Planes proof of Tseitin contradictions over a grid graph. [ABSTRACT FROM AUTHOR]

Data storage in DNA has recently emerged as a promising archival solution, offering space-efficient and long-lasting digital storage solutions. Recent studies suggest leveraging the inherent redundancy of synthesis and sequencing technologies by using composite DNA alphabets. A major challenge of this approach involves the noisy inference process, obstructing large composite alphabets. This paper introduces a novel approach for DNA-based data storage, offering, in some implementations, a 6.5-fold increase in logical density over standard DNA-based storage systems, with near-zero reconstruction error. Combinatorial DNA encoding uses a set of clearly distinguishable DNA shortmers to construct large combinatorial alphabets, where each letter consists of a subset of shortmers. We formally define various combinatorial encoding schemes and investigate their theoretical properties. These include information density and reconstruction probabilities, as well as required synthesis and sequencing multiplicities. We then propose an end-to-end design for a combinatorial DNA-based data storage system, including encoding schemes, two-dimensional (2D) error correction codes, and reconstruction algorithms, under different error regimes. We performed simulations and show, for example, that the use of 2D Reed-Solomon error correction has significantly improved reconstruction rates. We validated our approach by constructing two combinatorial sequences using Gibson assembly, imitating a 4-cycle combinatorial synthesis process. We confirmed the successful reconstruction, and established the robustness of our approach for different error types. Subsampling experiments supported the important role of sampling rate and its effect on the overall performance. Our work demonstrates the potential of combinatorial shortmer encoding for DNA-based data storage and describes some theoretical research questions and technical challenges. Combining combinatorial principles with error-correcting strategies, and investing in the development of DNA synthesis technologies that efficiently support combinatorial synthesis, can pave the way to efficient, error-resilient DNA-based storage solutions. [ABSTRACT FROM AUTHOR]

In this paper, we define some combinatorial principles to characterize spaces X whose hyperspace satisfies some variation of some classical star selection principle. Specifically, the variations characterized are the selective and absolute versions of the star selection principles for the Menger and Rothberger cases; also, the hyperspaces considered in these characterizations are CL(X), 핂(X), 픽(X) and ℂ핊(X) in both cases, endowed with either the Fell topology or the Vietoris topology. [ABSTRACT FROM AUTHOR]

We investigate the generalized tree properties and guessing model properties introduced by Weiß and Viale, as well as natural weakenings thereof, studying the relationships among these properties and between these properties and other prominent combinatorial principles. We introduce a weakening of Viale and Weiß's Guessing Model Property, which we call the Almost Guessing Property, and prove that it provides an alternate formulation of the slender tree property in the same way that the Guessing Model Property provides and alternate formulation of the ineffable slender tree property. We show that instances of the Almost Guessing Property have sufficient strength to imply, for example, failures of square or the nonexistence of weak Kurepa trees. We show that these instances of the Almost Guessing Property hold in the Mitchell model starting from a strongly compact cardinal and prove a number of other consistency results showing that certain implications between the principles under consideration are in general not reversible. In the process, we provide a new answer to a question of Viale by constructing a model in which, for all regular θ ≥ ω 2 , there are stationarily many ω 2 -guessing models M ∈ P ω 2 H (θ) that are not ω 1 -guessing models. [ABSTRACT FROM AUTHOR]

Atypical predictive processing has been associated with autism across multiple domains, based mainly on artificial antecedents and consequents. As structured sequences where expectations derive from implicit learning of combinatorial principles, language and music provide naturalistic stimuli for investigating predictive processing. In this study, we matched melodic and sentence stimuli in cloze probabilities and examined musical and linguistic prediction in Mandarin‐ (Experiment 1) and English‐speaking (Experiment 2) autistic and non‐autistic individuals using both production and perception tasks. In the production tasks, participants listened to unfinished melodies/sentences and then produced the final notes/words to complete these items. In the perception tasks, participants provided expectedness ratings of the completed melodies/sentences based on the most frequent notes/words in the norms. While Experiment 1 showed intact musical prediction but atypical linguistic prediction in autism in the Mandarin sample that demonstrated imbalanced musical training experience and receptive vocabulary skills between groups, the group difference disappeared in a more closely matched sample of English speakers in Experiment 2. These findings suggest the importance of taking an individual differences approach when investigating predictive processing in music and language in autism, as the difficulty in prediction in autism may not be due to generalized problems with prediction in any type of complex sequence processing. Lay Summary: Predictive processing plays a central role in everyday life. While autism has been associated with atypical prediction across multiple domains, evidence has been mixed and mainly based on artificial rather than naturalistic associations. In two experiments, this study examined predictive processing in Mandarin and English speakers with autism across music and language domains using naturalistic melodic and sentence stimuli through production and perception tasks. Our results reveal musical training experience and receptive vocabulary as confounding factors influencing predictive processing of music and language in autism, suggesting that autism may not be linked to generalized problems with prediction in any type of complex sequence processing. [ABSTRACT FROM AUTHOR]

[Display omitted] • A highly conductive TT-COF(Zn)/NH 2 -CNTs was designed and synthesized. • TT-COF(Zn)/NH 2 -CNTs represents the first example of COF-based tandem electrochemical sensor for detecting I− and Hg2+. • The developed sensor was successfully applied for the analysis of I− and Hg2+ in real samples. The residues of environmental pollutants have aroused intensive concern in food and agriculture safety. An efficient rapid multifunctional sensor for diverse environmental pollutants based on covalent organic framework (COF) represents the huge development of fancy monitoring technique. In this work, the TT-COF(Zn)/NH 2 -CNTs material was successfully designed and fabricated by hybridization means via one-pot synthesized method and can be modified with GCE to construct an electrochemical sensor for the tandem detection of I− and Hg2+ based on combinatorial principles with high selectivity. The sensor displayed wide detecting range of 0.01–2 mM and 0.01–2 mM, as well as low LOD of 6.82 and 1.20 μM for I− and Hg2+, respectively. Furthermore, practical application results in determining the quantification of I− and Hg2+ was convenient and effective. This work employs the COF as the first example to fabricate an electrochemical tandem sensor using combinatorial principles and represents a promising straightforward strategy to exploit diverse functional sensor. [ABSTRACT FROM AUTHOR]

We formalize various counting principles and compare their strengths over V0\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$V^{0}$$\end{document}. In particular, we conjecture the following mutual independence between:a uniform version of modular counting principles and the pigeonhole principle for injections,a version of the oddtown theorem and modular counting principles of modulus p, where p is any natural number which is not a power of 2,and a version of Fisher’s inequality and modular counting principles. Then, we give sufficient conditions to prove them. We give a variation of the notion of PHP-tree and k-evaluation to show that any Frege proof of the pigeonhole principle for injections admitting the uniform counting principle as an axiom scheme cannot have o(n)-evaluations. As for the remaining two, we utilize well-known notions of p-tree and k-evaluation and reduce the problems to the existence of certain families of polynomials witnessing violations of the corresponding combinatorial principles with low-degree Nullstellensatz proofs from the violation of the modular counting principle in concern.a uniform version of modular counting principles and the pigeonhole principle for injections,a version of the oddtown theorem and modular counting principles of modulus p, where p is any natural number which is not a power of 2,and a version of Fisher’s inequality and modular counting principles. [ABSTRACT FROM AUTHOR]

In the study of strong homology Mardešić and Prasolov isolated a certain inverse system of abelian groups A indexed by elements of ω ω . They showed that if strong homology is additive on a class of spaces containing closed subsets of Euclidean spaces then the higher derived limits lim n A must vanish, for n > 0. They also proved that under the Continuum Hypothesis lim 1 A ≠ 0. The question whether lim n A vanishes, for all n > 0 , has attracted considerable interest from set theorists. Dow, Simon and Vaughan showed that under the Proper Forcing Axiom (PFA) lim 1 A = 0. Bergfalk showed that it is consistent that lim 2 A does not vanish. Later Bergfalk and Lambie-Hanson showed that, modulo a weakly compact cardinal, it is relatively consistent with ZFC that lim n A = 0 , for all n. The large cardinal assumption was recently removed by Bergfalk, Hrušak and Lambie-Hanson. We complete the picture by showing that, for any n > 0 , it is relatively consistent with ZFC that lim n A ≠ 0. [ABSTRACT FROM AUTHOR]

The amount of hyperplanes that are needed in order to cover the Boolean cube has been studied in various contexts. Linial and Radhakrishnan introduced the notion of essential covers. An essential cover is a collection of hyperplanes that form a minimal cover of the vertices of the hypercube, and every coordinate is influential in at least one of the hyperplanes. Linial and Radhakrishnan proved using algebraic tools that every essential cover of the n-cube must be of size at least Ω (n) . We devise a stronger lower bound method, and show that the size of every essential cover is at least Ω (n 0.52) . This result has implications in proof complexity, because essential covers have been used to prove lower bounds for several proof systems. [ABSTRACT FROM AUTHOR]

The aim of this article is to re-examine the intellectual history of a principle central to seventeenth-century universal language projects. We call this principle 'word as definition'. It is the requirement that every word in the dictionary of a new language should already be, by its shape, a definition of what it denotes: the root of the word would express the proximate genus and the affixes the specific difference. In Comenius, we find it first formulated in the Via lucis and later elaborated in the Panglottia manuscript. Besides the medieval and early modern mystical traditions, Johann Heinrich Bisterfeld and Marin Mersenne are key figures in the process of its emergence. In this respect, Comenius plays a role in the link between the 'continental' and the British approach to the problem of language reform. [ABSTRACT FROM AUTHOR]

We prove that any proof of a ∀ Σ 2 0 sentence in the theory WKL 0 + RT 2 2 can be translated into a proof in RCA 0 at the cost of a polynomial increase in size. In fact, the proof in RCA 0 can be obtained by a polynomial-time algorithm. On the other hand, RT 2 2 has nonelementary speedup over the weaker base theory RCA 0 * for proofs of Σ 1 sentences. We also show that for n ≥ 0 , proofs of Π n + 2 sentences in B Σ n + 1 + exp can be translated into proofs in I Σ n + exp at a polynomial cost in size. Moreover, the Π n + 2 -conservativity of B Σ n + 1 + exp over I Σ n + exp can be proved in PV , a fragment of bounded arithmetic corresponding to polynomial-time computation. For n ≥ 1 , this answers a question of Clote, Hájek and Paris. [ABSTRACT FROM AUTHOR]

For A ⊆ ω , the coarse similarity class of A, denoted by [ A ] , is the set of all B ⊆ ω such that the symmetric difference of A and B has asymptotic density 0. There is a natural metric δ on the space of coarse similarity classes defined by letting δ ([ A ] , [ B ]) be the upper density of the symmetric difference of A and B. We study the metric space of coarse similarity classes under this metric, and show in particular that between any two distinct points in this space there are continuum many geodesic paths. We also study subspaces of the form { [ A ] : A ∈ } where is closed under Turing equivalence, and show that there is a tight connection between topological properties of such a space and computability-theoretic properties of . We then define a distance between Turing degrees based on Hausdorff distance in the metric space (, δ). We adapt a proof of Monin to show that the Hausdorff distances between Turing degrees that occur are exactly 0, 1 / 2 , and 1, and study which of these values occur most frequently in the senses of Lebesgue measure and Baire category. We define a degree a to be attractive if the class of all degrees at distance 1 / 2 from a has measure 1, and dispersive otherwise. In particular, we study the distribution of attractive and dispersive degrees. We also study some properties of the metric space of Turing degrees under this Hausdorff distance, in particular the question of which countable metric spaces are isometrically embeddable in it, giving a graph-theoretic sufficient condition for embeddability. Motivated by a couple of issues arising in the above work, we also study the computability-theoretic and reverse-mathematical aspects of a Ramsey-theoretic theorem due to Mycielski, which in particular implies that there is a perfect set whose elements are mutually 1-random, as well as a perfect set whose elements are mutually 1-generic. Finally, we study the completeness of (, δ) from the perspectives of computability theory and reverse mathematics. [ABSTRACT FROM AUTHOR]

Abstract Data storage in DNA has recently emerged as a promising archival solution, offering space-efficient and long-lasting digital storage solutions. Recent studies suggest leveraging the inherent redundancy of synthesis and sequencing technologies by using composite DNA alphabets. A major challenge of this approach involves the noisy inference process, obstructing large composite alphabets. This paper introduces a novel approach for DNA-based data storage, offering, in some implementations, a 6.5-fold increase in logical density over standard DNA-based storage systems, with near-zero reconstruction error. Combinatorial DNA encoding uses a set of clearly distinguishable DNA shortmers to construct large combinatorial alphabets, where each letter consists of a subset of shortmers. We formally define various combinatorial encoding schemes and investigate their theoretical properties. These include information density and reconstruction probabilities, as well as required synthesis and sequencing multiplicities. We then propose an end-to-end design for a combinatorial DNA-based data storage system, including encoding schemes, two-dimensional (2D) error correction codes, and reconstruction algorithms, under different error regimes. We performed simulations and show, for example, that the use of 2D Reed-Solomon error correction has significantly improved reconstruction rates. We validated our approach by constructing two combinatorial sequences using Gibson assembly, imitating a 4-cycle combinatorial synthesis process. We confirmed the successful reconstruction, and established the robustness of our approach for different error types. Subsampling experiments supported the important role of sampling rate and its effect on the overall performance. Our work demonstrates the potential of combinatorial shortmer encoding for DNA-based data storage and describes some theoretical research questions and technical challenges. Combining combinatorial principles with error-correcting strategies, and investing in the development of DNA synthesis technologies that efficiently support combinatorial synthesis, can pave the way to efficient, error-resilient DNA-based storage solutions.

The Ginsburg–Sands theorem from topology states that every infinite topological space has an infinite subspace homeomorphic to exactly one of the following five topologies on ω : indiscrete, discrete, initial segment, final segment, and cofinite. The original proof is nonconstructive, and features an interesting application of Ramsey's theorem for pairs (RT 2 2). We analyze this principle in computability theory and reverse mathematics, using Dorais's formalization of CSC spaces. Among our results are that the Ginsburg–Sands theorem for CSC spaces is equivalent to ACA 0 , while for Hausdorff spaces it is provable in RCA 0. Furthermore, if we enrich a CSC space by adding the closure operator on points, then the Ginsburg–Sands theorem turns out to be equivalent to the chain/antichain principle (CAC). The most surprising case is that of the Ginsburg–Sands theorem restricted to T 1 spaces. Here, we show that the principle lies strictly between ACA 0 and RT 2 2 , yielding arguably the first natural theorem from outside logic to occupy this interval. As part of our analysis of the T 1 case we introduce a new class of purely combinatorial principles below ACA 0 and not implied by RT 2 2 which form a hierarchy generalizing the stable Ramsey's theorem for pairs (SRT 2 2). We show that one of these, the Σ 2 0 subset principle (Σ 2 0 - Subset), has the property that it, together with the cohesive principle (COH), is equivalent over RCA 0 to the Ginsburg–Sands theorem for T 1 CSC spaces. [ABSTRACT FROM AUTHOR]

The purpose of this article is to give new constructions of linear orders which are minimal with respect to being non-σ-scattered. Specifically, we will show that Jensen's principle ⋄ implies that there is a minimal Countryman line, answering a question of Baumgartner [5]. We also produce the first consistent examples of minimal non- σ -scattered linear orders of cardinality greater than ℵ 1 , as given a successor cardinal κ + , we obtain such linear orderings of cardinality κ + with the additional property that their square is the union of κ -many chains. We give two constructions: directly building such examples using forcing, and also deriving their existence from combinatorial principles. The latter approach shows that such minimal non- σ -scattered linear orders of cardinality κ + exist for every cardinal κ in Gödel's constructible universe, and also (using work of Rinot [28]) that examples must exist at successors of singular strong limit cardinals in the absence of inner models satisfying the existence of a measurable cardinal μ of Mitchell order μ + +. [ABSTRACT FROM AUTHOR]

These are exciting times for quantum physics as new quantum technologies are expected to soon transform computing at an unprecedented level. Simultaneously network science is flourishing proving an ideal mathematical and computational framework to capture the complexity of large interacting systems. Here we provide a comprehensive and timely review of the rising field of complex quantum networks. On one side, this subject is key to harness the potential of complex networks in order to provide design principles to boost and enhance quantum algorithms and quantum technologies. On the other side this subject can provide a new generation of quantum algorithms to infer significant complex network properties. The field features fundamental research questions as diverse as designing networks to shape Hamiltonians and their corresponding phase diagram, taming the complexity of many-body quantum systems with network theory, revealing how quantum physics and quantum algorithms can predict novel network properties and phase transitions, and studying the interplay between architecture, topology and performance in quantum communication networks. Our review covers all of these multifaceted aspects in a self-contained presentation aimed both at network-curious quantum physicists and at quantum-curious network theorists. We provide a framework that unifies the field of quantum complex networks along four main research lines: network-generalized, quantum-applied, quantum-generalized and quantum-enhanced. Finally we draw attention to the connections between these research lines, which can lead to new opportunities and new discoveries at the interface between quantum physics and network science. [ABSTRACT FROM AUTHOR]

In the present paper, we address the following general question in the framework of classical first-order logic. Assume that a certain mathematical principle can be formalized in a first-order language by a set E of conditional formulas of the form α (v) → β (v) . Given a base theory T, we can use the set of conditional formulas E to extend the base theory in two natural ways. Either we add to T each formula in E as a new axiom (thus obtaining a theory denoted by T + E ) or we extend T by using the formulas in E as instances of an inference rule (thus obtaining a theory denoted by T + E – Rule ). The theory T + E will be stronger than T + E – Rule , but how much stronger can T + E be? More specifically, is T + E conservative over T + E – Rule for theorems of some fixed syntactical complexity Γ ? Under very general assumptions on the set of conditional formulas E, we obtain two main conservation results in this regard. Firstly, if the formulas in E have low syntactical complexity with respect to some prescribed class of formulas Π and in the applications of E – Rule side formulas from the class Π and can be eliminated (in a certain precise sense), then T + E is ∀ B (Π) -conservative over T + E – Rule . Secondly, if, in addition, E is a finite set with m conditional sentences, then nested applications of E – Rule of a depth at most of m suffice to obtain ∀ B (Π) conservativity. These conservation results between axioms and inference rules extend well-known conservation theorems for fragments of first-order arithmetics to a general, purely logical framework. [ABSTRACT FROM AUTHOR]

We show EOPL = PLS U PPAD. Here the class EOPL consists of all total search problems that reduce to the End-of-Potential-Line problem, which was introduced in the works by Hubavcek and Yogev (SICOMP 2020) and Fearnley et al. (JCSS 2020). In particular, our result yields a new simpler proof of the breakthrough collapse CLS = PLS U PPAD by Fearnley et al. (STOC 2021). We also prove a companion result SOPL = PLS U PPADS, where SOPL is the class associated with the Sink-of-Potential-Line problem. [ABSTRACT FROM AUTHOR]

Let TT1 be the combinatorial principle stating that every finite coloring of the infinite full binary tree has a homogeneous isomorphic subtree. Let RT22 and WKL0 denote respectively the principles of Ramsey's theorem for pairs and the weak König lemma. It is proved that TT1 + RT22 + WKL0 is Π30-conservative over the base system RCA0. Thus over RCA0, TT1 and Ramsey's theorem for pairs prove the same Π30-sentences. [ABSTRACT FROM AUTHOR]

Copyright of Central Asian Journal of Art Studies is the property of Central Asian Journal of Art Studies and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

In recent years there has been an increasing interest in studying proof systems stronger than Resolution, with the aim of building more efficient SAT solvers based on them. In defining these proof systems, we try to find a balance between the power of the proof system (the size of the proofs required to refute a formula) and the difficulty of finding the proofs. In this paper we consider the proof systems circular Resolution, Sherali-Adams, Nullstellensatz and Weighted Resolution and we study their relative power from a theoretical perspective. We prove that circular Resolution, Sherali-Adams and Weighted Resolution are polynomially equivalent proof systems. We also prove that Nullstellensatz is polynomially equivalent to a restricted version of Weighted Resolution. The equivalences carry on also for versions of the systems where the coefficients/weights are expressed in unary. The practical interest in these systems comes from the fact that they admit efficient algorithms to find proofs in case these have small width/degree. [ABSTRACT FROM AUTHOR]

Atypical predictive processing has been associated with autism across multiple domains, based mainly on artificial antecedents and consequents. As structured sequences where expectations derive from implicit learning of combinatorial principles, language and music provide naturalistic stimuli for investigating predictive processing. In this study, we matched melodic and sentence stimuli in cloze probabilities and examined musical and linguistic prediction in Mandarin- (Experiment 1) and English-speaking (Experiment 2) autistic and non-autistic individuals using both production and perception tasks. In the production tasks, participants listened to unfinished melodies/sentences and then produced the final notes/words to complete these items. In the perception tasks, participants provided expectedness ratings of the completed melodies/sentences based on the most frequent notes/words in the norms. While Experiment 1 showed intact musical prediction but atypical linguistic prediction in autism in the Mandarin sample that demonstrated imbalanced musical training experience and receptive vocabulary skills between groups, the group difference disappeared in a more closely matched sample of English speakers in Experiment 2. These findings suggest the importance of taking an individual differences approach when investigating predictive processing in music and language in autism, as the difficulty in prediction in autism may not be due to generalized problems with prediction in any type of complex sequence processing., (© 2024 The Authors. Autism Research published by International Society for Autism Research and Wiley Periodicals LLC.)