The state complexity, respectively, nondeterministic state complexity of a regular language L is the number of states of the minimal deterministic, respectively, of a minimal nondeterministic finite automaton for L. Some of the most studied state complexity questions deal with size comparisons of nondeterministic finite automata of differing degree of ambiguity. More generally, if for a regular language we compare the size of description by a finite automaton and by a more powerful language definition mechanism, such as a context-free grammar, we encounter non-recursive trade-offs. Operational state complexity studies the state complexity of the language resulting from a regularity preserving operation as a function of the complexity of the argument languages. Determining the state complexity of combined operations is generally challenging and for general combinations of operations that include intersection and marked concatenation it is uncomputable.

Metaverse can unleash the potentials of Internet of Sense (IoS) communication by intertwining objects and environment between physical world and parallel virtual world. In order to digitally experience smell or taste and navigate effortlessly in virtual reality, optimal resource allocation to strengthen sensing data based infrastructure system is a critical research challenge. The Metaverse Infrastructure Service Providers (MISPs) tap into data marketplace and subscribe to resources in advance for fulfilling the needs of data consumers and users. The demand of the data based services being uncertain, non-optimal subscription schemes may lead to unwanted resource wastage or shortage. Thus, we propose a Stochastic Integer Programming (SIP) model with two phase reservation and on-demand plans for optimal resource allocation in data marketplace. Further along this line, we strive to predict the demand by leveraging Quantum Neural Networks (QNN) that is able to learn with fewer historical data in comparison to classical machine/deep learning paradigms. Extensive simulation results justify that QNN as a supporting model can significantly reduce the computational complexities of SIP formulation. This research can contribute to reduce Metaverse resource fabrication costs, upgrade the profit margin for MISPs by increasing data based service sales revenue, provide real-time resource management decisions, and overall make real impacts in the virtual world.

Metaverse refers to the intersection of parallel virtual worlds with their physical counterparts by allowing users to interact with virtual people, objects, and environments. Resource allocation in various aspects of Metaverse domains, called as MetaSlices hereinafter, is a crucial optimization research problem. To serve this purpose, we consider a MetaSlice framework with the notion of sharing resources among common functions and enable placing time-sensitive services at the edge of multi-tier architecture in proximity to users. Unfortunately, the classical Integer Linear Programming is inappropriate for such heavily constrained optimization problem due to the extensive running time and memory. Hence, we model a novel Quadratic Unconstrained Binary Optimization (QUBO) formulation to simultaneously optimize resources and secure Quality of Service for MetaSlices as a paradigm shift towards quantum computing. Furthermore, we propose to employ a hybrid classical-quantum WSQA to optimize resource under uncertainty, offer ultra-low running time, and increase service acceptance rate/scalability in resource-hungry and dynamic Metaverse system. Extensive simulation results demonstrate that WSQA outperforms other classical and standalone quantum annealing approaches, even with the limited availability of qubits (quantum resources). Thus, this research paves the way to decrease massive resource fabrication costs and upgrade profit margin for Metaverse Internet Service Providers, while simultaneously providing real-time services for Metaverse users.

Metaverse can unleash the potentials of Internet of Sense (IoS) communication by intertwining objects and environment between physical world and parallel virtual world. In order to digitally experience smell or taste and navigate effortlessly in virtual reality, optimal resource allocation to strengthen sensing data based infrastructure system is a critical research challenge. The Metaverse Infrastructure Service Providers (MISPs) tap into data marketplace and subscribe to resources in advance for fulfilling the needs of data consumers and users. The demand of the data based services being uncertain, non-optimal subscription schemes may lead to unwanted resource wastage or shortage. Thus, we propose a Stochastic Integer Programming (SIP) model with two phase reservation and on-demand plans for optimal resource allocation in data marketplace. Further along this line, we strive to predict the demand by leveraging Quantum Neural Networks (QNN) that is able to learn with fewer historical data in comparison to classical machine/deep learning paradigms. Extensive simulation results justify that QNN as a supporting model can significantly reduce the computational complexities of SIP formulation. This research can contribute to reduce Metaverse resource fabrication costs, upgrade the profit margin for MISPs by increasing data based service sales revenue, provide real-time resource management decisions, and overall make real impacts in the virtual world.

We give an optimized construction of a tree automaton recognizing the k-parallel, k ≥ 1, tree concatenation of two regular tree languages. For tree automata with m and n states, respectively, the construction yields an upper bound (m+12)(n+1)⋅2nk−1 for the state complexity of k-parallel tree concat enation. We give a matching lower bound in the case k = 2. We conjecture that the upper bound is tight for all values of k. We also consider the special case where one of the tree languages is the set of all ranked trees and in this case establish a different tight state complexity bound for all values of k.

Redundant readers elimination is one of the fundamental optimization research problems in RFID networks. The problem is NP-hard and can be solved approximately using best known centralized set cover algorithms. However, either distributed or localized solutions for this problem are much more realistic and useful in practice. Different distributed and a few local algorithms are known in the literature. In this paper, we propose a cellular automaton based local algorithm for the redundant readers elimination optimization problem. To the best of our knowledge, this is the first cellular automaton based algorithm (that is, a strictly local algorithm) to solve this problem. We compare the performance of our algorithm with other local algorithms and establish that our algorithm gives much better results. We also compare our algorithm with the best known centralized approximation algorithm and find very competitive results even though our algorithm is a local one.

