Explore the vast range of titles available.

Information-theoretic-based measures have been useful in quantifying network complexity. Here we briefly survey and contrast (algorithmic) information-theoretic methods which have been used to characterize graphs and networks. We illustrate the strengths and limitations of Shannon’s entropy, lossless compressibility and algorithmic complexity when used to identify aspects and properties of complex networks. We review the fragility of computable measures on the one hand and the invariant properties of algorithmic measures on the other demonstrating how current approaches to algorithmic complexity are misguided and suffer of similar limitations than traditional statistical approaches such as Shannon entropy. Finally, we review some current definitions of algorithmic complexity which are used in analyzing labelled and unlabelled graphs. This analysis opens up several new opportunities to advance beyond traditional measures.

We investigate the properties of a Block Decomposition Method (BDM), which extends the power of a Coding Theorem Method (CTM) that approximates local estimations of algorithmic complexity based on Solomonoff–Levin’s theory of algorithmic probability providing a closer connection to algorithmic complexity than previous attempts based on statistical regularities such as popular lossless compression schemes. The strategy behind BDM is to find small computer programs that produce the components of a larger, decomposed object. The set of short computer programs can then be artfully arranged in sequence so as to produce the original object. We show that the method provides efficient estimations of algorithmic complexity but that it performs like Shannon entropy when it loses accuracy. We estimate errors and study the behaviour of BDM for different boundary conditions, all of which are compared and assessed in detail. The measure may be adapted for use with more multi-dimensional objects than strings, objects such as arrays and tensors. To test the measure we demonstrate the power of CTM on low algorithmic-randomness objects that are assigned maximal entropy (e.g., π ) but whose numerical approximations are closer to the theoretical low algorithmic-randomness expectation. We also test the measure on larger objects including dual, isomorphic and cospectral graphs for which we know that algorithmic randomness is low. We also release implementations of the methods in most major programming languages—Wolfram Language (Mathematica), Matlab, R, Perl, Python, Pascal, C++, and Haskell—and an online algorithmic complexity calculator.

Arguments inspired by algorithmic information theory predict an inverse relation between the probability and complexity of output patterns in a wide range of input–output maps. This phenomenon is known as simplicity bias. By viewing the parameters of dynamical systems as inputs, and the resulting (digitised) trajectories as outputs, we study simplicity bias in the logistic map, Gauss map, sine map, Bernoulli map, and tent map. We find that the logistic map, Gauss map, and sine map all exhibit simplicity bias upon sampling of map initial values and parameter values, but the Bernoulli map and tent map do not. The simplicity bias upper bound on the output pattern probability is used to make a priori predictions regarding the probability of output patterns. In some cases, the predictions are surprisingly accurate, given that almost no details of the underlying dynamical systems are assumed. More generally, we argue that studying probability–complexity relationships may be a useful tool when studying patterns in dynamical systems.

This work applies concepts from algorithmic probability to Boolean and quantum combinatorial logic circuits. The relations among the statistical, algorithmic, computational, and circuit complexities of states are reviewed. Thereafter, the probability of states in the circuit model of computation is defined. Classical and quantum gate sets are compared to select some characteristic sets. The reachability and expressibility in a space-time-bounded setting for these gate sets are enumerated and visualized. These results are studied in terms of computational resources, universality, and quantum behavior. The article suggests how applications like geometric quantum machine learning, novel quantum algorithm synthesis, and quantum artificial general intelligence can benefit by studying circuit probabilities.

Combining the study of queuing with inventory is very common and such systems are referred to as queuing-inventory systems in the literature. These systems occur naturally in practice and have been studied extensively in the literature. The inventory systems considered in the literature generally include (s,S)-type. However, in this paper we look at opportunistic-type inventory replenishment in which there is an independent point process that is used to model events that are called opportunistic for replenishing inventory. When an opportunity (to replenish) occurs, a probabilistic rule that depends on the inventory level is used to determine whether to avail it or not. Assuming that the customers arrive according to a Markovian arrival process, the demands for inventory occur in batches of varying size, the demands require random service times that are modeled using a continuous-time phase-type distribution, and the point process for the opportunistic replenishment is a Poisson process, we apply matrix-analytic methods to study two of such models. In one of the models, the customers are lost when at arrivals there is no inventory and in the other model, the customers can enter into the system even if the inventory is zero but the server has to be busy at that moment. However, the customers are lost at arrivals when the server is idle with zero inventory or at service completion epochs that leave the inventory to be zero. Illustrative numerical examples are presented, and some possible future work is highlighted.

