On the Gap-Complexity of Simple RL-Automata

Analysis by reduction is a method used in linguistics for checking the correctness of sentences of natural languages. This method is modelled by restarting automata. All types of restarting automata considered in the literature up to now accept at least the deterministic context-free languages. Here we introduce and study a new type of restarting automaton, the so-called t-RL-automaton, which is an RL-automaton that is rather restricted in that it has a window of size one only, and that it works under a minimal acceptance condition. On the other hand, it is allowed to perform up to t rewrite (that is, delete) steps per cycle. Here we study the gap-complexity of these automata. The membership problem for a language that is accepted by a t-RL-automaton with a bounded number of gaps can be solved in polynomial time. On the other hand, t-RL-automata with an unbounded number of gaps accept NP-complete languages.

The Complexity of Safety Stock Placement in General-Network Supply Chains

We consider the optimization problem of safety stock placement in a supply chain, as formulated in [1]. We prove that this problem is NP-Hard for supply chains modeled as general acyclic networks. Thus, we do not expect to find a polynomial-time algorithm for safety stock placement for a general-network supply chain.

An investigation of the germylene addition reaction, GeH2+C2H2: Time-resolved gas-phase kinetic studies and quantum chemical calculations of the reaction energy surface

Time resolved studies of germylene, GeH2, generated by laser flash photolysis of 3,4-dimethylgermacyclopentene-3, have been carried out to obtain rate constants for its bimolecular reaction with acetylene, C2H2. The reaction was studied in the gas-phase over the pressure range 1-100 Tort, with SF6 as bath gas, at 5 temperatures in the range 297-553 K. The reaction showed a very slight pressure dependence at higher temperatures. The high pressure rate constants (obtained by extrapolation at the three higher temperatures) gave the Arrhenius equation: log(k(infinity)/cm(3) molecule(-1) s(-1)) (-10.94 +/- 0.05) + (6.10 +/- 0.36 kJ mol(-1))/RTln10. These Arrhenius parameters are consistent with a fast reaction occurring at approximately 30% of the collision rate at 298 K. Quantum chemical calculations (both DFT and ab initio G2//B3LYP and G2//QCISD) of the GeC2H4 potential energy surface (PES), show that GeH2 + C2H2 react initially to form germirene which can isomerise to vinylgermylene with a relatively low barrier. RRKM modelling, based on a loose association transition state, but assuming vinylgermylene is the end product (used in combination with a weak collisional deactivation model) predicts a strong pressure dependence using the calculated energies, in conflict with the experimental evidence. The detailed GeC2H4 PES shows considerable complexity with ten other accessible stable minima (B3LYP level), the three most stable of which are all germylenes. Routes through this complex surface were examined in detail. The only product combination which appears capable of satisfying the (P-3) + C2H4.C2H4 was confirmed as a product by GC observed lack of a strong pressure dependence is Ge(P-3) + C2H4. C2H4 was confirmed as a product by GC analysis. Although the formation of these products are shown to be possible by singlet-triplet curve crossing during dissociation of 1-germiranylidene (1-germacyclopropylidene), it seems more likely (on thermochernical grounds) that the triplet biradical, (GeCH2CH2.)-Ge-., is the immediate product precursor. Comparisons are made with the reaction of SiH2 with C2H2.

PIC based detection for distributed space-time block coding under imperfect synchronisation

A parallel interference cancellation (PIC) detection scheme is proposed to suppress the impact of imperfect synchronisation. By treating as interference the extra components in the received signal caused by timing misalignment, the PIC detector not only offers much improved performance but also retains a low structural and computational complexity.

Distributed space-time block coding with incremental relay: performance improvement under imperfect synchronisation

This paper addresses the impact of imperfect synchronisation on D-STBC when combined with incremental relay. To suppress such an impact, a novel detection scheme is proposed, which retains the two key features of the STBC principle: simplicity (i.e. linear computational complexity), and optimality (i.e. maximum likelihood). These two features make the new detector very suitable for low power wireless networks (e.g. sensor networks).

Distributed space-time block coding for 3 and 4 relay nodes: Imperfect synchronisation and a solution

Most research on distributed space time block coding (STBC) has so far focused on the case of 2 relay nodes and assumed that the relay nodes are perfectly synchronised at the symbol level. By applying STBC to 3-or 4-relay node systems, this paper shows that imperfect synchronisation causes significant performance degradation to the conventional detector. To this end, we propose a new STBC detection solution based on the principle of parallel interference cancellation (PIC). The PIC detector is moderate in computational complexity but is very effective in suppressing the impact of imperfect synchronisation.

Computational complexity of weighted splitting schemes on parallel computers

In models of complicated physical-chemical processes operator splitting is very often applied in order to achieve sufficient accuracy as well as efficiency of the numerical solution. The recently rediscovered weighted splitting schemes have the great advantage of being parallelizable on operator level, which allows us to reduce the computational time if parallel computers are used. In this paper, the computational times needed for the weighted splitting methods are studied in comparison with the sequential (S) splitting and the Marchuk-Strang (MSt) splitting and are illustrated by numerical experiments performed by use of simplified versions of the Danish Eulerian model (DEM).

PIC detector for distributed space-time block coding under imperfect synchronisation

A parallel interference cancellation (PIC) detection scheme is proposed to suppress the impact of imperfect synchronisation. By treating as interference the extra components in the received signal caused by timing misalignment, the PIC detector not only offers much improved performance but also retains a low structural and computational complexity.

Signal detection for orthogonal space-time block coding over time-selective fading channels: the H(i) systems

One major assumption in all orthogonal space-time block coding (O-STBC) schemes is that the channel remains static over the length of the code word. However, time-selective fading channels do exist, and in such case conventional O-STBC detectors can suffer from a large error floor in the high signal-to-noise ratio (SNR) cases. As a sequel to the authors' previous papers on this subject, this paper aims to eliminate the error floor of the H(i)-coded O-STBC system (i = 3 and 4) by employing the techniques of: 1) zero forcing (ZF) and 2) parallel interference cancellation (PIC). It is. shown that for an H(i)-coded system the PIC is a much better choice than the ZF in terms of both performance and computational complexity. Compared with the, conventional H(i) detector, the PIC detector incurs a moderately higher computational complexity, but this can well be justified by the enormous improvement.

Space-time multirate blind multiuser detection for synchronous DS/CDMA systems

This paper proposes the subspace-based space-time (ST) dual-rate blind linear detectors for synchronous DS/CDMA systems, which can be viewed as the ST extension of our previously presented purely temporal dual-rate blind linear detectors. The theoretical analyses on their performances are also carried out. Finally, the two-stage ST blind detectors are presented, which combine the adaptive purely temporal dual-rate blind MMSE filters with the non-adaptive beamformer. Their adaptive stages with parallel structure converge much faster than the corresponding adaptive ST dual-rate blind MMSE detectors, while having a comparable computational complexity to the latter.

Time diversity decorrelator (TDD); a near-far resistant detector for asynchronous CDMA system

Greater attention has been focused on the use of CDMA for future cellular mobile communications. CA near-far resistant detector for asynchronous code-division multiple-access (CDMA) systems operating in additive white Gaussian noise (AWGN) channels is presented. The multiuser interference caused by K users transmitting simultaneously, each with a specific signature sequence, is completely removed at the receiver. The complexity of this detector grows only linearly with the number of users, as compared to the optimum multiuser detector which requires exponential complexity in the number of users. A modified algorithm based on time diversity is described. It performs detection on a bit-by-bit basis and overcomes the complexity of using a sequence detector. The performance of this detector is shown to be superior to that of the conventional receiver.

Land re-use, complexity and actor-networks: a framework for research

This paper will present a conceptual framework for the examination of land redevelopment based on a complex systems/networks approach. As Alvin Toffler insightfully noted, modern scientific enquiry has become exceptionally good at splitting problems into pieces but has forgotten how to put the pieces back together. Twenty-five years after his remarks, governments and corporations faced with the requirements of sustainability are struggling to promote an ‘integrated’ or ‘holistic’ approach to tackling problems. Despite the talk, both practice and research provide few platforms that allow for ‘joined up’ thinking and action. With socio-economic phenomena, such as land redevelopment, promising prospects open up when we assume that their constituents can make up complex systems whose emergent properties are more than the sum of the parts and whose behaviour is inherently difficult to predict. A review of previous research shows that it has mainly focused on idealised, ‘mechanical’ views of property development processes that fail to recognise in full the relationships between actors, the structures created and their emergent qualities. When reality failed to live up to the expectations of these theoretical constructs then somebody had to be blamed for it: planners, developers, politicians. However, from a ‘synthetic’ point of view the agents and networks involved in property development can be seen as constituents of structures that perform complex processes. These structures interact, forming new more complex structures and networks. Redevelopment then can be conceptualised as a process of transformation: a complex system, a ‘dissipative’ structure involving developers, planners, landowners, state agencies etc., unlocks the potential of previously used sites, transforms space towards a higher order of complexity and ‘consumes’ but also ‘creates’ different forms of capital in the process. Analysis of network relations point toward the ‘dualism’ of structure and agency in these processes of system transformation and change. Insights from actor network theory can be conjoined with notions of complexity and chaos to build an understanding of the ways in which actors actively seek to shape these structures and systems, whilst at the same time are recursively shaped by them in their strategies and actions. This approach transcends the blame game and allows for inter-disciplinary inputs to be placed within a broader explanatory framework that does away with many past dichotomies. Better understanding of the interactions between actors and the emergent qualities of the networks they form can improve our comprehension of the complex socio-spatial phenomena that redevelopment comprises. The insights that this framework provides when applied in UK institutional investment into redevelopment are considered to be significant.

Higher education as a portfolio investment: students’ choices about studying, term time employment, leisure, and loans

Recent UK changes in the number of students entering higher education, and in the nature of financial support, highlight the complexity of students’ choices about human capital investments. Today’s students have to focus not on the relatively narrow issue of how much academic effort to invest, but instead on the more complicated issue of how to invest effort in pursuit of ‘employability skills’, and how to signal such acquisitions in the context of a highly competitive graduate jobs market. We propose a framework aimed specifically at students’ investment decisions, which encompasses corner solutions for both borrowing and employment while studying.

CP-OQAM-OFDM based SC-FDMA: adjustable user bandwidth and space-time coding

The discrete Fourier transmission spread OFDM DFTS-OFDM) based single-carrier frequency division multiple access (SC-FDMA) has been widely adopted due to its lower peak-to-average power ratio (PAPR) of transmit signals compared with OFDM. However, the offset modulation, which has lower PAPR than general modulation, cannot be directly applied into the existing SC-FDMA. When pulse-shaping filters are employed to further reduce the envelope fluctuation of transmit signals of SC-FDMA, the spectral efficiency degrades as well. In order to overcome such limitations of conventional SC-FDMA, this paper for the first time investigated cyclic prefixed OQAMOFDM (CP-OQAM-OFDM) based SC-FDMA transmission with adjustable user bandwidth and space-time coding. Firstly, we propose CP-OQAM-OFDM transmission with unequally-spaced subbands. We then apply it to SC-FDMA transmission and propose a SC-FDMA scheme with the following features: a) the transmit signal of each user is offset modulated single-carrier with frequency-domain pulse-shaping; b) the bandwidth of each user is adjustable; c) the spectral efficiency does not decrease with increasing roll-off factors. To combat both inter-symbolinterference and multiple access interference in frequencyselective fading channels, a joint linear minimum mean square error frequency domain equalization using a prior information with low complexity is developed. Subsequently, we construct space-time codes for the proposed SC-FDMA. Simulation results confirm the powerfulness of the proposed CP-OQAM-OFDM scheme (i.e., effective yet with low complexity).