Search

We consider the problem of finding the largest clique of a graph. This is an NP-hard problem and no exact algorithm to solve it exactly in polynomial time is known to exist. Several heuristic approaches have been proposed to find approximate solutions. Markov Chain Monte Carlo is one of these. In the context of Markov Chain Monte Carlo, we present a class of "parallel dynamics", known as Probabilistic Cellular Automata, which can be used in place of the more standard choice of sequential "single spin flip" to sample from a probability distribution concentrated on the largest cliques of the graph. We perform a numerical comparison between the two classes of chains both in terms of the quality of the solution and in terms of computational time. We show that the parallel dynamics are considerably faster than the sequential ones while providing solutions of comparable quality. [ABSTRACT FROM AUTHOR]

This paper introduces the INFLUTRUST framework that is designed to address challenges in trust-based influencer marketing campaigns on Online Social Networks (OSNs). The INFLUTRUST framework enables the influencers to autonomously select products across the OSN platforms for advertisement by employing a reinforcement learning algorithm. The Stochastic Learning Automata reinforcement algorithm considers the OSN platforms' provided monetary rewards, the influencers' advertising profit, and the influencers' trust levels towards the OSN platforms to enable the influencers to autonomously select an OSN platform. The trust model for the influencers incorporates direct and indirect trust, which are derived from past interactions and social ties among the influencers and the OSN platforms, respectively. The OSN platforms allocate rewards through a multilateral bargaining model that supports competition among the influencers. Simulation-based results validate the INFLUTRUST framework's effectiveness across diverse scenarios, with the scalability analysis demonstrating its robustness. Comparative evaluations highlight the INFLUTRUST framework's superiority in considering trust levels and reward allocation fairness, benefiting both the influencers and the OSN platforms. [ABSTRACT FROM AUTHOR]

In text classifier models, the complexity of recurrent neural networks (RNNs) is very high because of the vast state space and uncertainty of transitions, which makes the RNN classifier's explainability insufficient. It is almost impossible to explain the large-scale RNN directly. A feasible method is to generalize the rules undermining it, that is, model abstraction. To deal with the low efficiency and excessive information loss in existing model abstraction for RNNs, this work proposes a PSO (Particle Swarm Optimization)-based model abstraction and explanation generation method for RNNs. Firstly, the k-means clustering is applied to preliminarily partition the RNN decision process state. Secondly, a frequency prefix tree is constructed based on the traces, and a PSO algorithm is designed to implement state merging to address the problem of vast state space. Then, a PFA (probabilistic finite automata) is constructed to explain the RNN structure with preserving the origin RNN information as much as possible. Finally, the quantitative keywords are labeled as an explanation for classification results, which are automatically generated with the abstract model PFA. We demonstrate the feasibility and effectiveness of the proposed method in some cases. [ABSTRACT FROM AUTHOR]

According to the principles of compositional verification, verifying that lower-level components satisfy their specification ensures that the whole system satisfies its top-level specification. The key step is to ensure that the lower-level specifications constitute a correct decomposition of the top-level specification. In a non-stochastic context, such decomposition can be analyzed using techniques of theorem proving. In industrial applications, especially in safety-critical systems, specifications are often of stochastic nature, for example, giving a bound on the probability that a system failure will occur before a given time. A decomposition of such a specification requires techniques beyond traditional theorem proving. The first contribution of the paper is a theoretical framework that allows the representation of, and reasoning about, stochastic and timed behavior of systems as well as specifications for such behavior. The framework is based on traces that describe the continuous-time evolution of a system, and specifications are formulated using timed automata combined with probabilistic acceptance conditions. The second contribution is a novel approach to verifying decompositions of such specifications by reducing the problem to checking emptiness of the solution space for a system of linear inequalities. [ABSTRACT FROM AUTHOR]

The goal of this paper it to explore the possibility to simplify a stochastic complex dynamical system by reducing the number of its degrees of freedom, through a coarse graining procedure. Our objective is to create reduced systems which requires less computational burden to control. In other words, the question is whether one can act on the simplified system to control its evolution towards a given target, so that the same strategy also applies to the full system. We analyze this problem in three stages. First we consider the general case of coarse-graining 1D cellular automata. We show that the procedure is expected to produce extra stochasticity in the system, while still retaining some characteristics of the original system. In a second step, we study a 1D voter model for which the coarse-graining procedure requires component weighting, with weights based on causal paths. Finally, in a third part, we consider the same voter model on a scale-free graph, and perform a reduction according to a partition of the graph in communities. The equivalence between the reduced and full systems, whether controlled or not, is investigated through a delayed mutual information analysis, a concept from information theory. [ABSTRACT FROM AUTHOR]

Employee behavior exhibits diversity at different times and environments, with obvious characteristics of complex systems. Cellular automata (CA) is a mathematical model with discrete time, space, and state, suitable for complex dynamic system problems that are difficult to quantitatively describe mathematically. This article has established a model based on random CA simulation of employee behavior, calibrated parameters such as cell state and moving steps, and designed cell transfer rules. This article conducted experiments on two organizational structures: single employee enterprises and mixed employee enterprises. The experimental results indicated that the cohesion of employees who adopted reverse incentives before positive incentives in management organizations was greater than that of employees who adopted consistently positive incentives. When the number of iterations was 12, the cohesion of group a of mixed employees reached its peak. As t increased, influenced by surrounding neighbors, loyalty Y2 decreased and eventually reached a stable value, which was greater than the value of Y2 of group b. The simulation results indicated that CA is suitable for practical applications and provides assistance for decision-makers in human resource management. [ABSTRACT FROM AUTHOR]

