Most of the past research on the problem of deadlock avoidance for complex resource allocation systems (RAS) has acknowledged the fact that the computation of the maximally permissive (optimal) deadlock avoidance policy (DAP) possesses super-polynomial complexity for most RAS classes, and therefore, it has resorted to solutions that trade off maximal permissiveness for computational tractability. In this work, we distinguish between the off-line and the on-line computation that is required for the effective implementation of the maximally permissive DAP, and we seek to develop representations of this policy that will require minimal on-line computation. The particular representation that we adopt is that of a compact classifier that will effect the underlying dichotomy of the reachable state space into safe and unsafe subspaces. Through a series of reductions of the derived classification problem, we are also able to attain extensive reductions in the computational complexity of the off-line task of the construction of the sought classifier. In a first study of the aforementioned problem, we restrict our attention to a particular RAS class that is motivated by an ongoing project called Gadara. This particular RAS class accepts the separation of the safe and unsafe subspaces of its instantiations through a set of linear inequalities. We propose design procedures that will construct a classifier employing the minimum possible number of linear inequalities, and we formally establish their "completeness", i.e., their ability to provide an effective classifier for every instance of the considered RAS class. We also offer heuristics that, if necessary, can alleviate the computational effort that is necessary for the construction of the sought classifier. We extend the aforementioned results to encompass more general RAS classes, where the sought dichotomy might not be represented by a set of linear inequalities. To this end, we propose new parametric and non-parametric classification schemes for this more complex case, and establish formally their completeness. We also provide effective and computationally efficient procedures for the synthesis of the sought classifiers. A bottleneck in the developments described above is defined by the fact that they presuppose the availability of the enumerations of the RAS safe and unsafe subspaces. To address this obstacle, we propose a novel approach for the deployment of the maximally permissive DAP for RAS, that is based on the identification and the efficient storage of a critical subset of states of the underlying RAS state space. In particular, the proposed algorithm provides those critical states, while avoiding the complete enumeration of the RAS state space. Furthermore, we extend the existing theory on maximally permissive deadlock avoidance, so that it can handle RAS with reader/writer (R/W) locks. A key challenge that is posed by this new RAS class stems from the fact that the underlying state space is not necessarily finite. We effectively address this obstacle by taking advantage of special structure that exists in the set of unsafe states and enables a finite representation of this set through its minimal elements. Finally, we would like to mention that numerical experimentation demonstrates the efficacy of the proposed approaches, and establishes their ability to support the deployment of maximally permissive DAP for RAS with very large structure and state spaces. To the best of our knowledge, these experiments also establish the ability of the proposed methodology to effectively compute tractable implementations of the maximally permissive DAP for problem instances significantly beyond the capacity of any other approach currently available in the literature. Moreover, this is the first work to address the RAS with R/W locks.

In pursuance of decreasing costs, both the client and the contractor would strive to speed up the construction project. However, accelerating the project schedule will impose additional cost and might be profitable up to a certain limit. Paramount for construction management, analyses of this trade-off between duration and cost is hailed as the time-cost trade-off (TCT) optimization. Inadequacies of existing commercial software packages for such analyses tied with eminence of discretization, motivated development of different paradigms of particle swarm optimizers (PSO) for three extensions of discrete TCT problems (DTCTPs). A sole-PSO algorithm for concomitant minimization of time and cost is proposed which involves minimal adjustments to shift focus to the completion deadline problem. A hybrid model is also developed to unravel the time-cost curve extension of DCTCPs. Engaging novel principles for evaluation of cost-slopes, and pbest/gbest positions, the hybrid SAM-PSO model combines complementary strengths of overhauled versions of the Siemens Approximation Method (SAM) and the PSO algorithm. Effectiveness and efficiency of the proposed algorithms are validated employing instances derived from the literature. Throughout computational experiments, mixed integer programming technique is implemented to introduce the optimal non-dominated fronts of two specific benchmark problems for the very first time in the literature. Another chief contribution of this thesis can be depicted as potency of SAM-PSO model in locating the entire Pareto fronts of the practiced instances, within acceptable time-frames with reasonable deviations from the optima. Possible further improvements and applications of SAM-PSO model are suggested in the conclusion.

Given the result $v_0$ of a survey and a nested collection of summary statistics that could be used to describe that result, it is natural to ask which of these summary statistics best describe $v_0$. In 1998 Diaconis and Sturmfels presented an approach for determining the conditional significance of a higher order statistic, after sampling a space conditioned on the value of a lower order statistic. Their approach involves the computation of a Markov basis, followed by the use of a Markov process with stationary hypergeometric distribution to generate a sample.This technique for data analysis has become an accepted tool of algebraic statistics, particularly for the study of fully ranked data. In this thesis, we explore the extension of this technique for data analysis to the study of partially ranked data, focusing on data from surveys in which participants are asked to identify their top $k$ choices of $n$ items. Before we move on to our own data analysis, though, we present a thorough discussion of the Diaconis–Sturmfels algorithm and its use in data analysis. In this discussion, we attempt to collect together all of the background on Markov bases, Markov proceses, Gröbner bases, implicitization theory, and elimination theory, that is necessary for a full understanding of this approach to data analysis.

