33469096
The generalization of generalized automata: expression automata
We explore expression automata with respect to determinism and minimization. We define determinism of expression automata using prefix-freeness. This approach is, to some extent, similar to that of Giammarresi and Montalbano's definition of deterministic generalized automata. We prove that deterministic expression automata languages are a proper subfamily of the regular languages. We close by defining the minimization of deterministic expression automata.
14544092
Intercode Regular Languages
Intercodes are a generalization of comma-free codes. Using the structural properties of finite-state automata recognizing an intercode we develop a polynomial-time algorithm for determining whether or not a given regular language L is an intercode. If the answer is yes, our algorithm yields also the smallest index k such that L is a k-intercode. 
 
Furthermore, we examine the prime intercode decomposition of intercode regular languages and design an algorithm for the intercode primality test of an intercode recognized by a finite-state automaton. We also propose an algorithm that computes the prime intercode decomposition of an intercode regular language in polynomial time. Finally, we demonstrate that the prime intercode decomposition need not be unique.
8774753
Overlap-Free Regular Languages
We define a language to be overlap-free if any two distinct strings in the language do not overlap with each other. We observe that overlap-free languages are a proper subfamily of infix-free languages and also a proper subfamily of comma-free languages. Based on these observations, we design a polynomial-time algorithm that determines overlap-freeness of a regular language. We consider two cases: A language is specified by a nondeterministic finite-state automaton and a language is described by a regular expression. Furthermore, we examine the prime overlap-free decomposition of overlap-free regular languages and show that the prime overlap-free decomposition is not unique.
1251651
Obtaining shorter regular expressions from finite-state automata
We consider the use of state elimination to construct shorter regular expressions from finite-state automata (FAs). Although state elimination is an intuitive method for computing regular expressions from FAs, the resulting regular expressions are often very long and complicated. We examine the minimization of FAs to obtain shorter expressions first. Then, we introduce vertical chopping based on bridge states and horizontal chopping based on the structural properties of given FAs. We prove that we should not eliminate bridge states until we eliminate all non-bridge states to obtain shorter regular expressions. In addition, we suggest heuristics for state elimination that leads to shorter regular expressions based on vertical chopping and horizontal chopping.
10385992
A New Linearizing Restriction in the Pattern Matching Problem
In the pattern matching problem, there can be a quadratic number of matching substrings in the size of a given text. The linearizing restriction finds, at most, a linear number of matching substrings. We first explore two well-known linearizing restriction rules, the longest-match rule and the shortest-match substring searchrule, and show that both rules give the same result when a pattern is an infix-free set even though they have different semantics. Then, we introduce a new linearizing restriction, the leftmost non-overlapping match rule that is suitable for find-and-replace operations in text searching, and propose an efficient algorithm when the pattern is a regular language according to the new match rule.
52184467
International workshop on service oriented software engineering (IW-SOSE'06)
International workshop on service oriented software engineering (IW-SOSE'06) : In Proceeding of the 28th international Conference on Software Engineering (Shanghai, China, May 20 - 28, 2006). ICSE '06.
6196244
Decoding Linear Block Codes Using a Priority-First Search : Performance Analysis and Suboptimal Version
An efficient maximum-likelihood soft-decision decoding algorithm for linear block codes using a generalized Dijkstra's algorithm was proposed by Han, Hartmann, and Chen (1993). We prove that this algorithm is efficient for most practical communication systems where the probability of error is less than 10/sup -3/ by finding an upper bound of the computational effort of the algorithm. A suboptimal decoding algorithm is also proposed. The performance of this suboptimal decoding algorithm is within 0.25 dB of the performance of an optimal decoding algorithm for the (104, 52) binary extended quadratic residue code, and within 0.5 dB of the optimal performance for the (128, 64) binary BCH code, respectively.
1671028
A key management scheme for wireless sensor networks using deployment knowledge
To achieve security in wireless sensor networks, it is important to he able to encrypt messages sent among sensor nodes. Keys for encryption purposes must he agreed upon by communicating nodes. Due to resource constraints, achieving such key agreement in wireless sensor networks is nontrivial. Many key agreement schemes used in general networks, such as Diffie-Hellman and public-key based schemes, are not suitable for wireless sensor networks. Pre-distribution of secret keys for all pairs of nodes is not viable due to the large amount of memory used when the network size is large. Recently, a random key pre-distribution scheme and its improvements have been proposed. A common assumption made by these random key pre-distribution schemes is that no deployment knowledge is available. Noticing that in many practical scenarios, certain deployment knowledge may be available a priori, we propose a novel random key pre-distribution scheme that exploits deployment knowledge and avoids unnecessary key assignments. We show that the performance (including connectivity, memory usage, and network resilience against node capture) of sensor networks can he substantially improved with the use of our proposed scheme. The scheme and its detailed performance evaluation are presented in this paper.
46047704
A New Decoding Algorithm for Complete Decoding of Linear Block Codes
In this paper we present and describe an improved version of the Zero-Neighbors algorithm, which we call the Zero-Coverings algorithm. We also present a method for finding a smallest subset of codewords ( Zero-Coverings) which need to be stored to perform the Zero-Coverings algorithm. For some short codes, the sizes of Zero-Coverings are obtained by computer searches; for long codes, an asymptotic bound on the sizes of such subsets is also given.
18390270
Adaptive Retransmission for Distributed Detection in Wireless Sensor Networks
An approach combining distributed detection with error-correcting codes has recently been proposed to design a fault-tolerant classification system in wireless sensor networks. The detection result of each sensor must be transmitted to a fusion center for making a final decision. The mis-classification probability using this approach is high when the transmission channel is highly noisy. This work proposes a novel adaptive retransmission algorithm to improve the mis classification probability. The fusion center calculates reliability of each received detection result while making the final decision. When the final decision is not reliable, the sensor which has sent the received result with the lowest reliability will be asked to retransmit its detection result by the fusion center. Simulation results show that the misclassification probability can be effectively reduced through the retransmission