More than a decade ago, Moller and Tofts published their seminal work on relating processes, which are annotated with lower time bounds, with respect to speed. Their paper has left open many questions regarding the semantic theory for the suggested bisimulation-based faster-than preorder, the MT-preorder, which have not been addressed since. The encountered difficulties concern a general compositionality result, a complete axiom system for finite processes, a convincing intuitive justification of...

More than a decade ago, Moller and Tofts published their seminal work on relating processes, which are annotated with lower time bounds, with respect to speed. Their paper has left open many questions regarding the semantic theory for the suggested bisimulation-based faster-than preorder, the MT-preorder, which have not been addressed since. The encountered difficulties concern a general compositionality result, a complete axiom system for finite processes, a convincing intuitive justification...

In this paper, we develop a divide-and-conquer approach, called block decomposition, to solve the minimum geodetic set problem. This provides us with a unified approach for all graphs admitting blocks for which the problem of finding a minimum geodetic set containing a given set of vertices (g-extension problem) can be efficiently solved. Our method allows us to derive linear time algorithms for the minimum geodetic set problem in (a proper superclass of) block-cacti and monopolar chordal graphs....

For almost all infinite binary sequences of Bernoulli trials $(p,q)$ the frequency of blocks of length $k\left(N\right)$ in the first $N$ terms tends asymptotically to the probability of the blocks, if $k\left(N\right)$ increases like ${\log }_{\frac{1}{p}}N-{\log }_{\frac{1}{p}}N-\psi \left(N\right)$ (for $p\le q$) where $\psi \left(N\right)$ tends to $+\infty$. This generalizes a result due to P. Flajolet, P. Kirschenhofer and R.F. Tichy concerning the case $p=q=\frac{1}{2}$.

Border bases are an alternative to Gröbner bases. The former have several more desirable properties. In this paper some constructions and operations on border bases are presented. Namely; the case of a restriction of an ideal to a polynomial ring (in a smaller number of variables), the case of the intersection of two ideals, and the case of the kernel of a homomorphism of polynomial rings. These constructions are applied to the ideal of relations and to factorizable derivations.

The theory of partially observable Markov decision processes (POMDPs) is a useful tool for developing various intelligent agents, and learning hierarchical POMDP models is one of the key approaches for building such agents when the environments of the agents are unknown and large. To learn hierarchical models, bottom-up learning methods in which learning takes place in a layer-by-layer manner from the lowest to the highest layer are already extensively used in some research fields such as hidden...

Given $n$ rectangles in a plane whose all sides belong to two perpendicular directions, an algorithm for the construction of the boundary of the union of those rectangles is shown in teh paper.

Let $x=x_0{x}_1\cdots$ be a fixed point of a substitution on the alphabet $\left\{a,b\right\},$ and let $U_a=\left(\begin{array}{cc}\hfill -1& \hfill -1\\ \hfill 0& \hfill 1\end{array}\right)$ and $U_b=\left(\begin{array}{cc}\hfill 1& \hfill 1\\ \hfill 0& \hfill 1\end{array}\right)$. We give a complete classification of the substitutions $\sigma :{\left\{a,b\right\}}^{☆}$ according to whether the sequence of matrices ${\left(U_{x_0}{U}_{x_1}\cdots U_{x_n}\right)}_{n=0}^{\infty }$ is bounded or unbounded. This corresponds to the boundedness or unboundedness of the oriented walks generated by the substitutions.

Stochastic Petri nets generalize the notion of queuing systems and are a useful model in performance evaluation of parallel and distributed systems. We give necessary and sufficient conditions for the boundedness of a stochastic process related to these nets.