Search

A basic two-terminal secret key generation model is considered, where the interactive communication rate between the terminals may be limited, and in particular may not be enough to achieve the maximum key rate. We first prove a multi-letter characterization of the key-communication rate region (where the number of auxiliary random variables depends on the number of rounds of the communication), and then provide an equivalent but simpler characterization in terms of concave envelopes in the case of unlimited number of rounds. Two extreme cases are given special attention. First, in the regime of very low communication rates, the key bits per interaction bit (KBIB) is expressed with a new “symmetric strong data processing constant”, which has a concave envelope characterization analogous to that of the conventional strong data processing constant. The symmetric strong data processing constant can be upper bounded by the supremum of the maximal correlation coefficient over a set of distributions, which allows us to determine the KBIB for binary symmetric sources, and conclude, in particular, that the interactive scheme is not more efficient than the one-way scheme at least in the low communication-rate regime. Second, a new characterization of the minimum interaction rate needed for achieving the maximum key rate (MIMK) is given, and we resolve a conjecture by Tyagi regarding the MIMK for (possibly nonsymmetric) binary sources. We also propose a new conjecture for binary symmetric sources that the interactive scheme is not more efficient than the one-way scheme at any communication rate. [ABSTRACT FROM PUBLISHER]

Interface theories are employed in the component-based design of concurrent systems. They often emerge as combinations of Interface Automata (IA) and Modal Transition Systems (MTS), e.g., Nyman et al.'s IOMTS, Bauer et al.'s MIO, Raclet et al.'s MI or our MIA. In this paper, we generalise MI to nondeterministic interfaces, for which we properly resolve the longstanding conflict between unspecified inputs being allowed in IA but forbidden in MTS. With this solution we achieve, in contrast to related work, an associative parallel composition, a compositional preorder, a conjunction on interfaces with dissimilar alphabets supporting perspective-based specifications, and a quotienting operator for decomposing nondeterministic specifications in a single theory. In addition, we define a hiding and a restriction operator, complement conjunction with a disjunction operator and illustrate our interface theory by means of a simple example. [ABSTRACT FROM AUTHOR]

Suffix trees are highly regarded data structures for text indexing and string algorithms [MCreight 76, Weiner 73]. For any given string w of length n = | w | , a suffix tree for w takes O ( n ) nodes and links. It is often presented as a compacted version of a suffix trie for w , where the latter is the trie (or digital search tree) built on the suffixes of w . Here the compaction process replaces each maximal chain of unary nodes with a single arc. For this, the suffix tree requires that the labels of its arcs are substrings encoded as pointers to w (or equivalent information). On the contrary, the arcs of the suffix trie are labeled by single symbols but there can be Θ ( n 2 ) nodes and links for suffix tries in the worst case because of their unary nodes. It is an interesting question if the suffix trie can be stored using O ( n ) nodes. We present the linear-size suffix trie , which guarantees O ( n ) nodes. We use a new technique for reducing the number of unary nodes to O ( n ) , that stems from some results on antidictionaries. For instance, by using the linear-size suffix trie, we are able to check whether a pattern p of length m = | p | occurs in w in O ( m log ⁡ | Σ | ) time and we can find the longest common substring of two strings w 1 and w 2 in O ( ( | w 1 | + | w 2 | ) log ⁡ | Σ | ) time for an alphabet Σ. [ABSTRACT FROM AUTHOR]

Kubica et al. [33] and Kim et al. [29] introduced order-preserving pattern matching: for a given text the goal is to find its factors having the same ‘shape’ as a given pattern. Known results include a linear-time algorithm for this problem (in case of polynomially-bounded alphabet) and a generalization to multiple patterns. We propose an index that enables order-preserving pattern matching queries in time proportional to pattern length. The index can be constructed in O ( n log ⁡ log ⁡ n ) expected time or in O ( n log 2 ⁡ log ⁡ n / log ⁡ log ⁡ log ⁡ n ) worst-case time. It is an incomplete order-preserving suffix tree which may miss a single edge label at each branching node. For most applications such incomplete suffix trees provide the same functional power as the complete ones. We show a number of their applications, including computation of longest common factors, longest previously occurring factors and squares in a string in the order-preserving setting. We also give an O ( n log ⁡ n ) -time algorithm constructing complete order-preserving suffix trees. [ABSTRACT FROM AUTHOR]

