The search session has expired. Please query the service again.
Displaying 821 –
840 of
948
We study the relation between the standard two-way automata and
more powerful devices, namely, two-way finite automata equipped
with some additional “pebbles” that are movable along
the input tape, but their use is restricted (nested) in
a stack-like fashion. Similarly as in the case of the classical
two-way machines, it is not known whether there exists
a polynomial trade-off, in the number of states, between the
nondeterministic and deterministic two-way automata with
nested pebbles. However,...
We consider the languages of finite trees called tree-shift languages which are factorial extensible tree languages. These languages are sets of factors of subshifts of infinite trees. We give effective syntactic characterizations of two classes of regular tree-shift languages: the finite type tree languages and the tree languages which are almost of finite type. Each class corresponds to a class of subshifts of trees which is invariant by conjugacy. For this goal, we define a tree algebra which...
We show that the inclusion problem is decidable for rational languages
of words indexed by scattered countable linear orderings. The method leans on a reduction to
the decidability of the monadic second order theory of the infinite binary tree
[9].
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 nodes, the automaton has at most states, its transition function cardinality is at most and there are pushdown store symbols. If hashing is used for storing...
In this work we deal with tree pattern matching over ranked trees, where the pattern set to be matched against is defined by a regular tree expression. We present a new method that uses a tree automaton constructed inductively from a regular tree expression. First we construct a special tree automaton for the regular tree expression of the pattern , which is somehow a generalization of Thompson automaton for strings. Then we run the constructed automaton on the subject tree . The pattern matching...
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 enumerable...
We consider languages expressed by word equations in two variables and give a complete
characterization for their complexity functions, that is, the functions that give the number of
words of the same length. Specifically, we prove that there are only five types of complexities:
constant, linear, exponential, and two in between constant and linear. For the latter two, we
give precise characterizations in terms of the number of solutions of Diophantine equations of
certain types. In particular,...
Currently displaying 821 –
840 of
948