Search

Abstract: The paper proves a pumping lemma for a certain subclass of mildly context-sensitive languages, the one defined by commutation-augmented pregroup grammars; in addition, an automaton equivalent to such grammars is introduced, augmenting push-down automata by cancellation in the bottom of its stack. [Copyright &y& Elsevier]

Several cryptosystems based on Elliptic Curve Cryptography such as KMOV and Demytko process the message as a point M = (x 0 , y 0) of an elliptic curve with an equation of the form y 2 ≡ x 3 + a x + b (mod n) over a finite field when n is a prime number, or over a finite ring when n = p q is an RSA modulus. Other systems use singular cubic curves such as y 2 ≡ x 3 + a x 2 (mod n) and y 2 + a x y ≡ x 3 (mod n). In this paper, we present a method to find the small solutions of the former modular cubic equations. Our method is based on Coppersmith's technique and enables one to find the solutions (x 0 , y 0) when | x 0 | 3 | y 0 | 2 is smaller than the modulus. [ABSTRACT FROM AUTHOR]

Finite-state dimension, introduced by Dai, Lathrop, Lutz and Mayordomo quantifies the information rate in an infinite sequence as measured by finite-state automata. In this paper, we define a relative version of finite-state dimension. The finite-state relative dimension dim F S Y (X) of a sequence X relative to Y is the finite-state dimension of X measured using the class of finite-state gamblers with oracle access to Y. We show its mathematical robustness by equivalently characterizing this notion using the relative block entropy rate of X conditioned on Y. We derive inequalities relating the dimension of a sequence to the relative dimension of its subsequences along any arithmetic progression (A. P.). These enable us to obtain a strengthening of Wall's Theorem on the normality of A. P. subsequences of a normal sequence, in terms of relative dimension. In contrast to the original theorem, this stronger version has an exact converse yielding a new characterization of normality. We also obtain finite-state analogues of van Lambalgen's theorem on the symmetry of relative normality. [ABSTRACT FROM AUTHOR]

The extended Burrows-Wheeler Transform (eBWT) [Mantaci et al. TCS 2007] is a variant of the BWT, introduced for collections of strings. In this paper, we present the extended r-index , an analogous data structure to the r -index [Gagie et al. JACM 2020]. It occupies O (r) words, with r the number of runs of the eBWT, and offers the same functionalities as the r -index. We also show how to efficiently support finding maximal exact matches (MEMs). We implemented the extended r -index and tested it on circular bacterial genomes and plasmids, comparing it to five state-of-the-art compressed text indexes. While our data structure maintains similar time and memory requirements for answering pattern matching queries as the original r -index, it is the only index in the literature that can naturally be used for both circular and linear input collections. This is an extended version of [Boucher et al., r-indexing the eBWT, SPIRE 2021]. • Introducing the extended r -index (r -index for the eBWT). • Full cyclic pattern matching functionality in O (r) space. • Efficient construction of the extended r -index. • Computation of MEMs with the extended r -index. • Experimental comparison with several compressed indexes on real biological data. [ABSTRACT FROM AUTHOR]

The question if a deterministic finite automaton admits a software reset in the form of a so-called synchronizing word can be answered in polynomial time. In this paper, we extend this algorithmic question to deterministic automata beyond finite automata. We prove that the question of synchronizability becomes undecidable even when looking at deterministic one-counter automata. This is also true for another classical mild extension of regularity, namely, that of deterministic one-turn push-down automata. However, when we combine both restrictions, we arrive at scenarios with a PSPACE -complete (and hence decidable) synchronizability problem. Likewise, we arrive at a decidable synchronizability problem for (partially) blind deterministic counter automata. There are several interpretations of what synchronizability should mean for deterministic push-down automata. This is depending on the role of the stack: should it be empty on synchronization, should it be always the same or is it arbitrary? For the automata classes studied in this paper, the complexity or decidability status of the synchronizability problem is mostly independent of this technicality, but we also discuss one class of automata where this makes a difference. [ABSTRACT FROM AUTHOR]