Propagation models of flow-like landslides can be calibrated by comparing on-site evidence of past occurrences with the propagation paths and the deposition zones resulting from numerical simulations of the phenomena. Most typically, the performance of these models is evaluated considering the events independently from one another and, heuristically, i.e., subjectively assessing the fit between numerical results and available on-site data. At regional scale, however, storms often trigger, within a given area, multiple landslides of the flow type that occur more or less simultaneously. At this scale, a procedure that objectively quantifies the success, or the errors, of the numerical simulations of multiple landslides is lacking. In this study, such a quantitative calibration procedure is proposed, and assessed, considering the debris flows that occurred in Sarno in 1998 (Italy). The numerical model used is called Debris Flow Predictor (DFP), which is able to simulate the propagation paths and the accumulation depths of multiple debris flows, at regional scale, from a series of predefined triggering areas. The model employs a cellular automata method with a probabilistic behavioral rule, which is a function of the adopted digital elevation model and a series of parameters related to the erosional, the depositional, and the spreading capacity of the propagating soil mass. The numerical simulations were evaluated over the study area considering the entire set of debris flow events, as well as the individual debris flows, following a preliminary discretization of both the mapped footprints and the remaining portion of the territory. The relative and total operator characteristic curves, in addition to 6 indicators derived from a confusion matrix, have been used to quantify the performance of the simulations. The results show that the quantitative evaluation of the numerical results is essential to properly calibrate the adopted model, i.e., to discriminate among different simulations arising from different sets of model parameters. [ABSTRACT FROM AUTHOR]

Insect biological control agents may be released in relatively few locations; thus, the rate of spread is critical to predicting the spatial distribution of the agent.Exotic dung beetles have been introduced into Australia since the 1960s to bury dung, reduce bush fly populations, increase pasture productivity and improve livestock health.We use a stochastic cellular automata model to predict the historical occupancy and abundance of introduced dung beetles in the South West agricultural region of Western Australia. The model predicts the spread of four species of dung beetles in six‐month time steps for 10 years following initial release. Our model includes release locations, species‐specific ecological parameters, dung resource availability and weather variables.The average rate of spread varied between species from a high of ca. 79 km/year (Euoniticellus intermedius) to a low of 28 km/year (Onthophagus taurus). Thus, after 10 years, the area of spread varied between 99,175 and 34,175 km2 and abundance varied from 88,100 to 4,189 beetles/km2.These findings provide an estimate of the spread patterns of dung beetles. The model can be used to guide future dung beetle release programmes in Australia and elsewhere. [ABSTRACT FROM AUTHOR]

Background and Objectives: The detection of community in networks is an important tool for revealing hidden data in network analysis. One of the signs that the community exists in the network is the neighborhood density between nodes. Also, the existence of a concept called a motif indicates that a community with a high edge density has a correlation between nodes that goes beyond their close neighbors. Motifs are repetitive edge patterns that are frequently seen in the network. Methods: By estimating the triangular motif in the network, our proposed probabilistic motif-based community detection model (PMCD) helps to find the communities in the network. The idea of the proposed model is network analysis based on structural density between nodes and detecting communities by estimating motifs using probabilistic methods. Results: The suggested model's output is the strength of each node's affiliation to the communities and detecting overlaps in communities. To evaluate the performance and accuracy of the proposed method, experiments are done on real-world and synthetic networks. The findings show that, compared to other algorithms, the proposed method is acting more accurately and densely in detecting communities. Conclusion: The advantage of PMCD in using the probabilistic generative model is speeding up the computation of the hidden parameters and establishing the community based on the likelihood of triangular motifs. In fact, the proposed method proves there is a probabilistic correlation between the observation of two node pairs in different communities and the increased existence of motif structure in the network. [ABSTRACT FROM AUTHOR]

In the realm of data protection strategies, differential privacy ensures that unauthorized entities cannot reconstruct original data from system outputs. This study explores discrete event systems, specifically through probabilistic automata. Central is the protection of state data, particularly the initial state privacy of multiple starting states. We introduce an evaluation criterion to safeguard initial states. Using advanced algorithms, the proposed method counters the probabilistic identification of any state within this collection by adversaries from observed data points. The efficacy is confirmed when the probability distributions of data observations tied to these states converge. If a system's architecture does not meet state differential privacy demands, we propose an enhanced supervisory control mechanism. This control upholds state differential privacy across all initial states, maintaining operational flexibility within the probabilistic automaton framework. Concluding, a numerical analysis validates the approach's strength in probabilistic automata and discrete event systems. [ABSTRACT FROM AUTHOR]

The self-adaptive multi-agent system requires adaptive adjustments based on the dynamic environment during its runtime. Heterogeneous agent can accomplish different task goals, enhance the efficiency of system operation, but its complex collaboration problem poses new challenges to the study of verification of adaptive policies for heterogeneous multi-agents. This paper proposes a runtime verification method for self-adaptive multi-agent systems using probabilistic timed automata. The method constructs a probabilistic timed automaton model by formally describing the functional characteristics of heterogeneous agents and integrating random factors in the environment to simulate the operation process of the self-adaptive multi-agent system. Regarding the collaboration logic among heterogeneous agents, security constraints are established to ensure the security of state transition processes during system operation. Combining model checking with runtime quantitative verification methods to conduct experiment and applying it in the case of an intelligent unmanned parking system. Experimental results manifest the correctness of the cooperation logic between agents can effectively ensure the stability of the system at runtime. Significant improvement in system uptime and efficiency compared to the initial system without runtime quantitative validation. [ABSTRACT FROM AUTHOR]

The multi-agent self-adaptive system requires adaptive adjustments based on the dynamic environment during its runtime. Heterogeneous agents can enhance the efficiency of agent utilization and reduce system construction costs, but also present complex collaboration issues. Therefore, this paper proposes a runtime verification method for heterogeneous multi-agent self-adaptive systems based on probabilistic timed automata. The approach constructs a probabilistic timed automaton model by formally describing the functional characteristics of heterogeneous agents and integrating random factors in the environment to simulate the operation process of the self-adaptive system. Regarding the collaboration logic among heterogeneous agents, establishing security constraints to ensure the security of state transition processes during system operation. Combining model checking with runtime quantitative verification methods to conduct experiment and applying it in the case of an intelligent unmanned parking system. Experimental results show that the correctness of the cooperation logic between agents can effectively ensure the stability of the system at runtime, and compared with the initial system without runtime quantitative verification, the uptime of the system is increased by about 21% at the same time. [ABSTRACT FROM AUTHOR]

Probabilistic pushdown automata (pPDA) are a standard operational model for programming languages involving discrete random choices and recursive procedures. Temporal properties are useful for specifying the chronological order of events during program execution. Existing approaches for model checking pPDA against temporal properties have focused mostly on 1-regular and LTL properties. In this paper, we give decidability and complexity results for the model checking problem of pPDA against 1-visibly pushdown languages that can be described by specification logics such as CaRet. These logical formulae allow specifying properties that explicitly take the structured computations arising from procedural programs into account. For example, CaRet is able to match procedure calls with their corresponding future returns, and thus allows to express fundamental program properties such as total and partial correctness. [ABSTRACT FROM AUTHOR]

Stochastic hybrid automata (SHA) are a powerful tool to evaluate the dependability and safety of critical infrastructures. However, the resolution of nondeterminism, which is present in many purely hybrid models, is often only implicitly considered in SHA. This article instead proposes algorithms for computing maximum and minimum reachability probabilities for singular automata with urgent transitions and random clocks that follow arbitrary continuous probability distributions. We borrow a well-known approach from hybrid systems reachability analysis, namely flowpipe construction, which is then extended to optimize nondeterminism in the presence of random variables. First, valuations of random clocks that ensure reachability of specific goal states are extracted from the computed flowpipes, and second, reachability probabilities are computed by integrating over these valuations. We compute maximum and minimum probabilities for history-dependent prophetic and non-prophetic schedulers using set-based methods. The implementation featuring the library HyPro and the complexity of the approach are discussed in detail. Two case studies featuring nondeterministic choices show the feasibility of the approach. [ABSTRACT FROM AUTHOR]

Summary: Collaborative and autonomous driving vehicles combine hardware and software complex processes, also are heavily dependent on and influenced by the world of physical and cyber interactions. They have enabled many new features and advanced functionalities, such as stochastic and hybrid natures, mobile spatial topologies, and time‐critical dependability. However, the existing modeling and verification techniques have not established faith in proving correctness and safety. Spatial and time collision avoidance remains crucial obstacles on the path to becoming ubiquitous and dependable. In order to ensure safety, we first design an accident prediction architecture in system design‐time and run‐time stages. We apply it on collaborative and autonomous overtaking systems involving spatial‐ and time‐critical accident predictions. Then, we develop a novel and dedicated spatio‐clock stochastic specification language (SCSSL) to describe safety invariants and guards in domain‐specific autonomous driving systems. Next, we create the spatio‐clock stochastic and hybrid automata models based on SCSSL in order to model inherently stochastic and hybrid behaviors. To illustrate the effectiveness of spatio‐clock consistency stochastic specification and verification, we adopt statistical model checking natively to provide reliable predictions for the incoming collision instants and positions. Finally, we present an illustrative overtaking case study to verify spatio‐clock stochastic and hybrid related properties and ensure correct modeling, and demonstrate the significance of our proposed approach. [ABSTRACT FROM AUTHOR]

The objective is to find a Cellular Automata (CA) rule that can generate "loop patterns". A loop pattern is given by ones on a zero background showing loops. In order to find out how loop patterns can be locally defined, tentative loop patterns are generated by a genetic algorithm in a preliminary stage. A set of local matching tiles is designed and checked whether they can produce the aimed loop patterns by the genetic algorithm. After having approved a certain set of tiles, a probabilistic CA rule is designed in a methodical way. Templates are derived from the tiles, which then are used in the CA rule for matching. In order to drive the evolution to the desired patterns, noise is injected if the templates do not match or other constraints are not fulfilled. Simulations illustrate that loops and connected loops can be evolved by the CA rule. [ABSTRACT FROM AUTHOR]

This paper introduces the affinity classification problem, which is a generalization of the density classification problem. To solve this problem, we introduce temporally stochastic cellular automata where two rules are stochastically applied in each step on all cells of the automata. Our model is defined on a two-dimensional grid having affection capability. We show that this model can be used in several applications, such as modeling self-healing systems. [ABSTRACT FROM AUTHOR]

We develop the notion of Random Domino Automaton, a simple probabilistic cellular automaton model for earthquake statistics, in order to provide a mechanistic basis for the interrelation of Gutenberg–Richter law and Omori law with the waiting time distribution for earthquakes. In this work, we provide a general algebraic solution to the inverse problem for the model and apply the proposed procedure to seismic data recorded in the Legnica-Głogów Copper District in Poland, which demonstrate the adequacy of the method. The solution of the inverse problem enables adjustment of the model to localization-dependent seismic properties manifested by deviations from Gutenberg–Richter law. [ABSTRACT FROM AUTHOR]

Roughly speaking, differential privacy is a privacy-preserving strategy that guarantees attackers to be unlikely to infer, from the previous system output, the dataset from which an output is derived. This work introduces differential privacy to discrete event systems modeled by probabilistic automata to protect the state information pertaining to system resource configurations. State differential privacy is defined to protect the initial state of a discrete event system, which represents its initial resource configuration. Step-based state differential privacy verification is proposed in the framework of probabilistic automata, such that an attacker is unlikely to determine the initial state from which a system evolves, within a finite step of observations, if two systems with two different initial states satisfy state differential privacy. Specifically, the probability distributions of generating observations within a finite step from the two different initial states are approximate. If the two systems do not satisfy state differential privacy, a control specification is proposed, such that state differential privacy is enforced via supervisory control that is maximally permissive. Experimental studies are given to illustrate that the proposed method can effectively verify state differential privacy and enforce privacy protection in the probabilistic automata framework. [ABSTRACT FROM AUTHOR]

Knaster-Tarski's theorem, characterising the greatest fixpoint of a monotone function over a complete lattice as the largest post-fixpoint, naturally leads to the so-called coinduction proof principle for showing that some element is below the greatest fixpoint (e.g., for providing bisimilarity witnesses). The dual principle, used for showing that an element is above the least fixpoint, is related to inductive invariants. In this paper we provide proof rules which are similar in spirit but for showing that an element is above the greatest fixpoint or, dually, below the least fixpoint. The theory is developed for non-expansive monotone functions on suitable lattices of the form MY, where Y is a finite set and M an MV-algebra, and it is based on the construction of (finitary) approximations of the original functions. We show that our theory applies to a wide range of examples, including termination probabilities, metric transition systems, behavioural distances for probabilistic automata and bisimilarity. Moreover it allows us to determine original algorithms for solving simple stochastic games. [ABSTRACT FROM AUTHOR]

Scheduling production is an important decision issue in the manufacturing domain. With the advent of the era of Industry 4.0, the basic generation of schedules becomes no longer sufficient to face the new constraints of flexibility and agility that characterize the new architecture of production systems. In this context, schedules must take into account an increasingly disrupted environment while maintaining a good performance level. This paper contributes to the identified field of smart manufacturing scheduling by proposing a complete process for assessing the robustness of schedule solutions: i.e., its ability to resist to uncertainties. This process focuses on helping the decision maker in choosing the best scheduling strategy to be implemented. It aims at considering the impact of uncertainties on the robustness performance of predictive schedules. Moreover, it is assumed that data upcoming from connected workshops are available, such that uncertainties can be identified and modelled by stochastic variables This process is supported by stochastic timed automata for modelling these uncertainties. The proposed approach is thus based on Stochastic Discrete Event Systems models and model checking techniques defining a highly reusable and modular process. The solution process is illustrated on an academic example and its performance (generecity and scalability) are deeply evaluated using statistical analysis. The proposed application of the evaluation process is based on the technological opportunities offered by the Industry 4.0. [ABSTRACT FROM AUTHOR]

Probabilistic Cellular Automata are a generalization of Cellular Automata. Despite their simple definition, they exhibit fascinating and complex behaviours. The stationary behaviour of these models changes when model parameters are varied, making the study of their phase diagrams particularly interesting. The block approximation method, also known in this context as the local structure approach, is a powerful tool for studying the main features of these diagrams, improving upon Mean Field results. This work considers systems with multiple stationary states, aiming to understand how their interactions give rise to the structure of the phase diagram. Additionally, it shows how a simple algorithmic implementation of the block approximation allows for the effective study of the phase diagram even in the presence of several absorbing states. • The block method captures phase transitions in PCA more accurately than the Mean Field. • The block method may reveal phase transitions not captured by the Mean Field method. • A 3-block method offers a balance between computational feasibility and efficiency. [ABSTRACT FROM AUTHOR]

In this study, the continuous dynamic recrystallization (CDRX) behaviors of a hot-deformed Ti-55511 alloy are investigated in β single-phase domain. CDRX is found to play a dominant role in the microstructure evolution during thermomechanical forming of the Ti-55511 alloy. In order to quantitatively and visually simulate the hot forming process, a probabilistic cellular automata (CA) method is established. This CA technology integrates the dislocation evolution model, subgrain nucleation rate model, misorientation evolution model, grain boundary (GB) migration model, and topology deformation model. The results of a systematic study of both microstructural evolution and macroscopic mechanical response at various strains, strain rates, and temperatures are presented. The average absolute relative error (AARE), correlation coefficient (R), and root-mean squared error (RMSE) values between the experimental and simulated stresses are 4.63 %, 0.9963, and 3.81 MPa, respectively. The deviation values of subgrain size range from 1.27 % to 17.25 %, when the temperatures varies from 920 to 980 °C. The predicted results well agree with the measured results, demonstrating the transition from a coarse and static recrystallized structure to a refined and continuous dynamic recrystallized structure. A low Zener-Hollomon (Z) parameter can effectively enhance the progress of CDRX. Higher temperatures and lower strain rates result in a larger volume fraction of CDRX. Quantitative analyses confirm that the incubation period for CDRX is significantly longer than that for subgrain formation, indicating a sustained transformation from the low-angle grain boundaries (LAGBs) to the high-angle grain boundaries (HAGBs) through the absorption of dislocations. • A probabilistic CA model is developed to study continuous dynamic recrystallization (CDRX) behaviors of a Ti alloy. • Coarse and static recrystallized structures are transformed to refined and CDRX structures. • A low Zener-Hollomon (Z) parameter can effectively enhance the progress of CDRX. • The subgrain size depends on the Z parameter and follows an inverse logarithmic relationship. • The incubation period for CDRX is significantly longer than that for subgrain formation. [ABSTRACT FROM AUTHOR]

We study an important specialization of the general problem of broadcasting on directed acyclic graphs, namely, that of broadcasting on two-dimensional (2D) regular grids. Consider an infinite directed acyclic graph with the form of a 2D regular grid, which has a single source vertex $X$ at layer 0, and $k + 1$ vertices at layer $k \geq 1$ , which are at a distance of $k$ from $X$. Every vertex of the 2D regular grid has outdegree 2, the vertices at the boundary have indegree 1, and all other non-source vertices have indegree 2. At time 0, $X$ is given a uniform random bit. At time $k \geq 1$ , each vertex in layer $k$ receives transmitted bits from its parents in layer $k-1$ , where the bits pass through independent binary symmetric channels with common crossover probability $\delta \in \left({0,\frac {1}{2}}\right)$ during the process of transmission. Then, each vertex at layer $k$ with indegree 2 combines its two input bits using a common deterministic Boolean processing function to produce a single output bit at the vertex. The objective is to recover $X$ with probability of error better than $\frac {1}{2}$ from all vertices at layer $k$ as $k \rightarrow \infty $. Besides their natural interpretation in the context of communication networks, such broadcasting processes can be construed as one-dimensional (1D) probabilistic cellular automata, or discrete-time statistical mechanical spin-flip systems on 1D lattices, with boundary conditions that limit the number of sites at each time $k$ to $k+1$. Inspired by the literature surrounding the “positive rates conjecture” for 1D probabilistic cellular automata, we conjecture that it is impossible to propagate information in a 2D regular grid regardless of the noise level $\delta $ and the choice of common Boolean processing function. In this paper, we make considerable progress towards establishing this conjecture, and prove using ideas from percolation and coding theory that recovery of $X$ is impossible for any $\delta \in \left({0,\frac {1}{2}}\right)$ provided that all vertices with indegree 2 use either AND or XOR for their processing functions. Furthermore, we propose a detailed and general martingale-based approach that establishes the impossibility of recovering $X$ for any $\delta \in \left({0,\frac {1}{2}}\right)$ when all NAND processing functions are used if certain structured supermartingales can be rigorously constructed. We also provide strong numerical evidence for the existence of these supermartingales by computing several explicit examples for different values of $\delta $ via linear programming. [ABSTRACT FROM AUTHOR]

Event-B is a formal method that is used in the development of safety-critical systems; however, these systems may introduce uncertainty and also need to meet real-time requirements, which make the modeling and analysis of such systems a challenging task. While some works exist that try to extend Event-B with probability and over time, they fail to address both in a single framework. Besides, these works mainly addressed extending the language itself, not integrating extended Event-B with verification. In this paper, we aim to represent both probability and time in the Event-B language, and we will show how such a representation can be automatically translated into the probabilistic timed automata (PTA) that are described in the language of the PRISM probabilistic model checker. This transformation approach would allow us to analyze the probabilistic and time-bounded probabilistic reachability properties of probabilistic real-time systems through probabilistic timed CTL (PTCTL) logic. [ABSTRACT FROM AUTHOR]

This article introduces temporally stochastic cellular automata where a cell of the cellular system can be updated using one of the two elementary cellular automata rules, say f and g. The f is the default rule and g is temporally applied to the overall system with some probability that acts as noise to the system. As the mathematical analysis of such system is a difficult task, we use qualitative and quantitative simulations to study the dynamics of these temporally stochastic cellular automata. We are specially interested to exploring if it is possible that two periodic (resp. chaotic) rules together depict chaotic (resp. periodic) dynamics. To answer these questions, we fully classify temporally stochastic cellular automata. The study further observes phase transition and various types of class transition in the temporally stochastic cellular automata. [ABSTRACT FROM AUTHOR]

The problem of an optimal coverage of a wireless sensor network area is considered. To solve this problem, a Cellular Automata (CA) approach is proposed. More specifically, the objective is to find CA rules which are able to cover the 2D space by a minimum number of so–called "Sensor Tiles". A sensor tile consists of a von Neumann neighborhood of range 2 centered at sensor "point" and surrounded by 12 sensing "pixels". Two probabilistic CA rules were designed that can perform this task. Results of an experimental study show that the first rule evolves very fast stable sub-optimal coverings, starting from a random configuration. The second rule finds optimal coverings, however it needs much more time for their evolution. The results are supported by a theoretical study on von Neumann neighborhoods and borrowing either from heuristics or from the spectral theory of circulant graphs. [ABSTRACT FROM AUTHOR]

Together with the thermodynamics and kinetics, the complex microstructure of high-entropy alloys (HEAs) exerts a significant influence on the associated oxidation mechanisms in these concentrated solid solutions. To describe the surface oxidation in AlCoCrFeNi HEA, we employed a stochastic cellular automata model that replicates the mesoscale structures that form. The model benefits from diffusion coefficients of the principal elements through the native oxides predicted by using molecular simulations. Through our examination of the oxidation behavior as a function of the alloy composition, we corroborated that the oxide scale growth is a function of the complex chemistry and resultant microstructures. The effect of heat treatment on these alloys is also simulated by using reconstructed experimental micrographs. When they are in a single-crystal structure, no segregation is noted for α-Al2O3 and Cr2O3, which are the primary scale-forming oxides. However, a coexistent separation between Al2O3 and Cr2O3 oxide scales with the Al-Ni- and Cr-Fe-rich regions is predicted when phase-separated microstructures are incorporated into the model. [ABSTRACT FROM AUTHOR]

In this paper we formulate and prove a criterion for implementability of functions on strings by probabilistic Moore automata. [ABSTRACT FROM AUTHOR]

We study the dynamics of information sharing in web-based social networks and analyse in a stochastic manner some aspects of this phenomenon. We define the stochastic sharing calculus by considering probabilistic factors and stochastic evolutions that could be analysed statistically. A rate-based operational semantics allows specific observations and results regarding sharing in web-based social networks. To reason about the dynamics of the social networks, we verify statistically various aspects of information sharing expressed in CTL by employing an existing statistical model checker (after a translation of our processes into stochastic automata). Some queries related to the stochastic behaviours in social networks are illustrated by a running example. [ABSTRACT FROM AUTHOR]

We consider the computability and complexity of decision questions for Probabilistic Finite Automata (PFA) with sub-exponential ambiguity. We show that the emptiness problem for strict and non-strict cut-points of polynomially ambiguous commutative PFA remains undecidable, implying that the problem is undecidable when inputs are from a letter monotonic language. We show that the problem remains undecidable over a binary input alphabet when the input word is over a bounded language, in the noncommutative case. In doing so, we introduce a new technique based upon the Turakainen construction of a PFA from a Weighted Finite Automaton which can be used to generate PFA of lower dimensions and of sub-exponential ambiguity. We also study freeness/injectivity problems for polynomially ambiguous PFA and study the border of decidability and tractability for various cases. [ABSTRACT FROM AUTHOR]

Context: Landscape structure influences the spread of plant pathogens, including coffee leaf rust, a fungal disease affecting the coffee industry. Rust transmission is likely affected by landscape structure through the dispersal of wind-borne spores. Previous studies found positive associations between rust incidence and the proportion of pasture cover, suggesting deforestation may facilitate spore dispersal. Objectives: We explored the links between landscape structure and coffee rust by modeling the spread of rust transmission. We investigated how (1) spatial clustering of coffee farms, (2) proportion of landscape deforestation, and (3) clustering of deforestation affects the speed of rust transmission. Methods: We developed a probabilistic model to simulate within-patch and between-patch transmission in simulated and real landscapes. We modeled within-patch transmission using a probabilistic cellular automata model and between-patch transmission using a random walk with spore movement inhibited by canopy cover. Results: Clustering of coffee farms is the primary driver of rust transmission. Deforestation is a secondary driver of rust spread: outbreaks spread more rapidly in landscapes where deforested areas are evenly dispersed throughout the landscape. When applied to real landscapes in Costa Rica, the model yields the same trends as simulated landscapes and suggests increased amounts of coffee near the starting location of the outbreak are correlated with more rapid rust spread. Conclusions: It is essential to consider landscape structure when managing the spread of crop diseases. Increasing the spacing between coffee farms and reducing forest fragmentation in coffee-growing regions can benefit biodiversity conservation and reduce the economic impacts of coffee rust. [ABSTRACT FROM AUTHOR]

Currently, the subject of acute discussion in the scientific community is the self-development of administrative-territorial entities and increasing their financial independence. In this regard, the problems of budget decentralization as an engine of economic development, as well as related issues of applying mathematical tools for modeling decision support in this area are updated. Budget decentralization is considered in this article as an institutional financial innovation, the dominant factor of which is the ratio between "soft" and "hard" budget constraints. To implement the strategy of "hard" budget constraints implemented in the process of performing the stimulating function of inter-budget regulation, the article suggests the use of economic and mathematical tools as a model innovation. The article offers economic and mathematical models representing fuzzy automata, developed through the application of the interdisciplinary synthesis of the theory of stochastic automata and fuzzy logic. The convergence of the mathematical devices of these theories allowed us to form an intellectual approach for the construction of abstract mathematical objects that have the properties of learning rational behavior in the process of decision-making and adaptation to environmental changes. To confirm these properties, we present a proof of the theorems on the asymptotic optimality of the constructed models. The functioning of economic and mathematical models is detailed through their integration into technological financial innovation in their interaction with the database. [ABSTRACT FROM AUTHOR]

We present two fundamental results about the computational power of affine finite automata (AfAs). First, we show that changing the cutpoints does not change the class of languages defined by AfAs. Second, we show that AfAs define more languages than probabilistic and quantum finite automata with exclusive cutpoints. [ABSTRACT FROM AUTHOR]

We study a class of one-dimensional probabilistic cellular automata in which each component can be in either state zero or state one. The component interacts with two neighbors: if its neighbors are in an equal state, then the component assumes the same state as its neighbors. If its neighbors are in different states, the following can happen: a one on the right-hand side of a zero, in which case the component becomes one with probability α or zero with probability 1 − α, and conversely, a zero on the right-hand side of a one, in which case the component becomes one with probability β or zero with probability 1 − β. For a set of initial distributions when both neighbors are placed on the right-hand side (respectively, both on the left-hand side) of a component, we prove that the process always converges weakly to the measure concentrated on the configuration where all the components are zeros. When one neighbor is placed on the left-hand side and the other is on the right-hand side, the same convergence happens when β < fN(α), where N is the distance between the neighbors. However, this convergence does not happen for β > 1/2α. Thus, in this case, we get the regimes of ergodicity and non-ergodicity. Moreover, we exhibit another type of phase transition, independent of neighbors' locations. We also present some numerical studies in which we use mean field approximation and Monte Carlo simulation. [ABSTRACT FROM AUTHOR]

Analyzing the behavior of sensors is becoming one of the key challenges due to their increasing use for decision making in IoT systems. The paper proposes an approach for a formal specification and analysis of such behavior starting from existing sensor traces. A model that embodies the sensor measurements over time in the form of stochastic automata is built, then temporal properties are fed to Statistical Model Checker to simulate the learned model and to perform analysis. LTL properties are employed to predict sensors' readings in time and to check the conformity of sensed data with the sensor traces in order to detect any abnormal behavior. We also use LTL properties to analyze the collective behavior of a set of sensors and build a formal model that checks the conformity of a combination of sensors' readings in time. [ABSTRACT FROM AUTHOR]

Deriving an accurate behavior model from historical data of a black box for verification and feature forecasting is seen by industry as a challenging issue especially for a large featured dataset. This paper focuses on an alternative approach where stochastic automata can be learned from time-series observations captured from a set of deployed sensors. The main advantage offered by such techniques is that they enable analysis and forecasting from a formal model instead of traditional learning methods. We perform statistical model checking to analyze the learned automata by expressing temporal properties. For this purpose, we consider a critical water infrastructure that provides a scenario based on a set of input and output values of heterogeneous sensors to regulate the dam spill gates. The method derives a consistent approximate model with traces collected over thirty years. The experiments show that the model provides not only an approximation of the desired output of a feature value but, also, forecasts the ebb and flow of the sensed data. [ABSTRACT FROM AUTHOR]

The pore scale model considers the porous structure and can fundamentally elucidate the filtration dynamics inside the DPF. In this paper, a developed two-dimensional pore scale model based on lattice Boltzmann method is adopted. A new determination method for soot particle threshold value is proposed. Flow field characteristics along different streamlines are analyzed. Particle cluster distributions and their effects are analyzed. The results show for streamlines close to the porous wall, the inlet contraction pressure drop and the outlet channel pressure drop account for a higher proportion and dominate the total pressure drop. It is necessary to focus on reducing the resistance along the last 1/5 of total outlet channel length. Near the particle deposition area, inlet channel pressures increase and outlet channel pressures decrease, creating a low-pressure area. Soot particles tend to deposit in the middle part of the channel when considering the effect of particle dynamic deposition. [Display omitted] • The continuous and complete flow process along different streamlines is simulated inside DPF channels. • Pressure drop characteristics and pressure composition along different streamlines are analyzed. • A new determination method for soot particle threshold value is proposed with consideration of soot packing density. • Dynamic particle deposition process is simulated by LB-CA method and particle cluster distributions are analyzed. • The effects of deposited soot particles on the flow field and subsequent soot particle deposition are evaluated. [ABSTRACT FROM AUTHOR]

Dietze's conjecture concerns the problem of equipping a tree automaton M with weights to make it probabilistic, in such a way that the resulting automaton N predicts a given corpus C as accurately as possible. The conjecture states that the accuracy cannot increase if the states in M are merged with respect to an equivalence relation ∼ so that the result is a smaller automaton M ∼. Put differently, merging states can never improve predictions. This is under the assumption that both M and M ∼ are bottom-up deterministic and accept every tree in C. We prove that the conjecture holds, using a construction that turns any probabilistic version N ∼ of M ∼ into a probabilistic version N of M , such that N assigns at least as great a weight to each tree in C as N ∼ does. [ABSTRACT FROM AUTHOR]

Unmanned aerial vehicles (UAVs), commonly known as drones, have found extensive applications across diverse sectors, such as agriculture, delivery, surveillance, and military. In recent times, drone swarming has emerged as a novel field of research, which involves multiple drones working in collaboration towards a shared objective. This innovation holds immense potential in transforming the way we undertake tasks, including military operations, environmental monitoring, and search and rescue missions. However, the emergence of drone swarms also brings new security challenges, as they can be susceptible to hacking and intrusion. To address these concerns, we propose utilizing a timed probabilistic automata (TPA)-based intrusion detection system (IDS) to model the normal behavior of drone swarms and identify any deviations that may indicate an intrusion. This IDS system is particularly efficient and adaptable in detecting different types of attacks in drone swarming. Its ability to adapt to evolving attack patterns and identify zero-day attacks makes it an invaluable tool in protecting drone swarms from malicious attacks.

Monitoring Activities of Daily Living (ADL) has become a major occupation to respond to the aging population and prevent frailty. To do this, the scientific community is using Machine Learning (ML) techniques to learn the lifestyle habits of people at home. The most-used formalism to represent the behaviour of the inhabitant is the Hidden Markov Model (HMM) or Probabilistic Finite Automata (PFA), where events streams are considered. A common decomposition to design ADL using a mathematical model is Activities–Actions–Events (AAE). In this paper, we propose mathematical criteria to evaluate a priori the performance of these instrumentations for the goals of ADL recognition. We also present a case study to illustrate the use of these criteria. [ABSTRACT FROM AUTHOR]

