For substructural logics with contraction or weakening admitting cut-free sequent calculi, proof search was analyzed using well-quasi-orders on ℕ^d (Dickson’s lemma), yielding Ackermann upper bounds via controlled bad-sequence arguments. For hypersequent calculi, that argument lifted the ordering to the powerset, since a hypersequent is a (multi)set of sequents. This induces a jump from Ackermann to hyper-Ackermann complexity in the fast-growing hierarchy, suggesting that cut-free hypersequent calculi for extensions of the commutative Full Lambek calculus with contraction or weakening (FL_ec/FL_ew) inherently entail hyper-Ackermann upper bounds. We show that this intuition does not hold: every extension of FL_ec and FL_ew admitting a cut-free hypersequent calculus has an Ackermann upper bound on provability. To avoid the powerset, we exploit novel dependencies between individual sequents within any hypersequent in backward proof search. The weakening case, in particular, introduces a Karp-Miller-style acceleration, and it improves the upper bound for the fundamental fuzzy logic MTL. Our Ackermann upper bound is optimal for the contraction case (realized by the logic FL_ec).

Abstract We consider a family of non-classical three-valued logics proposed to model indicative conditionals in natural language. Among these, systems introduced by B. De Finetti, W.S. Cooper, J. Cantwell and R.J. Farrell, as well as some variants that have not appeared in the literature, but seem nevertheless to be natural objects of interest from a formal point of view. Most of these logics are not easily treatable with the standard techniques of algebraic logic. We therefore resort to non-deterministic structures and multiple-conclusion calculi to provide alternative semantical characterizations and axiomatizations. In the best cases—logics given by a finite monadic matrix—this can be done directly, in a modular way, through a procedure due to Shoesmith and Smiley. In the more involved ones—logics preserving degrees of truth—some ingenuity and more sophisticated techniques are required. We characterize these logics by a partial non-deterministic matrix, and show how to produce analytic (and effective) calculi that are complete with respect to this generalized semantics. In all cases, the calculi thus obtained can be straightforwardly converted, by a uniform procedure, into traditional single-conclusion Hilbert-style axiomatizations.

A well-quasi-ordered (wqo) set generalizes the notion of well-foundedness andis a powerful tool for analyzing the complexity of computational problemsthrough upper bounds on the length of controlled bad sequences, known aslength theorems. The finitary multiset extension of a wqo-set induces anordering on finite multisets over elements of that set, where one multisetprecedes another if there exists an injective mapping between their elementsthat preserves the original ordering. In this work, we refine existing lengththeorems for the finitary multiset extension of Higman’s ordering over finitealphabets, and we establish a matching lower bound. As a corollary, weobtain tighter length bounds for the majoring extension of Higman’s orderingover finite alphabets. We demonstrate the application of our results in thecomplexity analysis of noncommutative hypersequent logics.

Abstract Perfect paradefinite algebras are De Morgan algebras expanded with an operation that allows for the full behavior of classical negation to be restored. They form a variety that is term-equivalent to the variety of involutive Stone algebras. Their associated multiple-conclusion (Set-Set) and single-conclusion ( ) order-preserving logics are non-algebraizable self-extensional logics of formal inconsistency and undeterminedness determined by a six-valued matrix. We studied these logics extensively in Gomes et al. ((2022). Electronic Proceedings in Theoretical Computer Science357 56–76.) from both the algebraic and the proof-theoretical perspectives. In the present paper, we continue that study by investigating directions for conservatively expanding these logics with an implication connective (essentially, one that admits the deduction-detachment theorem). We first consider logics given by very simple and manageable non-deterministic semantics whose implication (in isolation) is classical. These, nevertheless, fail to be self-extensional. We then consider the implication realized by the relative pseudo-complement over the six-valued perfect paradefinite algebra. Our strategy is to expand the language of the latter algebra with this connective and study the (self-extensional) Set-Set and order-preserving and $\top$ -assertional logics of the variety induced by the resulting algebra. We provide axiomatizations for such new variety and for such logics, drawing parallels with the class of symmetric Heyting algebras and with Moisil’s “symmetric modal logic.” For the order-preserving Set-Set logic, in particular, we obtain a Set-Set axiomatization that is analytic. We close by studying interpolation properties for these logics and concluding that the new variety has the Maehara amalgamation property.

This paper proposes a visual approach based on a RGB/HSV tag to precise and autonomous landing of unmanned aerial vehicles (UAV). The proposed tag is correctly identified by an algorithm divided in four stages: hue filtering, clustering, matching and center location. The first stage is based on fuzzy matching and highlights the pixels with similar colors to the searched pattern, while ignores the pixels with different colors. The clustering stage is responsible for grouping the pixels by color and proximity. The matching stage compares the searched and found landing points. Finally, the last stage locates the center of the landing point in relation to the UAV location. The proposed approach is significantly different from the state-of-the art techniques, since it is able not only to correctly identify a designated landing point, but also to distinguish it from different landing points. It requires very low computational effort and is very suitable for real-time video applications. The algorithm was successfully used, in an online manner, for location of landing points in real-time, using very limited hardware.