Data distribution management (DDM) is a mechanism to interconnect data producers and data consumers in a distributed application. Data producers provide useful data to consumers in the form of messages. For each message produced, DDM determines the set of data consumers interested in receiving the message and delivers it to those consumers. We are particularly interested in DDM techniques for parallel and distributed discrete event simulations. Thus far, researchers have treated synchronization of events (i.e. time management) and DDM independent of each other. This research focuses on how to realize time managed DDM mechanisms. The main reason for time-managed DDM is to ensure that changes in the routing of messages from producers to consumers occur in a correct sequence. Also time managed DDM avoids non-determinism in the federation execution, which may result in non-repeatable executions. An optimistic approach to time managed DDM is proposed where one allows DDM events to be processed out of time stamp order, but a detection and recovery procedure is used to recover from such errors. These mechanisms are tailored to the semantics of the DDM operations to ensure an efficient realization. A correctness proof is presented to verify the algorithm correctly synchronizes DDM events. We have developed a fully distributed implementation of the algorithm within the framework of the Georgia Tech Federated Simulation Development Kit (FDK) software. A performance evaluation of the synchronized DDM mechanism has been completed in a loosely coupled distributed system consisting of a network of workstations connected over a local area network (LAN). We compare time-managed versus unsynchronized DDM for two applications that exercise different mobility patterns: one based on a military simulation and a second utilizing a synthetic workload. The experiments and analysis illustrate that synchronized DDM performance depends on several factors: the simulations model (e.g. lookahead), applications mobility patterns and the network hardware (e.g. size of network buffers). Under certain mobility patterns, time-managed DDM is as efficient as unsynchronized DDM. There are also mobility patterns where time-managed DDM overheads become significant, and we show how they can be reduced.

Information-theoretic arguments focus on modeling the reliability of information transmission, assuming availability of infinite data at sources, thus ignoring randomness in message generation times at the respective sources. However, in information transport networks, not only is reliable transmission important, but also stability, i.e., finiteness of mean delay in- curred by messages from the time of generation to the time of successful reception. Usually, delay analysis is done separately using queueing-theoretic arguments, whereas reliable information transmission is studied using information theory. In this thesis, we investigate these two important aspects of data communication jointly by suitably combining models from these two fields. In particular, we model scheduled communication of messages , that arrive in a random process, (i) over multiaccess channels, with either independent decoding or joint decoding, and (ii) over degraded broadcast channels. The scheduling policies proposed permit up to a certain maximum number of messages for simultaneous transmission. In the first part of the thesis, we develop a multi-class discrete-time processor-sharing queueing model, and then investigate the stability of this queue. In particular, we model the queue by a discrete-time Markov chain defined on a countable state space, and then establish (i) a sufficient condition for c-regularity of the chain, and hence positive recurrence and finiteness of stationary mean of the function c of the state, and (ii) a sufficient condition for transience of the chain. These stability results form the basis for the conclusions drawn in the thesis. The second part of the thesis is on multiaccess communication with random message arrivals. In the context of independent decoding, we assume that messages can be classified into a fixed number of classes, each of which specifies a combination of received signal power, message length, and target probability of decoding error. Each message is encoded independently and decoded independently. In the context of joint decoding, we assume that messages can be classified into a fixed number of classes, each of which specifies a message length, and for each of which there is a message queue. From each queue, some number of messages are encoded jointly, and received at a signal power corresponding to the queue. The messages are decoded jointly across all queues with a target probability of joint decoding error. For both independent decoding and joint decoding, we derive respective discrete- time multiclass processor-sharing queueing models assuming the corresponding information-theoretic models for the underlying communication process. Then, for both the decoding schemes, we (i) derive respective outer bounds to the stability region of message arrival rate vectors achievable by the class of stationary scheduling policies, (ii) show for any mes- sage arrival rate vector that satisfies the outer bound, that there exists a stationary “state-independent” policy that results in a stable system for the corresponding message arrival process, and (iii) show that the stability region of information arrival rate vectors, in the limit of large message lengths, equals an appropriate information-theoretic capacity region for independent decoding, and equals the information-theoretic capacity region for joint de-coding. For independent decoding, we identify a class of stationary scheduling policies, for which we show that the stability region in the limit of large maximum number of simultane-ous transmissions is independent of the received signal powers, and each of which achieves a spectral efficiency of 1 nat/s/Hz in the limit of large message lengths. In the third and last part of the thesis, we show that the queueing model developed for multiaccess channels with joint decoding can be used to model communication over degraded broadcast channels, with superposition encoding and successive decoding across all queues. We then show respective results (i), (ii), and (iii), stated above.

