|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 11 van 25 gevonden artikelen
| Titel: |
Nondeterministic Bimachines and Rational Relations with Finite Codomain |
| Auteur: |
Santean, Nicolae Yu, Sheng |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 73 (2006) nr. 1-2 pagina's 237-264 |
| Jaar: |
2006-08-28 |
| Inhoud: |
Bimachines are important conceptual tools used for the characterization of rational word functions (realized by single-valued transducers). Despite the attention received in the past, these sequential machines are far from being exhaustively studied. A natural question which has not been addressed so far is what family of transductions are realized by bimachines that operate nondeterministically. We show that these machines characterize input-unambiguous (IU) rational transductions, i.e., those transductions that can be written as a composition of rational functions and finite substitutions. Two more families of rational transductions are defined and related in a natural way to IU transductions: input-deterministic transductions and rational transductions with finite codomain (FC). We have shown that FC transductions are recognizable and that they can be expressed as finite union of subsequential functions. Moreover, they can be realized by nondeterministic bimachines. Finally, we have defined the so called restricted nondeterministic bimachines and shown that, surprisingly, they are more powerful than nondeterministic bimachines: they characterize exactly the family of finitely ambiguous rational transductions. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 11 van 25 gevonden artikelen
| << vorige | volgende >> |