Displaying similar documents to “A new family of Markov branching trees: the alpha-gamma model.”

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...

Combinatorial trees in Priestley spaces

Richard N. Ball, Aleš Pultr, Jiří Sichler (2005)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

We show that prohibiting a combinatorial tree in the Priestley duals determines an axiomatizable class of distributive lattices. On the other hand, prohibiting n -crowns with n ≥ 3 does not. Given what is known about the diamond, this is another strong indication that this fact characterizes combinatorial trees. We also discuss varieties of 2-Heyting algebras in this context.

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...

Tree-controlled grammars with restrictions placed upon cuts and paths

Jiří Koutný, Alexander Meduna (2012)

Kybernetika

Similarity:

First, this paper discusses tree-controlled grammars with root-to-leaf derivation-tree paths restricted by control languages. It demonstrates that if the control languages are regular, these grammars generate the family of context-free languages. Then, in a similar way, the paper introduces tree-controlled grammars with derivation-tree cuts restricted by control languages. It proves that if the cuts are restricted by regular languages, these grammars generate the family of recursively...