Search

A context-free grammar with control language is a pair (G , R) where G is a context-free grammar and R is a regular set over the set of productions of G. Its language consists of all terminal words where the sequence of applied productions belongs to R. We study context-free grammars with control languages belonging to subsets of the set of regular languages. We prove that we can obtain only context-free languages if we use regular commutative and strictly locally 1-testable languages. By strictly locally k -testable, k ≥ 2 , ordered, union-free, ordered, and regular circular control languages, we have no loss in the generative power, i.e., we generate the same family which is obtained by arbitrary regular control sets. • Continuation of investigations the "power/simplification" of families of subregular languages. • Continuation of the work done by the author in the papers [3] , [4] , and [6]. • Research related to papers by Salomaa from the sixties and seventies. • Result on commutative control languages is interesting since it differs from the results for other regulation mechanisms. [ABSTRACT FROM AUTHOR]

In the study of temporal graphs, only paths respecting the flow of time are relevant. In this context, many concepts of walk disjointness have been proposed over the years and the validity of Menger's Theorem, as well as the complexity of related problems, have been investigated. Menger's Theorem states that the maximum number of vertex/edge disjoint paths between two vertices equals the minimum number of vertices/edges required to disconnect them. This paper introduces and investigates a type of disjointness that is only time-dependent. Two walks are said to be snapshot disjoint if they do not use edges active in the same snapshot. The related paths and cut problems are then defined and proved to be W[1]-hard and XP-time solvable when parameterized by the solution size. Additionally, in the light of the definition of Mengerian graphs given by Kempe, Kleinberg, and Kumar in their seminal paper (STOC'2000), we define a snapshot Mengerian graph as a graph G for which there is no time labeling for its edges where Menger's Theorem does not hold in the context of snapshot disjointness. We then characterize Mengerian graphs in terms of forbidden structures and provide a polynomial-time recognition algorithm. All our proofs work on the strict and the non-strict cases. Finally, we also present results about problems defined by similar types of disjointness, namely, multiedge disjointness and departure time disjointness. • A novel type of temporal paths disjointness. • Introduction of related parameters: maximum number of snapshot disjoint paths and minimum size of a snapshot cut. • Tight classification of related problems when parameterized by solution size. • Characterization and polynomial-time recognition of s-Mengerian graphs. • Comparison between parameters and "Mengerian" classes of graphs. [ABSTRACT FROM AUTHOR]

A trigraph is a graph where each pair of vertices is labelled either 0 (a non-arc), 1 (an arc) or ⋆ (both an arc and a non-arc). In a series of papers, Hell and co-authors (see for instance [P. Hell, 2014 [21] ]) proposed to study the complexity of homomorphisms from graphs to trigraphs, called Matrix Partition Problems , where arcs and non-arcs can be both mapped to ⋆-arcs, while a non-arc cannot be mapped to an arc, and vice-versa. Even though Matrix Partition Problems are generalisations of Constraint Satisfaction Problems (CSPs) , they share with them the property of being "intrinsically" combinatorial. So, the question of a possible P-time vs NP-complete dichotomy is a very natural one and was raised in Hell et al.'s papers. We propose a generalisation of Matrix Partition Problems to relational structures and study them with respect to the question of a dichotomy. We first show that trigraph homomorphisms and Matrix Partition Problems are P-time equivalent, and then prove that one can also restrict (with respect to having a dichotomy) to relational structures with a single relation. Failing in proving that Matrix Partition Problems on directed graphs are not P-time equivalent to Matrix Partitions on relational structures, we give some evidence that it might be unlikely by formalising the reductions used in the case of CSPs and by showing that such reductions cannot work for the case of Matrix Partition Problems. We then turn our attention to Matrix Partition problems that can be described by finite sets of (induced-subgraph) obstructions. We show, in particular, that any such problem has finitely many minimal obstructions if and only if it has finite duality. We conclude by showing that on trees (seen as trigraphs) it is NP-complete to decide whether a given tree has a homomorphism to another input trigraph. The latter shows a notable difference on tractability between CSP and Matrix Partition Problems as it is well-known that CSP is tractable on the class of trees. [ABSTRACT FROM AUTHOR]

Cellular automata are a famous model of computation, yet it is still a challenging task to assess the computational capacity of a given automaton; especially when it comes to showing negative results. In this paper, we focus on studying this problem via the notion of CA intrinsic simulation. We say that automaton A is simulated by B if each space-time diagram of A can be, after suitable transformations, reproduced by B. We study affine automata – i.e., automata whose local rules are affine mappings of vector spaces. This broad class contains the well-studied cases of linear automata. The main result of this paper shows that (almost) every automaton affine over a finite field F p can only simulate affine automata over F p. We discuss how this general result implies, and widely surpasses, limitations of linear and additive automata previously proved in the literature. We provide a formalization of the simulation notions into algebraic language and discuss how this opens a new path to showing negative results about the computational power of cellular automata using deeper algebraic theorems. [ABSTRACT FROM AUTHOR]

In the famous paper in which he introduced what is now known as the Turing machine, Alan Turing gave a definition of computable real numbers under which it turns out that multiplication by 3 is uncomputable. This shortcoming vanished in a Correction to his paper that Turing himself published shortly afterwards, but it clearly illustrates the subtlety of defining computability issues correctly. In this paper, we give the name "printable" to real numbers that Turing originally called "computable", we recall what is now the generally accepted definition of computable real numbers (which is not quite Turing's amended definition, but is equivalent to it), and we contrast the two notions. Despite the fact that the multiplication by 3 of printable numbers is uncomputable, as opposed to the same operation on computable numbers, a real number is computable if and only if it is printable. The resolution of this apparent paradox is that no machine can transform the "computable" description of a real number to its "printable" description, as Turing proved in his Correction. Finally, we address the subtle issue of allowing or not the printable description of a real number to end with an infinite sequence of 9s (or of 1s in binary), which was left open by Turing in his Correction. Several of these results were already known, as they appear in scattered places, some in non-refereed publications, but we give a unified treatment with some different proofs and a historical perspective. • Alan Turing's original definition of computable real numbers was inadequate. • Turing's use of the word Entscheidungsproblem led us to invent the Druckproblem. • The correct definition of computable real numbers is very subtle. • All computable real numbers are printable, but this is inherently non-constructive. • Discontinuous functions of the real numbers on closed intervals are uncomputable. [ABSTRACT FROM AUTHOR]

The complexity of the list homomorphism problem for signed graphs appears difficult to classify. Existing results focus on special classes of signed graphs, such as trees [4] and reflexive signed graphs [25]. Irreflexive signed graphs are in a certain sense the heart of the problem, as noted by a recent paper of Kim and Siggers. We focus on a special class of irreflexive signed graphs, namely those in which the unicoloured edges form a spanning path or cycle, which we call separable signed graphs. We classify the complexity of list homomorphisms to these separable signed graphs; we believe that these signed graphs will play an important role for the general resolution of the irreflexive case. We also relate our results to a conjecture of Kim and Siggers concerning the special case of semi-balanced irreflexive signed graphs; we have proved the conjecture in another paper, and the present results add structural information to that topic. [ABSTRACT FROM AUTHOR]

Accordingly to Duchet (1987), the first paper of convexity on general graphs, in english, is the 1981 paper "Convexity in graphs". One of its authors, Frank Harary, introduced in 1984 the first graph convexity games, focused on the geodesic convexity, which were investigated in a sequence of five papers that ended in 2003. In this paper, we continue this research line, extend these games to other graph convexities, and obtain winning strategies and complexity results. Among them, we obtain winning strategies for general convex geometries and winning strategies for trees from the Sprague-Grundy theory on impartial games. We also obtain the first PSPACE-hardness results on convexity games, by proving that the normal play and the misère play of the impartial hull game on the geodesic convexity is PSPACE-complete even in graphs with diameter two. [ABSTRACT FROM AUTHOR]

Watson-Crick D0L systems (WD0L systems) are augmented variants of D0L systems defined over a DNA-like alphabet, where each letter has a complementary letter and this relation is symmetric. WD0L systems operate under a control that is inspired by the well-known phenomenon of Watson-Crick complementarity of the double helix of DNA. Depending on a trigger, the standard D0L rewriting step is applied either to the string or to its complementary string. In this paper, we examine extended networks of standard Watson-Crick D0L systems (ENSWD0L systems) with a variant of incomplete communication. An NWD0L system is a finite set of WD0L systems defined over a common DNA-like alphabet and operating in a synchronized manner. After rewriting their own strings in the WD0L manner, they communicate copies of certain generated strings (the so-called good strings) to the other nodes. In some previous papers, it was shown that ENSWD0L systems are computationally complete, and their computational power does not change if the communicated string is a non-empty prefix (non-empty suffix) of the generated string. We strengthen the previous results, namely we show that ENSWD0L systems are computationally complete even if the communicated string is an arbitrary substring of the generated string. • We define a new communication protocol for extended networks of standard Watson-Crick D0L systems (ENSWD0L systems). • We show that ENSWD0L systems communicating substrings are computationally complete. • Communication of incomplete strings does not decrease the generative power of ENSWD0L systems. [ABSTRACT FROM AUTHOR]

This paper presents a new McEliece-type cryptosystem using Gabidulin-Kronecker product codes in the rank metric. The contributions of this paper are as follows. Firstly, we propose a new Gabidulin-Kronecker product code which is a kind of block circulant code, and give an efficient decoding algorithm. Secondly, we design a one-way secure public key encryption scheme based on the Gabidulin-Kronecker product codes. Thirdly, we obtain an IND-CCA2 secure public key encryption scheme by converting our one-way secure public key encryption scheme under the hardness assumption of the RSD Dual Problem. In terms of efficiency, our scheme has a smaller public key size by taking advantage of the block circulant structure. For 128-bit security, the public key size of our proposal is 13% of Lau-Tan's cryptosystem (in the rank metric), and 19% of BIKE (in the Hamming metric). In terms of security, our scheme can resist Overbeck attack, Coggia-Couvreur attack and Sendrier attack. [ABSTRACT FROM AUTHOR]

Modern distributed systems are becoming pervasive and increasingly provided with adaptation, (self-)reconfiguration and mobility capability. On one side, to face the challenges of the highly dynamic environments where they are deployed. On the other side, to keep production/maintenance costs down. Therein lies the increasing demand for formal models encompassing all of these aspects (besides concurrency). Hardly any of the classical formalisms like Petri Nets, Automata, and Process Algebra, even though powerful, permits designers to easily specify dynamic structural changes to systems and evaluate their impact on system behaviour. That has led to several extensions of classical formal models (e.g., the Pi calculus or the Nets-within-Nets paradigm) rarely accompanied by suitable analysis techniques. A recent formalization of a class of Rewritable Place-Transition Nets (RwPT) in Maude has proved potentially convenient to specify dynamically reconfigurable systems. Concerning analogous proposals, the RwPT formalism provides more abstraction/flexibility in modelling and efficiency in analysis. Nevertheless, its ability to scale the size of distributed systems built of several similar (nested) components is limited. This paper presents a compositional approach to define large RwPT models in a typical algebraic way and to exploit the modular structure of models during the analysis: Symmetries are implicitly captured by composite node-labelling (reflecting the model's hierarchical structure) that is preserved by net rewrites. A distributed, gracefully degrading production system is used as a case study. Experimental evidence points out the dramatic impact of the approach against a non-modular one and the advantages over alternative techniques. Even if the emphasis is on state-space-based verification, the paper shows the convenience of combining it with structural analysis, which is typical of Petri nets as well. For that purpose, rewrite-rule abstractions are given in the form of guidelines. [ABSTRACT FROM AUTHOR]

There are many infinite families of 2-designs and 3-designs supported by linear codes in the literature. Recently, several infinite families of 4-designs from linear codes were discovered. But no infinite family of linear codes supporting an infinite family of nontrivial simple 5-designs is reported in the literature. It is not easy to construct 5-designs from sporadic codes. Only a small number of sporadic 5-designs supported by linear codes are available in the literature. In this paper, we construct eight 5-designs from some lifted codes of some known linear codes. • There are many infinite families of 2-designs and 3-designs supported by linear codes in the literature. • Recently, several infinite families of 4-designs from linear codes were discovered. • But no infinite family of linear codes supporting an infinite family of nontrivial simple 5-designs is reported in the literature. • It is not easy to construct 5-designs from sporadic codes. Only a small number of sporadic 5-designs supported by linear codes are available in the literature. • In this paper, we construct eight new 5-designs from some lifted codes of some known linear codes. [ABSTRACT FROM AUTHOR]

Sorting is a fundamental component in many different applications including web indexing engines, geographic information systems, data mining and database systems. However, the existing optimal algorithms still cause huge costs when the input data becomes very large. Thus, the approximate sorting for big data is considered in this paper. The goal of approximate sorting for big data is to generate an approximate sorted result, but using less CPU and I/O cost. For big data, we consider the approximate sorting and applications for approximate sorted results in I/O model. The quality of approximate sorting results is usually measured by the distance metrics on permutation space. However, the existing metrics on permutation space are not available for external approximate sorting algorithms. Thus, we propose a new kind of metric named External metric, which ignores the errors and dislocations that happened in each I/O block. The External metric of Spearman's footrule metric is named as External Spearman's footrule metric (short as ESP metric), which is analyzed in this paper. Furthermore, to facilitate a better evaluation of the approximate sorted result, we propose a new metric, named as errors , which directly states the number of dislocation of the elements. The External errors are also considered in this paper. Then, according to the rate-distortion relationship under these two metrics, the lower bound of these two metrics on external approximate sorting problem with t I/O operations is proved. We propose a k-passes external approximate sorting algorithm, named as EASORT, and prove that EASORT is asymptotically optimal under ESP metric. Finally, we consider the applications on approximate sorting results. An index for the approximate sorted result is proposed. The single and range query on approximate sorted result using this index are also analyzed. Further, the sort-merge join on two relations, where one of the relations is approximate sorted or both relations are approximate sorted, are all discussed in this paper. • This paper first discusses the approximate sorting in I/O model. • This paper proposes a new external metric to evaluate the approximate sorted result. • This paper analyzes the lower bound of two metrics of approximate sorted result. • This paper proposes a new external approximate sorting algorithm. • This paper analyzes the applications on approximate sorted result. [ABSTRACT FROM AUTHOR]

Syntactic models constitute one of the main areas of mathematical studies on picture array generation. A number of 2D grammar models have been proposed with motivation from a variety of applications. Parallel Contextual Array Insertion Deletion Grammar (PCAIDG) and Pure 2D Context-Free Grammar (P2DCFG) are two such 2D grammars. In the case of P2DCFG, two new variants are studied with interesting properties. In this paper we show that PCAIDG has higher generative power than the generative powers of two variants of P2DCFG. Further, P systems associated with the grammars PCAIDG, P2DCFG and their variants are considered in the literature. In this paper, we show that the generative power of Parallel Contextual Array Insertion Deletion P System (PCAIDPS) is greater than the generative power of the P system associated with a variant of P2DCFG. [ABSTRACT FROM AUTHOR]

In this paper, we study the Differentially Private Empirical Risk Minimization (DP-ERM) problem, considering both convex and non-convex loss functions. For cases where DP-ERM involves smooth (strongly) convex loss functions with or without non-smooth regularization, we propose several novel methods. These methods achieve (near) optimal expected excess risks (i.e., utility bounds) while reducing the gradient complexity compared to existing approaches. When dealing with DP-ERM and smooth convex loss functions in high dimensions, we introduce an algorithm that achieves a superior upper bound with lower gradient complexity than previous solutions. In the second part of the paper, for DP-ERM with non-convex loss functions, we explore both low and high dimensional spaces. In the low dimensional case with a non-smooth regularizer, we extend an existing approach by measuring the utility using the ℓ 2 norm of the projected gradient. Furthermore, we introduce a novel error bound measurement, transitioning from empirical risk to population risk by employing the expected ℓ 2 norm of the gradient. For the high dimensional case, we demonstrate that by measuring utility with the Frank-Wolfe gap, we can bound the utility using the Gaussian Width of the constraint set, instead of the dimensionality (p) of the underlying space. We also show that the advantages of this approach can be achieved by measuring the ℓ 2 norm of the projected gradient. Finally, we reveal that the utility of certain special non-convex loss functions can be reduced to a level (depending only on log ⁡ p) similar to that of convex loss functions. [ABSTRACT FROM AUTHOR]

Non-interactive zero-knowledge proofs as well as succinct non-interactive argument of knowledge (SNARK) are playing a central role in both theory and application of cryptography. Simulation extractable for SNARKs is considered a necessary security requirement by most applications which prevents the protocol from malleable attacks. However, a trusted party is required to generate the common reference string (CRS) for SNARKs which can be quite problematic in real applications. Recently, the subvertible and updatable CRS model has been proposed to relax the trust in the CRS generation procedure. In this paper, we propose two generic compilers that can achieve simulation extractable in the updatable CRS model. By using an efficient updatable verifiable random function defined in this paper which may be of independent interest, we show that our compiler can lift the updatable knowledge soundness of the underlying SNARKs to achieve updatable simulation extractability. We extend our results by proposing another compiler that can lift a NIZK that has an even weaker security notion called updatable soundness to achieve updatable simulation extractability. We instantiate our compilers and compare them to other related works. This shows that our efficient compilers can be used in various applications. [ABSTRACT FROM AUTHOR]

The problem of two-sided matching markets is well-studied in computer science and economics, owing to its diverse applications across numerous domains. Since market participants are usually uncertain about their preferences in various online matching platforms, an emerging line of research is dedicated to the online setting where one-side participants (players) learn their unknown preferences through multiple rounds of interactions with the other side (arms). Sankararaman et al. [23] provide an Ω (N log ⁡ (T) Δ 2 + K log ⁡ (T) Δ) regret lower bound for this problem under serial dictatorship assumption, where N is the number of players, K (≥ N) is the number of arms, Δ is the minimum reward gap across players and arms, and T is the time horizon. Serial dictatorship assumes arms have the same preferences, which is common in reality when one side participants have a unified evaluation standard. Recently, the work of Kong and Li [10] proposes the ET-GS algorithm and achieves an O (K log ⁡ (T) Δ 2 ) regret upper bound, which is the best upper bound attained so far. Nonetheless, a gap between the lower and upper bounds, ranging from N to K , persists. It remains unclear whether the lower bound or the upper bound needs to be improved. In this paper, we propose a multi-level successive selection algorithm that obtains an O (N log ⁡ (T) Δ 2 + K log ⁡ (T) Δ) regret bound when the market satisfies serial dictatorship. To the best of our knowledge, we are the first to propose an algorithm that matches the lower bound in the problem of matching markets with bandits. [ABSTRACT FROM AUTHOR]

Given an edge-weighted metric complete graph with n vertices, the maximum weight metric triangle packing problem is to find a set of n / 3 vertex-disjoint triangles with the total weight of all triangles in the packing maximized. Several simple methods can lead to a 2/3-approximation ratio. However, this barrier is not easy to break. Chen et al. proposed a randomized approximation algorithm with an expected ratio of (0.66768 − ε) for any constant ε > 0. In this paper, we improve the approximation ratio to (0.66835 − ε). Furthermore, we can derandomize our algorithm. [ABSTRACT FROM AUTHOR]

Resistance distance has been studied extensively in the past years, with the majority of previous studies devoted to undirected networks, in spite of the fact that various realistic networks are directed. Although several generalizations of resistance distance on directed graphs have been proposed, they either have no physical interpretation or are not a metric. In this paper, we first extend the definition of resistance distance to strongly connected directed graphs based on random walks and show that the two-node resistance distance on directed graphs is a metric. Then, we introduce the Laplacian matrix for directed graphs that subsumes the Laplacian matrix of undirected graphs as a particular case, and use its pseudoinverse to express the two-node resistance distance, and many other relevant quantities derived from resistance distances. Moreover, we define the resistance distance between a vertex and a vertex group on directed graphs and further define a problem of optimally selecting a group of fixed number of nodes, such that their resistance distance is minimized. Since this combinatorial optimization problem is NP-hard, we present a greedy algorithm with a proved approximation ratio, and conduct experiments on model and realistic networks to validate the performance of this approximation algorithm. [ABSTRACT FROM AUTHOR]

In this paper we introduce a new feasible notion of Bennett's logical depth based on pebble transducers. This notion is defined based on the difference between the minimal length descriptional complexity of prefixes of infinite sequences from the perspective of finite-state transducers and pebble transducers. Our notion of pebble-depth satisfies the four fundamental properties of depth: i.e. deep sequences exist, trivial sequences are not deep, random sequences are not deep, and the existence of a slow growth law type result. We also compare pebble-depth to other depth notions based on finite-state transducers, pushdown compressors, and the Lempel-Ziv 78 compression algorithm. We first demonstrate how there exists a normal pebble-deep sequence even though there is no normal finite-state-deep sequence. We next build a sequence that has a pebble-depth level of roughly 1, a pushdown-depth level of roughly 1/2 and a finite-state-depth level of roughly 0. We then build a sequence that has a pebble-depth level of roughly 1/2 and a Lempel-Ziv-depth level of roughly 0. [ABSTRACT FROM AUTHOR]

Robustly reusable Fuzzy Extractor (rrFE) allows multiple extractions from the same fuzzy source in a reproducible way. The reusability of rrFE asks the pseudo-randomness of the extracted keys, while robustness of rrFE makes sure that active attacks can be detected during the reproduction of the extracted key. With rrFE, we are able to produce cryptographic keys for our cryptosystems from fuzzy sources, like biometrics, physical unclonable functions, etc. There are rrFE schemes from the DDH, LWE and LPN assumptions. However there is no rrFE scheme from isogeny-based assumptions up to now. In this paper, we construct the first rrFE from isogeny. To obtain such an rrFE, we propose a new framework for constructing rrFE with a core technical tool, named Enhanced Effective Group Action (EEGA). EEGA is built upon the basic Effective Group Action (EGA), and is equipped with a sampling algorithm and a derivation algorithm. With such an EEGA, the same random input can be derived to produce different pseudo-random and unpredictable outputs. The EEGA, together with other routine building blocks like secure sketch and extractor, leverages an FE to achieve reusability and robustness. We construct EEGA based on CSI-FiSh, which admits the first rrFE scheme from isogeny. Besides, we also propose another two EEGA instantiations from the DDH assumption, and this provides another approach to DDH-based rrFE, which may be of independent interest. [ABSTRACT FROM AUTHOR]