scientific article

zbMath0537.68056arXiv1509.06233MaRDI QIDQ3323279

Publication date: 1984

Full work available at URL: https://arxiv.org/abs/1509.06233

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

pattern recognition decision problems tree transformations lattices formal languages tree automata universal algebra tree transducers mathematical linguistics tree recognizers

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Pattern recognition, speech recognition (68T10) Decidability of theories and sets of sentences (03B25)

Related Items (only showing first 100 items - show all)

On algebraic and logical specifications of classes of regular languages. ⋮ Compositions of constant weighted extended tree transducers ⋮ Right-linear half-monadic term rewrite systems ⋮ Equivalence of regular binoid expressions and regular expressions denoting binoid languages over free binoids ⋮ Domains of partial attributed tree transducers ⋮ Tree automata for code selection ⋮ Tree Transformations and Dependencies ⋮ First-order properties of trees, star-free expressions, and aperiodicity ⋮ Deciding top-down determinism of regular tree languages ⋮ Axiomatizing the equational theory of regular tree languages ⋮ High level tree transducers and iterated pushdown tree transducers ⋮ Stochastically costed tree automata: Turakainen's theorem ⋮ A descriptive characterisation of linear languages ⋮ State hyperstructures of tree automata based on lattice-valued logic ⋮ Incremental construction of minimal tree automata ⋮ The complexity of tree automata and XPath on grammar-compressed trees ⋮ Semigroups of linear tree languages ⋮ Weighted tree automata with constraints ⋮ Hybrid tree automata and the yield theorem for constituent tree automata ⋮ Gaifman's theorem on categorial grammars revisited ⋮ Continuous monoids and semirings ⋮ Branching synchronization grammars with nested tables ⋮ Finite loops recognize exactly the regular open languages ⋮ A generalized superposition of linear tree languages and products of linear tree languages ⋮ Positive tree representations and applications to tree automata ⋮ Logical description of context-free graph languages ⋮ Forward and backward application of symbolic tree transducers ⋮ An Implementation of Deterministic Tree Automata Minimization ⋮ Syntax-Directed Translations and Quasi-alphabetic Tree Bimorphisms ⋮ Intersection of finitely generated congruences over term algebra ⋮ Decision procedures for inductive Boolean functions based on alternating automata ⋮ Test sets for the universal and existential closure of regular tree languages. ⋮ Decidability for left-linear growing term rewriting systems. ⋮ Term rewriting restricted to ground terms. ⋮ A gap property of deterministic tree languages. ⋮ Shape preserving top-down tree transducers. ⋮ On ground tree transformations and congruences induced by tree automata. ⋮ Model building with ordered resolution: Extracting models from saturated clause sets ⋮ Weighted logics for unranked tree automata ⋮ Coding tree languages based on lattice-valued logic ⋮ A hierarchy of deterministic top-down tree transformations ⋮ Regular Approximation of Weighted Linear Context-Free Tree Languages ⋮ From Tree-Based Generators to Delegation Networks ⋮ Aperiodicity in Tree Automata ⋮ Decidability of the confluence of finite ground term rewrite systems and of other related term rewrite systems ⋮ Unnamed Item ⋮ Extended Multi Bottom-Up Tree Transducers ⋮ Sur une classe de transformations d'arbres ⋮ Natural Language Processing, Moving from Rules to Data ⋮ Minimizing Deterministic Weighted Tree Automata ⋮ Yield-languages recognized by alternating tree recognizers ⋮ Compositions of Tree-to-Tree Statistical Machine Translation Models ⋮ Complexity of E0L structural equivalence ⋮ Decidability of equivalence for a class of non-deterministic tree transducers ⋮ Graph automata for linear graph languages ⋮ Concatenation of graphs ⋮ Variable Tree Automata over Infinite Ranked Alphabets ⋮ Multiple context-free tree grammars: lexicalization and characterization ⋮ Shuffles of trees ⋮ Another variation on the common subexpression problem ⋮ Variants of top-down tree transducers with look-ahead ⋮ Colored operads, series on colored operads, and combinatorial generating systems ⋮ Abstract Families of Abstract Categorial Languages ⋮ A Büchi-like theorem for weighted tree automata over multioperator monoids ⋮ Algebraic recognizability of regular tree languages ⋮ Querying linguistic treebanks with monadic second-order logic in linear time ⋮ Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity ⋮ Ogden's lemma, multiple context-free grammars, and the control language hierarchy ⋮ Set constraints with intersection ⋮ TREE AUTOMATA BASED ON COMPLETE RESIDUATED LATTICE-VALUED LOGIC: REDUCTION ALGORITHM AND DECISION PROBLEMS ⋮ Compositions of Tree-to-Tree Statistical Machine Translation Models ⋮ Decidability of the finiteness of ranges of tree transductions ⋮ The equivalence of bottom-up and top-down tree-to-graph transducers ⋮ Equational Weighted Tree Transformations with Discounting ⋮ Survey: Weighted Extended Top-Down Tree Transducers Part III — Composition ⋮ On Müller context-free grammars ⋮ Hierarchies of tree series transformations ⋮ Automata on finite trees ⋮ A property of left-linear rewrite systems preserving recognizability ⋮ A comparison of tree transductions defined by monadic second order logic and by attribute grammars ⋮ Recognizable formal series on trees and cofree coalgebraic systems ⋮ Interconvertibility of a class of set constraints and context-free-language reachability ⋮ Restricted ground tree transducers ⋮ Re-describing an algorithm by Hopcroft ⋮ Deciding path size of nondeterministic (and input-driven) pushdown automata ⋮ Uniform and nonuniform recognizability. ⋮ Derivation trees of ground term rewriting systems. ⋮ Macro tree transducers, attribute grammars, and MSO definable tree translations. ⋮ Sequentiality, monadic second-order logic and tree automata. ⋮ The combinator S ⋮ Ordering constraints over feature trees expressed in second-order monadic logic. ⋮ Pushdown tree automata, algebraic tree systems, and algebraic tree series ⋮ Recognizable tree-languages and nonlinear morphisms ⋮ Iterated relabeling tree transducers ⋮ Decidability of EDT0L structural equivalence ⋮ The alphabetic complexity in homomorphic definitions of word, tree and picture languages ⋮ Output string languages of compositions of deterministic macro tree transducers ⋮ On two families of forests ⋮ An operational and denotational approach to non-context-freeness ⋮ Ambiguity hierarchies for weighted tree automata

This page was built for publication: