Transition systems and concurrent processes
Transitive decomposition of fuzzy preference relations: the case of nilpotent minimum
Transitivity is a fundamental notion in preference modelling. In this work we study this property in the framework of additive fuzzy preference structures. In particular, we depart from a large preference relation that is transitive w.r.t. the nilpotent minimum t-norm and decompose it into an indifference and strict preference relation by means of generators based on t-norms, i. e. using a Frank t-norm as indifference generator. We identify the strongest type of transitivity these indifference and...
Transitive Hall sets.
Translation from classical two-way automata to pebble two-way automata
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,...
Translation from classical two-way automata to pebble two-way automata
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,...
Transparent Scheduling of Composite Web Services
Composite Web Services (CWS) aggregate multiple Web Services in one logical unit to accomplish a complex task (e.g. business process). This aggregation is achieved by defining a workflow that orchestrates the underlying Web Services in a manner consistent with the desired functionality. Since CWS can aggregate atomic and other CWS they foster the development of service layers and reuse of already existing functionality. An important issue in the deployment of services is their run-time performance under...
Traversing directed Eulerian mazes.
Treating the exceptional cases of the MeatAxe.
Tree algebra of sofic tree languages
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
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
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...
Tree inclusion problems
Given two trees (a target T and a pattern P) and a natural number w, window embedded subtree problems consist in deciding whether P occurs as an embedded subtree of T and/or finding the number of size (at most) w windows of T which contain pattern P as an embedded subtree. P is an embedded subtree of T if P can be obtained by deleting some nodes from T (if a node v is deleted, all edges adjacent to v are also deleted, and outgoing edges are replaced by edges going from the parent of v (if it exists)...
Tree pattern matching from regular tree expressions
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...
Tree transformations defined by hypersubstitutions
Tree transducers are systems which transform trees into trees just as automata transform strings into strings. They produce transformations, i.e. sets consisting of pairs of trees where the first components are trees belonging to a first language and the second components belong to a second language. In this paper we consider hypersubstitutions, i.e. mappings which map operation symbols of the first language into terms of the second one and tree transformations defined by such hypersubstitutions....
Tree-controlled grammars with restrictions placed upon cuts and paths
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...
Trees, band monoids, and formal languages.
Treewidth and minimum fill-in on -trapezoid graphs.
Treshold logic unit optimization by linear programming
Triangle-free planar graphs and segment intersection graphs.
Triangulace s hranovými kritérii - Šípkové Růženky právem nebo neprávem zapomenuté?
Planární triangulace zadané množiny bodů je častým základem aplikací, proto vzniklo mnoho metod, jak triangulaci zkonstruovat. Všechny metody se snaží dospět k trojúhelníkům "co nejrovnostrannějším", což je možné zařídit optimalizací úhlových nebo hranových kritérií. Vzhledem k vynikajícím vlastnostem, všestrannosti a snadné konstrukci Delaunayovy triangulace, nejdůležitější a nejznámější představitelky úhlových kritérií, stojí ostatní typy triangulace, zejména hranově optimalizované, poněkud...