Narrow Results

Based on recent results from extremal graph theory, we prove that every n-state binary deterministic finite automaton can be converted into an equivalent regular expression of size O(1.742ⁿ) using state elimination. Furthermore, we give improved upper bounds on the language operations intersection and interleaving on regular expressions.

We introduce a technique to formally represent and specify race conditions in multithreaded applications. Answer set programming (ASP) is a logic-based knowledge representation paradigm to formally express belief acquired through reasoning in an application domain. The transparent and expressiveness representation of problems along with powerful non-monotonic reasoning power enable ASP to abstractly represent and solve some certain classes of NP hard problems in polynomial times. We use ASP to formally express race conditions and thus represent potential data races often occurred in multithreaded applications with shared memory models. We then use ASP to generate all possible test inputs and thread interleaving, i.e. scheduling, whose executions would result in deterministically exposing thread interleaving failures. We evaluated the proposed technique with some moderate sized Java programs, and our experimental results confirm that the proposed technique can practically expose common data races in multithreaded programs with low false positive rates. We conjecture that, in addition to generating threads scheduling whose execution order leads to the exposition of data races, ASP has several other applications in constraint-based software testing research and can be utilized to express and solve similar test case generation problems where constraints play a key role in determining the complexity of searches.

Transmission of data over wireless sensor networks (WSNs) poses significant constraints on the energy and bandwidth of the communication system. We consider the problem of decision fusion in a distributed detection system in a classical parallel fusion structure by incorporating the fading channel layer that is omnipresent in WSNs. We use channel coding and transmit diversity schemes, equal gain combining (EGC) and maximum ratio combining (MRC). We employ a multi-carrier modulation scheme over the wireless communication channel. This paper proposes the use of Hamming, low-density parity-check (LDPC) coding, or Viterbi coding. Interleaving is also suggested in this paper using chaotic Baker map randomization for the reduction of the bit error rate (BER). Moreover, the chaotic interleaving adds a degree of security to the transmitted data. Simulation results show that the application of coding and interleaving achieves a performance improvement in the WSN.