The basic properties of distributivity and deletion of pure and o-substitution are investigated. The obtained results are applied to show preservation of recognizability in a number of surprising cases. It is proved that linear and recognizable tree series are closed under o-substitution provided that the underlying semiring is commutative, continuous, and additively idempotent. It is known that, in general, pure substitution does not preserve recognizability (not even for linear target tree series), but it is shown that recognizable linear probability distributions (represented as tree series) are closed under pure substitution.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa.de:bsz:14-qucosa-99193 |
| Date | 12 November 2012 |
| Creators | Maletti, Andreas |
| Contributors | Technische Universität Dresden, Fakultät Informatik |
| Publisher | Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | doc-type:workingPaper |
| Format | application/pdf |
| Relation | dcterms:isPartOf:Technische Berichte / Technische Universität Dresden, Fakultät Informatik ; 2006,05 (TUD-FI06-05 — Oktober 2006) |
Page generated in 0.0016 seconds