We study the problem of indexing a text T [ 1 … n ] such that whenever a pattern P [ 1 … p ] and an interval [ α , β ] come as a query, we can report all pairs ( i , j ) of consecutive occurrences of P in T with α ≤ j − i ≤ β . We present an O ( n log ⁡ n ) space data structure with optimal O ( p + k ) query time, where k is the output size. [ABSTRACT FROM AUTHOR]

In this paper we describe a fast algorithm that creates a wavelet tree for a sequence of symbols. We show that a wavelet tree can be constructed in O ( n ⌈ log ⁡ σ / log ⁡ n ⌉ ) time where n is the number of symbols and σ is the alphabet size. [ABSTRACT FROM AUTHOR]

In this paper we extend several well-known document listing problems to the case when documents contain a substring that approximately matches the query pattern. We study the scenario when the query string can contain a wildcard symbol that matches any alphabet symbol; all documents that match a query pattern with one wildcard must be enumerated. We describe a linear space data structure that reports all documents containing a substring P in O ( | P | + σ log ⁡ log ⁡ log ⁡ n + docc ) time, where σ is the alphabet size and docc is the number of listed documents. We also describe a succinct solution for this problem, as well as a solution for an extension of this problem. Furthermore our approach enables us to obtain an O ( n σ ) -space data structure that enumerates all documents containing both a pattern P 1 and a pattern P 2 in the special case when P 1 and P 2 differ in one symbol. [ABSTRACT FROM AUTHOR]

Tablet computers and other mobile devices are widely used in education and other life activities. However, touch screen keyboards are not adapted to languages using alphabets with more letters than the English alphabet has. In this paper, we analyze the existing keyboards on such devices for various languages, influence of keyboard usability on the number of typing errors, and propose keyboard design guidelines for non-English languages. As an example, the layout for the Lithuanian language keyboard (32 native letters and 3 foreign letters) has been presented here. The described solution is not strictly related to the peculiarities of the Lithuanian language alphabet (apart from the number of letters), therefore it is suitable for other languages using a similar number of letters. [ABSTRACT FROM AUTHOR]

Abstract: Partial words are sequences over a finite alphabet that may contain wildcard symbols, called holes, which match, or are compatible with, all letters in the alphabet ((full) words are just partial words without holes). The subword complexity function of a partial word over a finite alphabet assigns to each positive integer, , the number, , of distinct full words over that are compatible with factors of length of . In this paper, with the help of our so-called hole functions, we construct infinite partial words such that for any real number . In addition, these partial words have the property that there exist infinitely many non-negative integers satisfying . Combining these results with earlier ones on full words, we show that this represents a class of subword complexity functions not achievable by full words. We also construct infinite partial words with intermediate subword complexity, that is, between polynomial and exponential. [Copyright &y& Elsevier]

Regular model checking is a form of symbolic model checking for parameterized and infinite-state systems whose states can be represented as words of arbitrary length over a finite alphabet, in which regular sets of words are used to represent sets of states. We present LTL( MSO), a combination of the logics monadic second-order logic ( MSO) and LTL as a natural logic for expressing the temporal properties to be verified in regular model checking. In other words, LTL( MSO) is a natural specification language for both the system and the property under consideration. LTL( MSO) is a two-dimensional modal logic, where MSO is used for specifying properties of system states and transitions, and LTL is used for specifying temporal properties. In addition, the first-order quantification in MSO can be used to express properties parameterized on a position or process. We give a technique for model checking LTL( MSO), which is adapted from the automata-theoretic approach: a formula is translated to a buchi regular transition system with a regular set of accepting states, and regular model checking techniques are used to search for models. We have implemented the technique, and show its application to a number of parameterized algorithms from the literature. [ABSTRACT FROM AUTHOR]

Abstract: In a given word, one can count the number of occurrences of other words as a scattered subword. These counts can be “added” and/or “multiplied.” A subword history gives an instruction of what words to be counted and how these counts to be added and multiplied with other counts or integer constants, and hence, determines its unique value in a given word. Mateescu, Salomaa, and Yu asked: “is it decidable whether the value of a given subword history is non-negative in all words over a given alphabet?” (absoluteness problem). Another important problem is of whether there exists a word in which the value of a given subword history becomes 0 (equality problem). In this paper, we prove the undecidability of the equality problem and show that the equality problem is polynomial-time Karp reducible to the absoluteness problem; thus, the absoluteness problem is also undecidable. This approach solves the open problem actually under stronger conditions than supposed originally. [Copyright &y& Elsevier]