Since 1997, fully noncontributory minimum pensions have been established in many Latin American countries, and have more recently been encouraged as a "zero pillar" of social security by the World Bank and other IFIs. These policies came into being under diverse political regimes and display a range of levels of generosity and universality. Becuase these policies are generally part of a modern bureaucratic welfare state project, they require identity documents, something that many low-income citizens do not possess. States have lowered barriers to the supply of identity documents, and new social policies, like noncontributory pensions and conditional or unconditional cash transfers, have stimulated demand for identity documents among those who do not currently have them. Brazils noncontributory pension, the BPC, has a means test and a large benefit (equivalent to the minimum wage), but requires providing identity documents for all household members. This report discusses the propagation of noncontributory pensions, then examines Brazilian government records to determine the size of the incentive to demand documents in Brazil using a logit model and a more novel survival time regression discontinuity design, raising questions of the relationships between benefit size, universality, document requirements, and poverty. / text

Στην παρούσα εργασία εξετάζεται, αριθμητικά και αναλυτικά (όπου αυτό είναι εφικτό), η συμπεριφορά ενός 2-διάστατου διακριτού συστήματος, το οποίο συνθέτουν ένας γραμμικός πίνακας και ένα διάνυσμα ασυνέχειας. Παρόλη την απλότητα της έκφρασής του, η συμπεριφορά του χαρακτηρίζεται από ποικιλομορφία και πολυπλοκότητα. Αλλοιώνοντας το αρχικό αυτό σύστημα, με την παρουσία μιας παραμέτρου διαταραχής (όπως την ονομάζουμε), και στη συνέχεια φράσσοντας τις τιμές του με modulo, παράγουμε δύο συγγενή συστήματα με έντονα πολύπλοκη και απεριοδική συμπεριφορά. Οι απεριοδικές αλληλουχίες τιμών που παράγονται με αυτόν τον τρόπο δύνανται να μετατραπούν (μέσω διαφόρων κατάλληλων κωδικοποιήσεων) σε αποτελεσματικούς κρυπτογραφικούς κλειδάριθμους. / In this paper, we present an application of the theory of symbolic dynamics to a class of discrete dynamical systems of interest to cryptography, which are composed of a linear part and a discontinuity. The irregular behavior of such systems is studied, in the sense of the existence of non-periodic orbits in certain areas of the configuration space. Some theorems are stated and proved, concerning the correspondence of such orbits with an infinite set of non-periodic symbolic series of infinite length. A specific dynamical system is used as an example, illustrating the remarkable patterns displayed by the dynamics of this class of systems. Keywords: Uncountably infinite, non-periodic symbolic series, disk of influence, eventually periodic orbit, pre-orbit point.

In this thesis, the discrete time risk model with inhomogeneous claims is considered. This model is used for describing the insurer‘s capital and its components: initial capital, premiums received, and claims paid. The main risk measures, ruin probabilities and Gerber-Shiu function, are investigated and recursive formulas are obtained. These formulas give fast and accurate evaluation of the finite time ruin probabilities and Gerber-Shiu function. However, the infinite time investigations require that the Gerber-Shiu function's values for the initial capital equal to 0 must be known. This is slightly more difficult due to the claim inhomogeneity and for this reason a theorem with explicit expression of the infinite time Gerber-Shiu function for a zero initial capital is proposed. However, for the calculation of the infinite time values, some assumption about underlying claim structure must be made. As a solution the cyclically distributed claims are proposed, the algorithms for application of the theorems are given and numerical examples with graphical output are presented. Finally, a special case of discrete time risk model with inhomogeneous claims distributed according geometric law is investigated. In addition to the main results, another discrete time risk model with inhomogeneous claims acquiring rational values is investigated. Two theorems for evaluation of the finite time ruin probabilities are proved and some examples are presented. / Disertaciniame darbe nagrinėjamas diskretaus laiko rizikos modelis su skirtingai pasiskirsčiusiomis žalomis. Šis modelis aprašo draudimo įmonės turtą įtakojančius veiksnius: pradinį kapitalą, gaunamas įmokas, išmokamas žalas. Išvedamos rekursinės formulės, kurių pagalba galima tiksliai ir greitai rasti baigtinio laiko bankroto tikimybių ir Gerber-Shiu funkcijos vertes. Rekursinės formulės taip pat pateikiamos ir begalinio laiko rizikos matams, tačiau nevienodai pasiskirsčiusių žalų atveju iškyla papildomų sunkumų randant bankroto tikimybę ir Gerber-Shiu funkciją, kai pradinis kapitalas lygus 0. Tam įrodoma atskira teorema, tačiau nedarant jokių prielaidų apie žalų pasiskirstymus, apskaičiuoti vertes lengva tikrai nėra. Kaip išeitis pasiūloma cikliškai pasiskirsčiusių žalų struktūra ir pateikiami algoritmai, leidžiantys teoremas pritaikyti praktiškai. Demonstruojant teoremų ir rekursinių formulių veikimą, pateikiami skaitiniai pavyzdžiai su grafinėmis iliustracijomis bei programų kodai. Galiausiai nagrinėjamas atskiras diskretaus laiko rizikos modelio atvejis, kai žalos pasiskirsčiusios skirtingai pagal geometrinį dėsnį. Disertacijoje taip pat yra nagrinėjamas diskretaus laiko rizikos modelis su skirtingai pasiskirsčiusiomis žalomis, kurios įgyja racionalias reikšmes, bei kintančiomis įmokomis ir pradiniu kapitalu, taip pat įgyjančiais racionalias reikšmes su tam tikra sąlyga. Įrodomos dvi teoremos kaip rasti tokio modelio baigtinio laiko bankroto tikimybę ir keli... [toliau žr. visą tekstą]

