Recognizable formal power series on trees
From MaRDI portal
Publication:1164440
DOI10.1016/0304-3975(82)90019-6zbMath0485.68077OpenAlexW1987028886MaRDI QIDQ1164440
Christophe Reutenauer, Jean Berstel
Publication date: 1982
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(82)90019-6
free magmaalgebraic noncommutative formal power seriesalgebricity of enumerating functions on treesfunctions on treespumping lemma for recognizable functionsrecognizable function
Related Items
Crisp-determinization of weighted tree automata over strong bimonoids, Fuzzy tree automata, Weighted grammars and Kleene's theorem, Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids, Tree Transformations and Dependencies, Stochastically costed tree automata: Turakainen's theorem, Weighted tree automata and weighted logics, Compositions of tree series transformations, Positive tree representations and applications to tree automata, On Lindenmayerian algebraic power series, Minimisation of Multiplicity Tree Automata, Combinatory categorial grammars as generators of weighted forests, Ambiguity Hierarchies for Weighted Tree Automata, PURE AND O-SUBSTITUTION, Recognizable series on graphs and hypergraphs, Unnamed Item, Varieties of recognizable tree series over fields, A Comparison of Sets of Recognizable Weighted Tree Languages Over Specific Sets of Bounded Lattices, Weighted logics for unranked tree automata, Pumping Lemmata for Recognizable Weighted Languages over Artinian Semirings, Learning Rational Stochastic Tree Languages, Effective construction of the syntactic algebra of a recognizable series on trees, Automatic average-case analysis of algorithms, A complexity calculus for recursive tree algorithms, Weighted monadic Datalog, On the syntactic complexity of tree series, Colored operads, series on colored operads, and combinatorial generating systems, A Büchi-like theorem for weighted tree automata over multioperator monoids, Représentations matricielles des séries d'arbre reconnaissables, Branching automata with costs -- a way of reflecting parallelism in costs, Equational tree transformations, The Power of Weighted Regularity-Preserving Multi Bottom-Up Tree Transducers, Hasse diagrams for classes of deterministic bottom-up tree-to-tree-series transformations, Cut sets as recognizable tree languages, A Kleene theorem for weighted tree automata over distributive multioperator monoids, A Kleene theorem for weighted tree automata over tree valuation monoids, Characterizations of recognizable weighted tree languages by logic and bimorphisms, RELATING TREE SERIES TRANSDUCERS AND WEIGHTED TREE AUTOMATA, Finite sequentiality of unambiguous max-plus tree automata, On Finite and Polynomial Ambiguity of Weighted Tree Automata, Constructions effectives sur les séries formelles d'arbres. (Effective constructions on formal tree series), Approximate minimization of weighted tree automata, Principal abstract families of weighted tree languages, Weighted Tree Automata over Valuation Monoids and Their Characterization by Weighted Logics, Kleene Theorem in Partial Conway Theories with Applications, Equational Weighted Tree Transformations with Discounting, Survey: Weighted Extended Top-Down Tree Transducers Part III — Composition, Valuations of Weighted Automata: Doing It in a Rational Way, Revisiting regular sequences in light of rational base numeration systems, MAT learners for tree series: an abstract data type and two realizations, Equational weighted tree transformations, Hierarchies of tree series transformations, Weighted automata, Unique, guarded fixed points in an additive setting, Recognizable formal series on trees and cofree coalgebraic systems, The rank of a formal tree power series, Pushdown tree automata, algebraic tree systems, and algebraic tree series, Context-free series on trees, The theory of compositionals, Some remarks on recognizable treeseries, R-fuzzy computation, On two families of forests, Characterizing weighted MSO for trees by branching transitive closure logics, Ambiguity hierarchies for weighted tree automata, Survey: finite-state technology in natural language processing
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An Ogden-like iteration lemma for rational power series
- Un théorème de factorisation des produits d'endomorphismes de \(K^N\)
- Une demonstration combinatoire de la formule de Lagrange à deux variables
- Pumping lemmas for term languages
- Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
- Generalized sequential machine maps
- On the definition of a family of automata
- Representation of a word function as the sum of two functions
- Integral sequential word functions and growth equivalence of lindenmayer systems
- Generalized finite automata theory with an application to a decision problem of second-order logic
- Tree generating regular systems
- Tree-Manipulating Systems and Church-Rosser Theorems
