Displaying similar documents to “Average execution times of series-parallel networks.”

Arbology: Trees and pushdown automata

Bořivoj Melichar, Jan Janoušek, Tomas Flouri (2012)

Kybernetika

Similarity:

We present a unified and systematic approach to basic principles of Arbology, a new algorithmic discipline focusing on algorithms on trees. Stringology, a highly developed algorithmic discipline in the area of string processing, can use finite automata as its basic model of computation. For various kinds of linear notations of ranked and unranked ordered trees it holds that subtrees of a tree in a linear notation are substrings of the tree in the linear notation. Arbology uses pushdown...

Tree compression pushdown automaton

Jan Janoušek, Bořivoj Melichar, Martin Poliak (2012)

Kybernetika

Similarity:

A new kind of a deterministic pushdown automaton, called a Tree Compression Automaton, is presented. The tree compression automaton represents a complete compressed index of a set of trees for subtrees and accepts all subtrees of given trees. The algorithm for constructing our pushdown automaton is incremental. For a single tree with n nodes, the automaton has at most n + 1 states, its transition function cardinality is at most 4 n and there are 2 n + 1 pushdown store symbols. If hashing is used...

A note on the characterization ofsome minification processes

Wiesław Dziubdziela (1997)

Applicationes Mathematicae

Similarity:

We present a stochastic model which yields a stationary Markov process whose invariant distribution is maximum stable with respect to the geometrically distributed sample size. In particular, we obtain the autoregressive Pareto processes and the autoregressive logistic processes introduced earlier by Yeh et al