We propose a measure based upon the fundamental theoretical concept in algorithmic information theory that provides a natural approach to the problem of evaluating n -dimensional complexity by using an n -dimensional deterministic Turing machine. The technique is interesting because it provides a natural algorithmic process for symmetry breaking generating complex n -dimensional structures from perfectly symmetric and fully deterministic computational rules producing a distribution of patterns as described by algorithmic probability. Algorithmic probability also elegantly connects the frequency of occurrence of a pattern with its algorithmic complexity, hence effectively providing estimations to the complexity of the generated patterns. Experiments to validate estimations of algorithmic complexity based on these concepts are presented, showing that the measure is stable in the face of some changes in computational formalism and that results are in agreement with the results obtained using lossless compression algorithms when both methods overlap in their range of applicability. We then use the output frequency of the set of 2-dimensional Turing machines to classify the algorithmic complexity of the space-time evolutions of Elementary Cellular Automata.

We consider queueing-inventory models in which customers arrive according to a point process and each customer demands for one or more items but not exceeding a predetermined (finite) value, say, N. The demands of the customers require positive service times. Replenishments are based on (s, S)-type policy and the lead times are assumed to be random. We consider two models. In Model 1, any arriving customer finding the inventory level to be zero will be lost. In Model 2, the loss of customers occur in two ways. First, an arriving customer finding the inventory level to be zero with the server being idle will be lost, and secondly, the customers, if any, present at a service completion with zero inventory will all be lost. We assume that in both the models the demands may be met partially based on the requests and the available inventory levels at that time. The inventory level is reduced by the amount to meet (fully or partially) the requisite demand of the customer at the beginning of the service. Under the assumption that all underlying random variables are exponential, we perform the steady-state analysis of the models using the classical matrix-analytic methods. Illustrative examples comparing the two models are presented.

In this paper, we study an MAP/M/∞ queue associated with an inventory system. The inventory is replenished according to an (s, S)-policy. The (self) service and lead times are assumed to be exponentially distributed. No arriving customer is allowed to enter into the system (of infinite capacity) when there is no inventory available for servicing the customer. Thus, every customer in service is attached with an inventory at the time of entering into the system. We employ an algorithmic approach for the computation of various quantities of interest and derive some explicit expressions in some cases. An illustrative example and an optimization problem are presented.

We introduce a definition of algorithmic symmetry in the context of geometric and spatial complexity able to capture mathematical aspects of different objects using as a case study polyominoes and polyhedral graphs. We review, study and apply a method for approximating the algorithmic complexity (also known as Kolmogorov–Chaitin complexity) of graphs and networks based on the concept of Algorithmic Probability (AP). AP is a concept (and method) capable of recursively enumerate all properties of computable (causal) nature beyond statistical regularities. We explore the connections of algorithmic complexity—both theoretical and numerical—with geometric properties mainly symmetry and topology from an (algorithmic) information-theoretic perspective. We show that approximations to algorithmic complexity by lossless compression and an Algorithmic Probability-based method can characterize spatial, geometric, symmetric and topological properties of mathematical objects and graphs.

The complexity of solar radiation fluctuations received on the ground is nowadays of great interest for solar resource in the context of climate change and sustainable development. Over tropical maritime area, there are small inhabited islands for which the prediction of the solar resource at the daily and infra-daily time scales are important to optimize their solar energy systems. Recently, studies show that the theory of the information is a promising way to measure the solar radiation intermittency. Kolmogorov complexity (KC) is a useful tool to address the question of predictability. Nevertheless, this method is inaccurate for small time series size. To overcome this drawback, a new encoding scheme is suggested for converting hourly solar radiation time series values into a binary string for calculation of Kolmogorov complexity (KC-ES). To assess this new approach, we tested this method using the 2004–2006 satellite hourly solar data for the western part of the Indian Ocean. The results were compared with the algorithmic probability (AP) method which is used as the benchmark method to compute the complexity for short string. These two methods are a new approach to compute the complexity of short solar radiation time series. We show that KC-ES and AP methods give comparable results which are in agreement with the physical variability of solar radiation. During the 2004–2006 period, an important interannual SST (sea surface temperature) anomaly over the south of Mozambique Channel encounters in 2005, a strong MJO (Madden–Julian oscillation) took place in May 2005 over the equatorial Indian Ocean, and nine tropical cyclones crossed the western part of the Indian Ocean in 2004–2005 and 2005–2006 austral summer. We have computed KC-ES of the solar radiation time series for these three events. The results show that the Kolmogorov complexity with suggested encoding scheme (KC-ES) gives competitive measure of complexity in regard to the AP method also known as Solomonoff probability.