In this paper, we firstly give the notion of relative ϵ -approximate bisimulations between two fuzzy two-dimensional on-line tessellation automata (F2OTAs) and elaborate that the relative error between two F2OTAs, accompanying with a relative ϵ -approximate bisimulation between them, is less than or equal to ϵ where ϵ ∈ [ 0 , 1 ]. Moreover, if relative ϵ -approximate bisimulations between two F2OTAs are restricted to be surjective functional, then some properties are drawn and by which relative ϵ -approximate bisimulations on a F2OTA are defined. We construct the factor F2OTA of a F2OTA with respect to a relative ϵ -approximate bisimulation on it and describe the relationship between this factor automaton and the original F2OTA. Whereafter, we novelly design two algorithms to compute all maximal relative ϵ -approximate bisimulations on a given F2OTA. Finally, we discuss some interesting properties of bisimulations on F2OTAs. [ABSTRACT FROM AUTHOR]

The paper presents four distinct new ideas and results for communication networks: 1) We show that relay-networks (i.e. communication networks where different nodes use the same coding functions) can be used to model dynamic networks, in a way, akin to Kripke's possible worlds. Changes in the network are modelled by considering a multiverse where different possible situations arise as worlds existing in parallel. 2) We introduce the term model , which is a simple, graph-free symbolic approach to communication networks. This model yields an algorithm to calculate the capacity of a given communication network. 3) We state and prove variants of a theorem concerning the dispersion of information in single-receiver communications. The dispersion theorem resembles the max-flow min-cut theorem for commodity networks. The proof uses a very weak kind of network coding, called routing with dynamic headers. 4) We show that the solvability of an abstract multi-user communication problem is equivalent to the solvability of a single-target communication in a suitable relay network. In the paper, we develop a number of technical ramifications of these ideas and results. We prove a max-flow min-cut theorem for the Rényi entropy with order less than one, given that the sources are equiprobably distributed; conversely, we show that the max-flow min-cut theorem fails for order greater than one. We also show that linear network coding fails for relay networks, although routing with dynamic headers is asymptotically sufficient to reach capacity. [ABSTRACT FROM AUTHOR]

Reynolds' separation logical system for pointer program verification is investigated. This paper proves its completeness theorem that states that every true asserted program is provable in the logical system. In order to prove the completeness, this paper shows the expressiveness theorem that states the weakest precondition of every program and every assertion can be expressed by some assertion. This paper also introduces an extension of the assertion language with inductive definitions and proves the soundness theorem, the expressiveness theorem, and the completeness theorem. [ABSTRACT FROM AUTHOR]

