Advances in Logical Systems and Computational Complexity

The field of logical systems and computational complexity is witnessing significant developments, with a focus on exploring the boundaries of decidability, expressivity, and computational feasibility. Researchers are investigating the undecidability of linear logics, the expressivity of temporal constraint languages, and the computational complexity of various logical systems. Notably, the study of symmetric formulations and the Sum-of-Squares hierarchy is revealing new insights into the interplay between symmetry, degree, and bit size in proof complexity. Furthermore, advances in first-order modal logic are expanding our understanding of decidability and complexity in these systems.

Some noteworthy papers in this area include: The paper on Undecidability of Linear Logics without Weakening, which establishes the undecidability of two systems derived from classical propositional linear logic. The paper on Janus-faces of temporal constraint languages, which reveals a dichotomy of expressivity in temporal constraint languages and provides new algebraic consequences. The paper on Computing the Elementary Symmetric Polynomials in Positive Characteristics, which extends formula lower bounds to fields of positive characteristic and shows limitations on the representability of polynomials. The paper on On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations, which proves that symmetry alone does not lead to large bit size SoS proofs. The paper on Decidability in First-Order Modal Logic with Non-Rigid Constants and Definite Descriptions, which investigates the decidability of monodic fragments with non-rigid constants and definite descriptions.

Sources

Undecidability of Linear Logics without Weakening

Janus-faces of temporal constraint languages: a dichotomy of expressivity

Computing the Elementary Symmetric Polynomials in Positive Characteristics

On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations

Decidability in First-Order Modal Logic with Non-Rigid Constants and Definite Descriptions

Built with on top of