Object monitoring is an important application of mobile wireless sensor networks. Several algorithms appear in the literature for different variants of the object monitoring problem. Most of them are either centralized or distributed. Algorithms for mobile wireless sensor networks involve many aspects not dealt with in traditional networks and hence mobile wireless networks can be viewed as an unconventional computation model. We design algorithms for mobile wireless sensor networks based on another unconventional model of computation namely, the biologically inspired cellular automata. We design a cellular automaton based algorithm for an object monitoring problem where initially a number of mobile sensors and mobile objects are deployed randomly in a dense area of the network and they are allowed to move within the network. Our main goal is to monitor the mobile objects by the mobile sensors as long as possible. To the best of our knowledge, we propose the first cellular automaton based algorithm for this problem. We find that our algorithm can monitor a good number of objects constantly over time.

We propose a cellular automaton based local algorithm to reposition mobile sensors of a wireless sensors network. Our main goal is to maximize the total coverage of the network while maintaining the connectivity among the sensors. In most of the applications, it is not feasible to deploy mobile sensors using a global algorithm. Typically, the sensors are initially densely deployed and use their mobility to increase the coverage of the network. Our algorithm uses very limited local information to compute the final positions of the sensors. In many applications, maximizing the coverage is not the only objective; the sensors also need to communicate with each other. Therefore, maintaining connectivity when the sensors disperse is an important goal, and our algorithm achieves this as well. We perform different simulations on different starting configurations. For some configurations, the optimal solution is arrived at, while for others a near optimal solution is obtained.

We design new cellular automaton based algorithms to improve coverage in a network with mobile sensors. The algorithms can be useful in applications where sensors are initially deployed in one place and need to disperse to the environment autonomously, or in situations where in certain areas sensors may be destroyed (e.g. due to a natural disaster), and the sensors need to use their mobility in order to restore coverage. We propose a cellular automaton model that divides the neighborhood of a cell into four (North West, North East, South West and South East) quadrants and the sensors try to find out the directions where they can move to increase the coverage. We compared our model with a previous model for different initial configurations and have found that our model reaches a comparable coverage more quickly. Our algorithms use two parameter values to guide the movements of the sensors. Especially with the best choices of the parameter values, our algorithms require the sensors to make considerably fewer atomic movements than the earlier algorithm. For mobile sensor networks, energy consumption is largely determined by the amount of movement, and minimizing movement will increase the life time of the network.

We consider the transition complexity of regular languages based on the incomplete deterministic finite automata. We establish tight bounds for the transition complexity of Boolean operations, in the case of union the upper and lower bounds differ by a multiplicative constant two. We show that the transition complexity results for union and complementation are very different from the state complexity results for the same operations. However, for intersection, the transition complexity bounds turn out to be similar to the corresponding bounds for state complexity.

We consider the representational state complexity of unranked tree automata. The bottom-up computation of an unranked tree automaton may be either deterministic or nondeterministic, and further variants arise depending on whether the horizontal strin

We investigate the nondeterministic state complexity of basic operations for prefix-free regular languages. The nondeterministic state complexity of an operation is the number of states that are necessary and sufficient in the worst-case for a minimal nondeterministic finite-state automaton that accepts the language obtained from the operation. We establish the precise state complexity of catenation, union, intersection, Kleene star, reversal and complementation for prefix-free regular languages.

We consider classes of forests defined by synchronized and pushdown tree automata having a fixed size of, respectively, synchronization or pushdown alphabet. We show that such families have nice properties, for instance, they form either a sheaf or a strict alphabetic cone of forests. Furthermore, for the (deterministic and nondeterministic) synchronized tree automata and the real-time pushdown tree automata we obtain a strict infinite forest hierarchy with respect to the alphabet size.

We consider structured processes that compute changes of valuation functions defined for functional structures, where both the domain and range of each function are the set of sequences over a carrier set. By introducing consistency conditions and certain restrictions on the underlying graph, we obtain a determinism result guaranteeing that for each valuation the structured process computes a unique change of context, i.e., the process defines a partial function on the set of valuations. Employing the determinism theorem we obtain a decomposition result for interpreted trees using a structured process where the edges represent computations in the subtrees.

New constructs for synchronization termed synchronization expressions (SEs) have been developed as high-level language constructs for parallel programming languages [8, 9]. Statements that are constrained by certain synchronization requirements are tagged, and synchronization requests are specified as expressions of statement tags. In this paper, we introduce a new family of languages named synchronization languages which we use to give a precise semantic description for SEs. Under this description, relations such as equivalence and inclusion between SEs can be easily understood and tested. In practice, it also provides us with a systematic way for the implementation as well as the simplification of SEs in parallel programming languages. We show that each synchronization language is closed under the following rewriting rules: (1) a s b s → b s a s , (2) a t b t → b t a t , (3) a s b t → b t a s , (4) a t a s b t b s → b t b s a t a s and also h(a t a s b t b s ) → h(b t b s a t a s ) for any morphism h that satisfies certain conditions which will be specified in the paper. We conjecture that closure under the above rewriting rules is a sufficient condition for a regular st-language to be a synchronization language. Several other properties of synchronization languages are also studied.