Weighted grammars and Kleene's theorem

DOI10.1016/0020-0190(87)90190-6MaRDI QIDQ1090465zbMATH OpenOpenAlexFDO

Authors Athanasios Alexandrakis, Symeon Bozapalidis

Publication date 1987

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(87)90190-6

zbMATH Keywords

formal power series on treesweighted regular tree grammar

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Review text

The authors extend Kleene's theorem to formal power series on trees: a series is regular if and only if it is recognizable. The main tool is the notion of weighted regular tree grammar.

Recommendations

• A Kleene theorem for weighted tree automata
• Kleene's theorem for weighted tree-automata.
• Kleene type results for weighted tree automata
• A Kleene theorem for weighted tree automata over distributive multioperator monoids
• A Kleene theorem for weighted tree automata over tree valuation monoids

Cites work

• scientific article; zbMATH DE number 3615891 (Why is no real title available?)
• scientific article; zbMATH DE number 1456950 (Why is no real title available?)
• Recognizable formal power series on trees

Cited in

(36)

• On two families of forests
• A Kleene theorem for weighted tree automata
• Characterizations of recognizable weighted tree languages by logic and bimorphisms
• Finite sequentiality of unambiguous max-plus tree automata
• Principal abstract families of weighted tree languages
• Finite-image property of weighted tree automata over past-finite monotonic strong bimonoids
• Approximated determinisation of weighted tree automata
• Sequentiality of group-weighted tree automata
• A Kleene theorem for weighted tree automata over tree valuation monoids
• Weighted logics for unranked tree automata
• Weighted grammar tools: The GRM library
• Kleene type results for weighted tree automata
• A unifying Kleene theorem for weighted finite automata
• Weighted Tree Automata over Valuation Monoids and Their Characterization by Weighted Logics
• Equational weighted tree transformations with discounting
• Survey: Weighted extended top-down tree transducers. III. Composition
• Valuations of weighted automata: doing it in a rational way
• Weighted Deductive Parsing and Knuth's Algorithm
• Nonassociativity à la Kleene
• DECOMPOSITION OF WEIGHTED MULTIOPERATOR TREE AUTOMATA
• scientific article; zbMATH DE number 4039338 (Why is no real title available?)
• -Treeautomata and their relation to weighted context-free grammars
• scientific article; zbMATH DE number 2040324 (Why is no real title available?)
• scientific article; zbMATH DE number 2040902 (Why is no real title available?)
• Crisp-determinization of weighted tree automata over strong bimonoids
• Weighted tree generating regular systems over strong bimonoids with reduction semantics
• Kleene's theorem for weighted tree-automata.
• An ambiguity hierarchy of weighted context-free grammars
• A Comparison of Sets of Recognizable Weighted Tree Languages Over Specific Sets of Bounded Lattices
• Finite sequentiality of finitely ambiguous max-plus tree automata
• Rational weighted tree languages with storage
• Finite sequentiality of finitely ambiguous max-plus tree automata
• A Büchi-like theorem for weighted tree automata over multioperator monoids
• Equational weighted tree transformations
• A note on cut-worthiness of recognizable tree series
• Weighted monadic Datalog

This page was built for publication: Weighted grammars and Kleene's theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1090465)