All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 42 Next

Displaying 821 – 840 of 948

Showing per page

Translation from classical two-way automata to pebble two-way automata

Viliam Geffert, L'ubomíra Ištoňová (2011)

RAIRO - Theoretical Informatics and Applications

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

Tree algebra of sofic tree languages

Nathalie Aubrun, Marie-Pierre Béal (2014)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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

Tree Automata and Automata on Linear Orderings

Véronique Bruyère, Olivier Carton, Géraud Sénizergues (2009)

RAIRO - Theoretical Informatics and Applications

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

Tree compression pushdown automaton

Jan Janoušek, Bořivoj Melichar, Martin 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...

Tree pattern matching from regular tree expressions

Ahlem Belabbaci, Hadda Cherroun, Loek Cleophas, Djelloul Ziadi (2018)

Kybernetika

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 E , which is somehow a generalization of Thompson automaton for strings. Then we run the constructed automaton on the subject tree t . The pattern matching...

Tree-controlled grammars with restrictions placed upon cuts and paths

Jiří Koutný, Alexander Meduna (2012)

Kybernetika

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

Two-variable word equations

Lucian Ilie, Wojciech Plandowski (2000)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Two-variable word equations

Lucian Ilie, Wojciech Plandowski (2010)

RAIRO - Theoretical Informatics and Applications

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