Currently displaying 1 – 6 of 6

Showing per page

Order by Relevance | Title | Year of publication

Transformations of grammars and translation directed by L R parsing

Bořivoj MelicharNguyen van Bac — 2002

Kybernetika

The class of L R translation grammars is introduced. This class is characterized by a possibility to implement a formal translation as an algorithm directed by L R parsing. To perform a translation, the conventional L R parser is extended by a facility to perform output operations within the parsing actions shift and reduce. The definitions of Kernel ( R ) - and L R -translation grammars are presented. The transformations shaking-down and postponing that enable to transform some translation grammars into Kernel...

Tree compression pushdown automaton

Jan JanoušekBořivoj MelicharMartin Poliak — 2012

Kybernetika

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

Arbology: Trees and pushdown automata

Bořivoj MelicharJan JanoušekTomas Flouri — 2012

Kybernetika

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

Page 1

Download Results (CSV)