Disertaciniame darbe nagrinėjamas diskretaus laiko rizikos modelis su skirtingai pasiskirsčiusiomis žalomis. Šis modelis aprašo draudimo įmonės turtą įtakojančius veiksnius: pradinį kapitalą, gaunamas įmokas, išmokamas žalas. Išvedamos rekursinės formulės, kurių pagalba galima tiksliai ir greitai rasti baigtinio laiko bankroto tikimybių ir Gerber-Shiu funkcijos vertes. Rekursinės formulės taip pat pateikiamos ir begalinio laiko rizikos matams, tačiau nevienodai pasiskirsčiusių žalų atveju iškyla papildomų sunkumų randant bankroto tikimybę ir Gerber-Shiu funkciją, kai pradinis kapitalas lygus 0. Tam įrodoma atskira teorema, tačiau nedarant jokių prielaidų apie žalų pasiskirstymus, apskaičiuoti vertes lengva tikrai nėra. Kaip išeitis pasiūloma cikliškai pasiskirsčiusių žalų struktūra ir pateikiami algoritmai, leidžiantys teoremas pritaikyti praktiškai. Demonstruojant teoremų ir rekursinių formulių veikimą, pateikiami skaitiniai pavyzdžiai su grafinėmis iliustracijomis bei programų kodai. Galiausiai nagrinėjamas atskiras diskretaus laiko rizikos modelio atvejis, kai žalos pasiskirsčiusios skirtingai pagal geometrinį dėsnį. Disertacijoje taip pat yra nagrinėjamas diskretaus laiko rizikos modelis su skirtingai pasiskirsčiusiomis žalomis, kurios įgyja racionalias reikšmes, bei kintančiomis įmokomis ir pradiniu kapitalu, taip pat įgyjančiais racionalias reikšmes su tam tikra sąlyga. Įrodomos dvi teoremos kaip rasti tokio modelio baigtinio laiko bankroto tikimybę ir keli... [toliau žr. visą tekstą] / In this thesis, the discrete time risk model with inhomogeneous claims is considered. This model is used for describing the insurer‘s capital and its components: initial capital, premiums received, and claims paid. The main risk measures, ruin probabilities and Gerber-Shiu function, are investigated and recursive formulas are obtained. These formulas give fast and accurate evaluation of the finite time ruin probabilities and Gerber-Shiu function. However, the infinite time investigations require that the Gerber-Shiu function's values for the initial capital equal to 0 must be known. This is slightly more difficult due to the claim inhomogeneity and for this reason a theorem with explicit expression of the infinite time Gerber-Shiu function for a zero initial capital is proposed. However, for the calculation of the infinite time values, some assumption about underlying claim structure must be made. As a solution the cyclically distributed claims are proposed, the algorithms for application of the theorems are given and numerical examples with graphical output are presented. Finally, a special case of discrete time risk model with inhomogeneous claims distributed according geometric law is investigated. In addition to the main results, another discrete time risk model with inhomogeneous claims acquiring rational values is investigated. Two theorems for evaluation of the finite time ruin probabilities are proved and some examples are presented.

After reviewing some properties of the two dimensional hyperbolic toral automorphism called Arnold's discrete cat map, including its generalizations with matrices having positive unit determinant, this thesis contains a definition of a novel cat map where the elements of the matrix are found in the sequence of Pell numbers. This mapping is therefore denoted as Pell's cat map. The main result of this thesis is a theorem determining the upper bound for the minimal period of Pell's cat map. From numerical results four conjectures regarding properties of Pell's cat map are also stated. A brief exposition of some applications of Arnold's discrete cat map is found in the last part of the thesis.