We show that the direct sum, under more relaxed conditions compared to those of Polujan and Pott (2020), can generate bent functions provably outside the completed Maiorana-McFarland class (MM #). We also show that the indirect sum method of generating bent functions, by imposing certain conditions (which are completely absent if only the bentness of the resulting function is required) on the initial bent functions, can be employed in the design of bent functions outside MM #. Furthermore, applying this method to suitably chosen bent functions we construct several generic classes of homogeneous cubic bent functions (considered as a difficult problem) that might possess additional properties (namely without affine derivatives and/or outside MM #). Our results significantly improve upon the best known instances of this type of bent functions given by Polujan and Pott (2020), and additionally we provide a solution to an open problem presented in their paper. [ABSTRACT FROM AUTHOR]

Session types are a type-based approach to correct message-passing programs. A session type specifies a channel's protocol as sequences of exchanges. Aiming to uncover the essential notions of session-based concurrency, prior work defined minimal session types (MSTs), a formulation of session types without the sequentiality construct, and showed a minimality result : every process typable with standard session types can be transformed into a process typable using MSTs. Such a minimality result was proven for a higher-order session π -calculus, in which values are abstractions (functions from names to processes). In this paper, we study MSTs but now for the session π -calculus, the (first-order) language in which values are names and for which session types have been more widely studied. We first show that a new minimality result can be obtained by composing known results. Then, we develop optimizations of this new minimality result and prove also a dynamic correctness guarantee. [ABSTRACT FROM AUTHOR]

In this paper we use the theory of computing to study fractal dimensions of projections in Euclidean spaces. A fundamental result in fractal geometry is Marstrand's projection theorem, which states that for every analytic set E , for almost every line L , the Hausdorff dimension of the orthogonal projection of E onto L is maximal. We use Kolmogorov complexity to give two new results on the Hausdorff and packing dimensions of orthogonal projections onto lines. The first shows that the conclusion of Marstrand's theorem holds whenever the Hausdorff and packing dimensions agree on the set E , even if E is not analytic. Our second result gives a lower bound on the packing dimension of projections of arbitrary sets. Finally, we give a new proof of Marstrand's theorem using the theory of computing. [ABSTRACT FROM AUTHOR]

In this paper we present new constructions of multi-party homomorphic secret sharing (HSS) based on a new primitive that we call homomorphic encryption with decryption to shares (HEDS). Our first scheme, which we call Scooby , is based on many popular fully homomorphic encryption (FHE) schemes with a linear decryption property. Scooby achieves an n -party HSS for general circuits with complexity O (| F | + log ⁡ n) , as opposed to O (n 2 ⋅ | F |) for the prior best construction based on multi-key FHE. Scooby relies on a trusted setup procedure, and can be based on (ring)-LWE with a super-polynomial modulus-to-noise ratio. In our second construction, Scrappy , assuming any generic FHE plus HSS for NC1-circuits, we obtain a HEDS scheme which does not require a super-polynomial modulus. While these schemes all require FHE, in another instantiation, Shaggy , we show how it is also possible to obtain multi-party HSS without FHE, instead relying on the DCR assumption to obtain 4-party HSS for constant-degree polynomials. [ABSTRACT FROM AUTHOR]

In a period-timestamped, relational temporal database, each tuple is timestamped with a period. The timestamp records when the tuple is "alive" in some temporal dimension. Sequenced semantics is a special semantics for evaluating a query in a temporal database. The semantics stipulates that the query must, in effect, be evaluated simultaneously in each time instant using the tuples alive at that instant. Previous research has proposed changes to a database management system's query evaluation engine to support sequenced semantics. We show how to achieve sequenced semantics without modifying a query evaluation engine. Our technique has two pillars. First we use log-segmented timestamps to record a tuple's lifetime. A log-segmented timestamp divides the time-line into segments of known length. Any temporal period can be represented by a small number of such segments. Second, by taking advantage of the properties of log-segmented timestamps, we translate a sequenced query to a non-temporal query, using the operations already present in an unmodified, non-temporal query evaluation engine. The paper provides translations for both relational algebra and SQL. We experimentally evaluate the SQL translation. The primary contribution of this paper is how to implement sequenced semantics using log-segmented timestamped tuples in a generic SQL DBMS. [ABSTRACT FROM AUTHOR]

Many attribute-based anonymous credential (ABC) schemes have been proposed, enabling users to anonymously prove possession of attributes. Recent papers introduced constant-size credentials issued by a single credential issuer for showing a subset of attributes. However, proving possession of attributes from multiple issuers typically requires independent credentials. Only aggregate signature-based attribute-based credential schemes can overcome this limitation. This paper presents new ABC schemes using aggregate signatures with randomizable tags. The schemes consider malicious credential issuers, adaptive corruptions, and collusions with malicious users. While our constructions only support selective attribute disclosures to remain compact, our approach significantly improves the complexity in time and memory for showing multiple attributes. For the first time, the cost for the prover becomes (almost) independent of the number of attributes and issuers. Whereas anonymous credentials require privacy of the user, we also propose the first schemes allowing traceability by a specific tracing authority. [ABSTRACT FROM AUTHOR]

In this paper we study sublogics of RoCTL*, a recently proposed logic for specifying robustness. RoCTL* allows specifying robustness in terms of properties that are robust to a certain number of failures. RoCTL* is an extension of the branching time logic CTL* which in turn extends CTL by removing the requirement that temporal operators be paired with path quantifiers. In this paper we consider three sublogics of RoCTL*. We present a tableau for RoBCTL*, a bundled variant of RoCTL* that allows fairness constraints to be placed on allowable paths. We then examine two CTL-like restrictions of CTL*. Pair-RoCTL* requires a temporal operator to be paired with a path quantifier; we show that Pair-RoCTL* is as hard to reason about as the full CTL*. State-RoCTL* is restricted to State formulas, and we show that there is a linear truth preserving translation of State-RoCTL into CTL, allowing State-RoCTL to be reasoned about as efficiently as CTL. [ABSTRACT FROM AUTHOR]

Emerging networked systems become increasingly flexible, reconfigurable, and "self-⁎". This introduces an opportunity to adjust networked systems in a demand-aware manner, leveraging spatial and temporal locality in the workload for online optimizations. However, it also introduces a tradeoff: while more frequent adjustments can improve performance, they also entail higher reconfiguration costs. This paper studies self-adjusting grid networks in which frequently communicating nodes (e.g., virtual machines) are moved topologically closer in an online and demand-aware manner, striking a balance between the benefits and costs of reconfigurations. The paper presents a general Ω (log ⁡ n) lower bound for this problem, even in scenarios where the demand graph is constant once learned. To demonstrate the challenge of adapting a network to pair-wise communication requests, we also design an O (log ⁡ n) -competitive algorithm for 1-dimensional grids. [ABSTRACT FROM AUTHOR]

This paper proves the decidability of the emptiness problem for two models which recognize finite graphs: graph-walking automata, and tilings of graphs by star subgraphs (star automata). Furthermore, it is proved that the non-emptiness problem for graph-walking automata (that is, whether a given automaton accepts at least one graph) is NEXP-complete. For star automata, which generalize nondeterministic tree automata to the case of graphs, it is proved that their non-emptiness problem is NP-complete. [ABSTRACT FROM AUTHOR]

Software systems rely on events for logging, coordination, handling unusual situations, and more. Monitoring event streams from systems that provide services can ensure the service complies with policies, regulations, and other business rules. Notably, monitoring to detect violations of rules as early as possible is much desired as, for example, the service may reclaim more resources from erring enactments. The primary goal of this paper is to develop techniques for detecting violations of time constraints as early as possible. We formalize a model for events and a language to specify constraints on event timing and data. We develop algorithms to detect violations of individual rules, then use a chase process to detect violations of acyclic sets of rules. We also present optimization techniques to reduce monitoring overhead. Finally, we implement and evaluate our algorithms through experiments to demonstrate our approach is feasible and beneficial. [ABSTRACT FROM AUTHOR]

Recently, the fourth weight of generalized Reed-Muller codes R q (a (q − 1) + b , m) have been characterized for 3 ≤ b < q + 4 3 and 0 ≤ a ≤ m − 3. In this paper, we study the codewords reaching the fourth weight of generalized Reed-Muller codes. We will determine the fourth weight codewords of generalized Reed-Muller codes of order r = a (q − 1) + b with 3 ≤ b < q + 4 3 and 0 ≤ a ≤ m − 3. Also, we characterize the number of fourth weight codewords of R q (b , m) for 3 ≤ b < q + 4 3. [ABSTRACT FROM AUTHOR]

This paper concerns a stochastic construction of probabilistic coherent spaces by employing novel ingredients (i) linear exponential comonad arising properly in the measure-theory (ii) continuous orthogonality between measures and measurable functions. A linear exponential comonad is constructed over a symmetric monoidal category of transition kernels, relaxing Markov kernels of Panangaden's stochastic relations into s-finite kernels. The model supports an orthogonality in terms of an integral between measures and measurable functions, which can be seen as a continuous extension of Girard-Danos-Ehrhard's linear duality for probabilistic coherent spaces. The orthogonality is formulated by a Hyland-Schalk double glueing construction, into which our measure theoretic monoidal comonad structure is accommodated. As an application to countable measurable spaces, a dagger compact closed category is obtained, whose double glueing gives rise to the familiar category of probabilistic coherent spaces. [ABSTRACT FROM AUTHOR]

Quantum computing utilizes properties of quantum physics to build a fast-computing machine that can perform quantum computations. This will eventually lead to faster and more efficient calculations especially when we deal with complex problems. However, there is a downside related to this hardware revolution since the security of widely used cryptographic schemes, e.g., RSA encryption scheme, relies on the hardness of certain mathematical problems that are known to be solved efficiently by quantum computers, i.e., making these protocols insecure. As such, while quantum computers most likely will not be available any time in the near future, it's necessary to create alternative solutions before quantum computers become a reality. This paper therefore provides a comprehensive review of attacks and countermeasures in Post-Quantum Cryptography (PQC) to portray a roadmap of PQC standardization, currently led by National Institute of Standards and Technology (NIST). More specifically, there has been a rise in the side-channel attacks against PQC schemes while the NIST standardization process is moving forward. We therefore focus on the side-channel attacks and countermeasures in major post-quantum cryptographic schemes, i.e., the final NIST candidates. [ABSTRACT FROM AUTHOR]

Given a graph G with vertex set V , a set S ⊆ V is a secure dominating set of G if S is a dominating set of G and if for every vertex u ∈ V ∖ S , there exists a vertex v ∈ S adjacent to u such that (S ∪ { u }) ∖ { v } is a dominating set of G.The minimum secure dominating set (or, for short, MSDS) problem asks to find an MSDS in a given graph. In this paper, we first show that the decision version of the MSDS problem is NP-complete in unit disk graphs, even in grid graphs. Secondly, we give an O (n + m) time t -approximation algorithm for the MSDS problem in several geometric intersection graphs which are K 1 , t -free for some integer t ≥ 3. Finally, we propose a PTAS for the MSDS problem in unit disk graphs. [ABSTRACT FROM AUTHOR]

This paper estimates the number of states in an unambiguous finite automaton (UFA) that is sufficient and in the worst case necessary to simulate an n -state two-way deterministic finite automaton (2DFA) and an n -state two-way unambiguous finite automaton (2UFA). It is proved that a 2UFA with n states can be transformed to a UFA with fewer than 2 n ⋅ n ! states. On the other hand, for every n , there is a language recognized by an n -state 2DFA that requires a UFA with at least Ω ((2 + 1) 2 n ⋅ n − 1) = Ω (5.828 n) states. The latter result is obtained as a lower bound on the rank of a certain matrix. [ABSTRACT FROM AUTHOR]

A group of mutually trusting clients outsources a computation to a remote server, which they do not fully trust and that may be subject to attacks. The clients do not communicate with each other and would like to verify the correctness of the remote computation and the consistency of the server's responses. This paper presents the Conflict-free Operation verification Protocol (COP) that ensures linearizability when the server is correct and preserves fork-linearizability otherwise. Clients that observe each other's operations are consistent and their operations are linearizable. If the server forks two clients by hiding an operation, however, they never again see operations of each other. COP is wait-free in the sense that when executed with a correct server, non-conflicting operations can run without waiting for other clients. The paper gives a precise model for the guarantees of COP and includes a formal analysis that these are achieved. [ABSTRACT FROM AUTHOR]

Allen's Interval Algebra is among the leading formalisms in the area of qualitative temporal reasoning. However, its applications are restricted to linear flows of time. While there is some recent work studying relations between intervals on branching structures, there is no rigorous study of the first-order theory of branching time. In this paper, we approach this problem under a general definition of time structures, namely, tree-like lattices. Allen's work proved that meets is expressively complete in the linear case. We also prove that, surprisingly, it remains complete for all unbounded tree-like lattices. This does not generalize to the case of all tree-like lattices, for which we prove that the smallest complete set of relations has cardinality three. We provide in this paper a sound and complete axiomatic system for both the unbounded and general case, in Allen's style, and we classify minimally complete and maximally incomplete sets of relations. [ABSTRACT FROM AUTHOR]

A finite dynamical system is a system consisting of some finite number of objects that take upon a value from some domain as a state, in which after initialization the states of the objects are updated based upon the states of the other objects and themselves according to a certain update schedule. This paper studies a subclass of finite dynamical systems the synchronous Boolean finite dynamical system ( synchronous BFDS , for short), where the states are Boolean and the state update takes place in discrete time and at the same on all objects. The paper is concerned with three problems, Convergence , Path Intersection , and Cycle Length, of the synchronous BFDS in which the state update functions (or the local state transition functions) are chosen from a predetermined finite basis of Boolean functions B . The paper results characterize their computational complexity. [ABSTRACT FROM AUTHOR]

In a surprising recent result, Gupta–Kamath–Kayal–Saptharishi have proved that over Q any n O ( 1 ) -variate and n -degree polynomial in VP can also be computed by a depth three ΣΠΣ circuit of size 2 O ( n log 3 / 2 ⁡ n ) . 2 Over fixed-size finite fields, Grigoriev and Karpinski proved that any ΣΠΣ circuit that computes the determinant (or the permanent) polynomial of a n × n matrix must be of size 2 Ω ( n ) . In this paper, for an explicit polynomial in VP (over fixed-size finite fields), we prove that any ΣΠΣ circuit computing it must be of size 2 Ω ( n log ⁡ n ) . The explicit polynomial that we consider is the iterated matrix multiplication polynomial of n generic matrices of size n × n . The importance of this result is that over fixed-size fields there is no depth reduction technique that can be used to compute all the n O ( 1 ) -variate and n -degree polynomials in VP by depth 3 circuits of size 2 o ( n log ⁡ n ) . The result of Grigoriev and Karpinski can only rule out such a possibility for ΣΠΣ circuits of size 2 o ( n ) . We also give an example of an explicit polynomial ( NW n , ϵ ( X ) ) in VNP (which is not known to be in VP ), for which any ΣΠΣ circuit computing it (over fixed-size fields) must be of size 2 Ω ( n log ⁡ n ) . The polynomial we consider is constructed from the combinatorial design of Nisan and Wigderson, and is closely related to the polynomials considered in many recent papers (by Kayal–Saha–Saptharishi, Kayal–Limaye–Saha–Srinivasan, and Kumar–Saraf), where strong depth 4 circuit size lower bounds are shown. [ABSTRACT FROM AUTHOR]

We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph G = (V , E) , with local rewards r : E → Z , and three types of positions: black V B , white V W , and random V R forming a partition of V. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, or not, even when | V R | = 0. In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this paper, 1 we show that BWR-games with a constant number of random positions can be solved in pseudo-polynomial time. More precisely, in any BWR-game with | V R | = O (1) , a saddle point in uniformly optimal pure stationary strategies can be found in time polynomial in | V W | + | V B | , the maximum absolute local reward, and the common denominator of the transition probabilities. [ABSTRACT FROM AUTHOR]

In this paper, we prove that the general CNF satisfiability problem can be solved in O ⁎ (1.0638 L) time, where L is the length of the input CNF-formula (i.e., the total number of literals in the formula), which improves the previous result of O ⁎ (1.0652 L) obtained in 2009. Our algorithm was analyzed by using the measure-and-conquer method. Our improvements are mainly attributed to the following two points: we carefully design branching rules to deal with degree-5 and degree-4 variables to avoid previous bottlenecks; we show that some worst cases will not always happen, and then we can use an amortized technique to get further improvements. In our analyses, we provide some general frameworks for analysis and several lower bounds on the decreasing of the measure to simplify the arguments. These techniques may be used to analyze more algorithms based on the measure-and-conquer method. [ABSTRACT FROM AUTHOR]

Timed Recursive CTL (TRCTL) was recently proposed as a merger of two extensions of the well-known branching-time logic CTL: Timed CTL on one hand is interpreted over real-time systems like timed automata, and Recursive CTL (RecCTL) on the other hand obtains high expressiveness through the introduction of a recursion operator. Model checking for the resulting logic is known to be 2-EXPTIME-complete. The aim of this paper is to investigate the possibility to obtain a fragment of lower complexity without losing too much expressive power. It is obtained by a syntactic property called "tail-recursiveness" that restricts the way that recursive formulas can be built. This restriction is known to decrease the complexity of model checking by half an exponential in the untimed setting. We show that this also works in the real-time world: model checking for the tail-recursive fragment of TRCTL is EXPSPACE-complete already in its data complexity, i.e. for a fixed formula. The upper bound is obtained via a model-checking procedure on region graphs combining standard untiming constructions with a tailored algorithm. The lower bound is established by a reduction from a suitable tiling problem. [ABSTRACT FROM AUTHOR]

In this paper, we prove Pspace -completeness of the finite satisfiability and model checking problems for the fragment of Halpern and Shoham interval logic with modality 〈 E 〉 , for the "suffix" relation on pairs of intervals, and modality 〈 D 〉 , for the "sub-interval" relation, under the homogeneity assumption. The result significantly improves the Expspace upper bound recently established for the same fragment, and proves the rather surprising fact that the complexity of the considered problems does not change when we add either the modality for suffixes (〈 E 〉) or, symmetrically, the modality for prefixes (〈 B 〉) to the logic of sub-intervals (featuring only 〈 D 〉). [ABSTRACT FROM AUTHOR]

The point-to-set principle of J. Lutz and N. Lutz (2018) has recently enabled the theory of computing to be used to answer open questions about fractal geometry in Euclidean spaces R n. These are classical questions, meaning that their statements do not involve computation or related aspects of logic. In this paper we extend the reach of the point-to-set principle from Euclidean spaces to arbitrary separable metric spaces X. We first extend two algorithmic dimensions—computability-theoretic versions of classical Hausdorff and packing dimensions that assign dimensions dim ⁡ (x) and Dim (x) to individual points x ∈ X —to arbitrary separable metric spaces and to arbitrary gauge families. Our first two main results then extend the point-to-set principle to arbitrary separable metric spaces and to a large class of gauge families. We demonstrate the power of our extended point-to-set principle by using it to prove new theorems about classical fractal dimensions in hyperspaces. [ABSTRACT FROM AUTHOR]

Abstract interpretation, Hoare logic, and incorrectness (or reverse Hoare) logic are powerful techniques for static analysis of computer programs. They have all been successfully extended to the quantum setting, but developed largely in parallel. This paper explores the relationship between these techniques in the context of verifying quantum while-programs, where the abstract domain and the set of assertions for quantum states are well-structured. We show that any complete quantum abstract interpretation induces a quantum Hoare logic and a quantum incorrectness logic, both being sound and relatively complete. Moreover, the induced logic systems operate in a forward manner, making them more suitable for certain applications. Conversely, any sound and relatively complete quantum Hoare logic or incorrectness logic induces a complete quantum abstract interpretation. As an application, we show the non-existence of any sound and relatively complete quantum Hoare logic or incorrectness logic if tuples of local subspaces are taken as assertions. [ABSTRACT FROM AUTHOR]

Introduced about thirty years ago in the field of data compression, the Burrows-Wheeler Transform (BWT) is a string transformation that, besides being a booster of the performance of memoryless compressors, plays a fundamental role in the design of efficient self-indexing compressed data structures. Finding other string transformations with the same remarkable properties of BWT has been a challenge for many researchers for a long time. In this paper, we introduce a whole class of new string transformations, called local orderings-based transformations , which have all the "myriad virtues" of BWT. As a further result, we show that such new string transformations can be used for the construction of the recently introduced r -index, which makes them suitable also for highly repetitive collections. In this context, we consider the problem of finding, for a given string, the BWT variant that minimizes the number of runs in the transformed string. [ABSTRACT FROM AUTHOR]