We introduce an affine generalization of counter automata, and analyze their ability as well as affine finite automata. Our contributions are as follows. We show that there is a language that can be recognized by exact realtime affine counter automata but by neither 1-way deterministic pushdown automata nor realtime deterministic k -counter automata. Then, we show that exact realtime affine counter automata can recognize a family of regular languages with a few states but the states required by realtime deterministic k -counter automata cannot be bounded. We also show that stateless affine increment-only counter automata can recognize some nonregular languages with one-sided bounded-error. Moreover, we show that a promise problem not solved by two-way quantum finite automata in polynomial time can be solved by Las Vegas affine finite automata. Lastly, we present an affine finite automaton algorithm using a counter cleverly to recognize a language, for which we do not know any bounded-error affine finite automata or two-way quantum finite automata recognizing it. [ABSTRACT FROM AUTHOR]

Metastability is a ubiquitous phenomenon in nature, which interests several fields of natural sciences. Since metastability is a genuine non-equilibrium phenomenon, its description in the framework of thermodynamics and statistical mechanics has progressed slowly for a long time. Since the publication of the first seminal paper in which the metastable behavior of the mean field Curie–Weiss model was approached by means of stochastic techniques, this topic has been largely studied by the scientific community. Several papers and books have been published in which many different spin models were studied and different approaches were developed. In this review, we focus on the comparison between the metastable behavior of synchronous and asynchronous dynamics, namely, stochastic processes in discrete time in which, at each time, either all the spins or one single spin is updated. In particular, we discuss how two different stochastic implementations of the very same Hamiltonian give rise to different metastable behaviors. [ABSTRACT FROM AUTHOR]

This paper studies trace-based equivalences for systems combining nondeterministic and probabilistic choices. We show how trace semantics for such processes can be recovered by instantiating a coalgebraic construction known as the generalised powerset construction. We characterise and compare the resulting semantics to known definitions of trace equivalences appearing in the literature. Most of our results are based on the exciting interplay between monads and their presentations via algebraic theories. [ABSTRACT FROM AUTHOR]

Autonomous driving vehicles are a kind of typical cyber-physical systems integrating complex interactions between hardware and software components such as collaborative computation, distributed communication, and spatio-clock synchronous control with surrounding traffic environment. They can percept the environment, communicate with surroundings, and react fast enough to control independently. The purpose of autonomous driving emergence is to improve driving safety, reduce environmental pollution, and ease the traffic congestion. However, new features with surrounding open and dynamic environment make systems design and verification becoming more and more complex than ever, such as stochastic communication delay, hardware spontaneous failure distribution, and natively hybrid behaviors described by ordinary differential equations. Spatial and time collision avoidance remains crucial obstacles on the path to becoming ubiquitous and dependable. In this paper, we adopt statistical model checking (SMC) to enlighten possible hazards affected by stochastic and hybrid features in the design phase of autonomous driving systems. In order to provide safety and accountability, we first propose a dedicated multi-lane spatio-clock stochastic specification language (MLSCL) to describe safety invariants and guards in domain-specific autonomous driving systems. Then, we present the semantic mapping rules between MLSCL and UPPAAL SMC models, and design the spatio-clock stochastic and hybrid automata based on MLSCL in order to model inherently stochastic and hybrid behaviors. Finally, we present an illustrative lane-change case study to verify spatio-clock stochastic and hybrid-related properties adopting SMC, and demonstrate the effectiveness of our proposed approach. [ABSTRACT FROM AUTHOR]

Eroders are monotonic cellular automata with a linearly ordered state set that eventually wipe out any finite island of nonzero states. One-dimensional eroders were studied by Gal'perin in the 1970s, who presented a simple combinatorial characterization of the class. The multi-dimensional case has been studied by Toom and others, but no such characterization has been found. We prove a similar characterization for those one-dimensional monotonic cellular automata that are eroders even in the presence of random noise. [ABSTRACT FROM AUTHOR]

Safe diagnosability of discrete-event systems (DESs) is viewed as the first necessary step of fault-tolerant supervision in the literature. For safe diagnosable systems, it is required that not only failures occurring in systems can be detected within a finite delay, but also the detection should be completed before running any unsafe operation. In this paper, we present a novel approach to deal with the safe diagnosis issue for stochastic DESs by constructing a nondeterministic automaton called the safe verifier, and the necessary and sufficient condition for safe diagnosability of stochastic DESs is presented. It is worth noting that the proposed approach has lower complexity than the existing approach based on safe diagnoser as far as the number of states. [ABSTRACT FROM AUTHOR]

Markov automata combine probabilistic branching, exponentially distributed delays and nondeterminism. This compositional variant of continuous-time Markov decision processes is used in reliability engineering, performance evaluation and stochastic scheduling. Their verification so far focused on single objectives such as (timed) reachability, and expected costs. In practice, often the objectives are mutually dependent and the aim is to reveal trade-offs. We present algorithms to analyze several objectives simultaneously and approximate Pareto curves. This includes, e.g., several (timed) reachability objectives, or various expected cost objectives. We also consider combinations thereof, such as on-time-within-budget objectives—which policies guarantee reaching a goal state within a deadline with at least probability p while keeping the allowed average costs below a threshold? We adopt existing approaches for classical Markov decision processes. The main challenge is to treat policies exploiting state residence times, even for untimed objectives. Experimental results show the feasibility and scalability of our approach. [ABSTRACT FROM AUTHOR]