Normality and Automata | ||
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Université Paris Diderot - Paris 7 | |
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.contributor.author | Becher, Veronica Andrea | |
| dc.contributor.author | Carton, Olivier | |
| dc.contributor.author | Heiber, Pablo Ariel | |
| dc.date.issued | 2015-12 | |
| dc.description.abstract | We prove that finite-state transducers with injective behavior, deterministic or not, real-time or not, with no extra memory or a single counter, cannot compress any normal word. We exhaust all combinations of determinism, real-time, and additional memory in the form of counters or stacks, identifying which models can compress normal words. The case of deterministic push-down transducers is the only one still open. We also present results on the preservation of normality by selection with finite automata. Complementing Agafonov's theorem for prefix selection, we show that suffix selection preserves normality. However, there are simple two-sided selection rules that do not. | es |
| dc.description.fil | Fil: Becher, Veronica Andrea. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | |
| dc.description.fil | Fil: Carton, Olivier. Université Paris Diderot - Paris 7; Francia | |
| dc.description.fil | Fil: Heiber, Pablo Ariel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Becher, Veronica Andrea; Carton, Olivier; Heiber, Pablo Ariel; Normality and Automata; Academic Press Inc Elsevier Science; Journal of Computer and System Sciences; 81; 8; 12-2015; 1592-1613 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0022-0000 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/59876 | |
| dc.journal.number | 8 | es |
| dc.journal.pagination | 1592-1613 | es |
| dc.journal.pais | Estados Unidos | es |
| dc.journal.title | Journal of Computer and System Sciences | es |
| dc.journal.volume | 81 | es |
| dc.language.iso | eng | es |
| dc.publisher | Academic Press Inc Elsevier Science | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.jcss.2015.04.007 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S002200001500046X | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/2.5/ar/ | * |
| dc.subject | Finite Automata | es |
| dc.subject | Non-Deterministic Automata | es |
| dc.subject | Normal Numbers | es |
| dc.subject.classification | Ciencias de la Computación | es |
| dc.subject.classification | Ciencias de la Computación e Información | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | Normality and Automata | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.a0956dfc-1ad6-4482-a18f-339e2d2f3474_A.pdf
- Tamaño:
- 827.79 KB
- Formato:
- Adobe Portable Document Format