This study extends the understanding of two-element pure codes. Some characteristics of different length two-element pure codes are studied. It is shown that a language is a pure code which contains two distinct primitive words u and v with different lengths if and only if the regular expression u v of the two distinct words u and v is primitive. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we construct a new infinite class of two-character sets in and determine their automorphism groups. From this construction arise new infinite classes of two-weight codes and strongly regular graphs, and a new distance-2 ovoid of the split Cayley hexagon of order 4. [Copyright &y& Elsevier]

Abstract: We give a mass formula for self-dual codes over , where p is an odd prime. Using the mass formula, we classify such codes of lengths up to over the ring , over and over . [Copyright &y& Elsevier]

This paper proposes a novel and simple adaptive control algorithm for the effective delay control and resource utilization of end host multicast (EMcast) when the traffic load becomes heavy in a multigroup network with real-time flows constrained by (σ, ρ) regulators. The control algorithm is implemented at the overlay networks and provides more regulations through a novel (σ, ρ, λ) regulator at each group end host who suffers from heavy input traffic. To our knowledge, it is the first work to incorporate traffic regulators into the end host multicast to control heavy traffic output. Our further contributions include a theoretical analysis and a set of results. We prove the existence and calculate the value of the rate threshold ρ* such that for a given set of K groups, when the average rate of traffic entering the group end hosts ρ¯ > ρ*, the ratio of the worst-case multicast delay bound of the proposed (σ, ρ, λ) regulator over the traditional (σ, ρ) regulator is O((Multiple line equation(s) cannot be represented in ASCII text)) for any integer n. We also prove the efficiency of the novel algorithm and regulator in decreasing worst-case delays by conducting computer simulations. [ABSTRACT FROM AUTHOR]

Various code constructions use expander graphs to improve the error resilience. Often the use of expanding graphs comes at the expense of the alphabet size. In this correspondence, we show that by replacing the balanced expanding graphs used in the above constructions with unbalanced dispersers the alphabet size can be dramatically improved. [ABSTRACT FROM AUTHOR]

We determine the entropy rate of patterns of certain random processes including all finite-entropy stationary processes. For independent and identically distributed (i.i.d.) processes, we also bound the speed at which the per-symbol pattern entropy converges to this rate, and show that patterns satisfy an asymptotic equipartition property. To derive some of these results we upper bound the probability that the nth variable in a random process differs from all preceding ones. [ABSTRACT FROM AUTHOR]

Let Φm ⊆ C be the set of all mth roots of unity, m ∊ IN. A balanced code over Φm is a block code over the alphabet Φm such that each code word is balanced; that is, the complex sum of its components (or weight) is equal to 0. Let Bm (n) be the set of all balanced words of length n over Φm. In this correspondence, it is shown that when m is a prime number, the set Bm(n) is not empty if, and only if, m divides n. In this case, the minimum redundancy for a balanced code over Φm of length n is = ρ(Bm(n)) = n - ∟logm∣Bm(n)∣⅃ ≈ [(m - 1)/2]logm(2πn) - m/2. On the other hand, it is shown that when m = 4, the set B4 (n) is not empty if, and only if, n is even, and in this case, the minimum redundancy for a balanced code over Φ4 of length n is ρ(B4(n)) = n - ∟log4∣B4(n)∣⅃ ≈ log4 n + 0.326. Further, this correspondence completely solves the problem of designing efficient coding methods for balanced codes over Φm, when m = 4. In fact, it reduces the problem of designing efficient coding schemes for balanced codes over Φ4 to the design of efficient balanced codes over the usual bipolar alphabet Φ4 = {-1, +1}. [ABSTRACT FROM AUTHOR]

A simplified alpha-numeric phonetic alphabet is proposed. It uses digits, standard keyboard symbols, and upper- and lowercase letters to give a computer-compatible unambiguous single-character phonetic writing of English. Such a phonetic spelling, in conjunction with a pronouncing dictionary giving standardized pronunciation of English worth in this phonetic alphabet, together with appropriate computer compilers and speech synthesizers and recognition systems, would facilitate man-machine oral communication and expand the use of talking and listening computers. This phonetic text is considerably shorter than standard English, can be written on any typewriter or computer terminal, and is easily learned in a short time. Rules and characteristics of this language are given, and it is compared to other phonetic alphabets. [ABSTRACT FROM AUTHOR]