Search results for "Tree"
showing 10 items of 1841 documents
On the determinization of weighted finite automata
1998
We study determinization of weighted finite-state automata (WFAs), which has important applications in automatic speech recognition (ASR). We provide the first polynomial-time algorithm to test for the twins property, which determines if a WFA admits a deterministic equivalent. We also provide a rigorous analysis of a determinization algorithm of Mohri, with tight bounds for acyclic WFAs. Given that WFAs can expand exponentially when determinized, we explore why those used in ASR tend to shrink. The folklore explanation is that ASR WFAs have an acyclic, multi-partite structure. We show, however, that there exist such WFAs that always incur exponential expansion when determinized. We then in…
Restricted 123-avoiding Baxter permutations and the Padovan numbers
2007
AbstractBaxter studied a particular class of permutations by considering fixed points of the composite of commuting functions. This class is called Baxter permutations. In this paper we investigate the number of 123-avoiding Baxter permutations of length n that also avoid (or contain a prescribed number of occurrences of) another certain pattern of length k. In several interesting cases the generating function depends only on k and is expressed via the generating function for the Padovan numbers.
Dimensions of random affine code tree fractals
2014
We calculate the almost sure Hausdorff dimension for a general class of random affine planar code tree fractals. The set of probability measures describing the randomness includes natural measures in random $V$-variable and homogeneous Markov constructions.
On the Power of Tree-Walking Automata
2000
Tree-walking automata (TWAs) recently received new attention in the fields of formal languages and databases. Towards a better understanding of their expressiveness, we characterize them in terms of transitive closure logic formulas in normal form. It is conjectured by Engelfriet and Hoogeboom that TWAs cannot define all regular tree languages, or equivalently, all of monadic second-order logic. We prove this conjecture for a restricted, but powerful, class of TWAs. In particular, we show that 1-bounded TWAs, that is TWAs that are only allowed to traverse every edge of the input tree at most once in every direction, cannot define all regular languages. We then extend this result to a class …
The terminal hyperspace of homogeneous continua
2010
Abstract We investigate the structure of the collection of terminal subcontinua in homogeneous continua. The main result is a reduction of this structure to six specific types. Three of these types are of one-dimensional spaces, and examples representing these types are known. It is not known whether higher dimensional examples having non-trivial terminal subcontinua and representing the three remaining types exist.
Nondeterministic operations on finite relational structures
1998
Abstract This article builds on a tutorial introduction to universal algebra for language theory (Courcelle, Theoret. Comput. Sci. 163 (1996) 1–54) and extends it in two directions. First, nondeterministic operations are considered, i.e., operations which give a set of results instead of a single one. Most of their properties concerning recognizability and equational definability carry over from the ordinary case with minor modifications. Second, inductive sets of evaluations are studied in greater detail. It seems that they are handled most naturally in the framework presented here. We consider the analogues of top-down and bottom-up tree transducers. Again, most of their closure propertie…
On extremal cases of Hopcroft’s algorithm
2010
AbstractIn this paper we consider the problem of minimization of deterministic finite automata (DFA) with reference to Hopcroft’s algorithm. Hopcroft’s algorithm has several degrees of freedom, so there can exist different executions that can lead to different sequences of refinements of the set of the states up to the final partition. We find an infinite family of binary automata for which such a process is unique, whatever strategy is chosen. Some recent papers (cf. Berstel and Carton (2004) [3], Castiglione et al. (2008) [6] and Berstel et al. (2009) [1]) have been devoted to find families of automata for which Hopcroft’s algorithm has its worst execution time. They are unary automata as…
The mixed general routing polyhedron
2003
[EN] In Arc Routing Problems, ARPs, the aim is to find on a graph a minimum cost traversal satisfying some conditions related to the links of the graph. Due to restrictions to traverse some streets in a specified way, most applications of ARPs must be modeled with a mixed graph. Although several exact algorithms have been proposed, no polyhedral investigations have been done for ARPs on a mixed graph. In this paper we deal with the Mixed General Routing Problem which consists of finding a minimum cost traversal of a given link subset and a given vertex subset of a mixed graph. A formulation is given that uses only one variable for each link (edge or arc) of the graph. Some properties of the…
A new formulation of the loop-tree duality at higher loops
2019
We present a new formulation of the loop-tree duality theorem for higher loop diagrams valid both for massless and massive cases. $l$-loop integrals are expressed as weighted sum of trees obtained from cutting $l$ internal propagators of the loop graph. In addition, the uncut propagators gain a modified $i \delta$-prescription, named dual-propagators. In this new framework one can go beyond graphs and calculate the integrand of loop amplitudes as a weighted sum of tree graphs, which form a tree-like object. These objects can be computed efficiently via recurrence relations.
SCHUR MULTIPLIERS AND SPHERICAL FUNCTIONS ON HOMOGENEOUS TREES
2010
Let X be a homogeneous tree of degree q + 1 (2 ≤ q ≤ ∞) and let ψ : X × X → ℂ be a function for which ψ(x, y) only depends on the distance between x, y ∈ X. Our main result gives a necessary and sufficient condition for such a function to be a Schur multiplier on X × X. Moreover, we find a closed expression for the Schur norm ||ψ||S of ψ. As applications, we obtaina closed expression for the completely bounded Fourier multiplier norm ||⋅||M0A(G) of the radial functions on the free (non-abelian) group 𝔽N on N generators (2 ≤ N ≤ ∞) and of the spherical functions on the q-adic group PGL2(ℚq) for every prime number q.