Repositorio Institucional
Repositorio Institucional
CONICET Digital
  • Inicio
  • EXPLORAR
    • AUTORES
    • DISCIPLINAS
    • COMUNIDADES
  • Estadísticas
  • Novedades
    • Noticias
    • Boletines
  • Ayuda
    • General
    • Datos de investigación
  • Acerca de
    • CONICET Digital
    • Equipo
    • Red Federal
  • Contacto
JavaScript is disabled for your browser. Some features of this site may not work without it.
  • INFORMACIÓN GENERAL
  • RESUMEN
  • ESTADISTICAS
 
Artículo

Linearizing well quasi-orders and bounding the length of bad sequences

Abriola, Sergio AlejandroIcon ; Figueira, SantiagoIcon ; Senno, Gabriel IgnacioIcon
Fecha de publicación: 10/2015
Editorial: Elsevier Science
Revista: Theoretical Computer Science
ISSN: 0304-3975
Idioma: Inglés
Tipo de recurso: Artículo publicado
Clasificación temática:
Matemática Pura

Resumen

We study the length functions of controlled bad sequences over some well quasi-orders (wqo's) and classify them in the Fast Growing Hierarchy. We develop a new and self-contained study of the length of bad sequences over the disjoint product in Nn (Dickson's Lemma), which leads to recently discovered upper bounds but through a simpler argument. We also give a tight upper bound for the length of controlled decreasing sequences of multisets of Nn with the underlying lexicographic ordering, and use it to give an upper bound for the length of controlled bad sequences in the majoring ordering with the underlying disjoint product ordering. We apply this last result to attain complexity upper bounds for the emptiness problem of itca and atra automata. For the case of the product and majoring wqo's the idea is to linearize bad sequences, i.e. to transform a bad sequence over a wqo into a decreasing one over a well-order, for which upper bounds can be more easily handled.
Palabras clave: Controlled Bad Sequence , Fast Growing Hierarchy , Lexicographic Ordering , Majoring Ordering , Multiset Ordering , Product Ordering , Well Quasi-Order
Ver el registro completo
 
Archivos asociados
Thumbnail
 
Tamaño: 578.1Kb
Formato: PDF
.
Descargar
Licencia
info:eu-repo/semantics/openAccess Excepto donde se diga explícitamente, este item se publica bajo la siguiente descripción: Atribución-NoComercial-SinDerivadas 2.5 Argentina (CC BY-NC-ND 2.5 AR)
Identificadores
URI: http://hdl.handle.net/11336/59573
URL: https://www.sciencedirect.com/science/article/pii/S0304397515006337
DOI: http://dx.doi.org/10.1016/j.tcs.2015.07.012
Colecciones
Articulos(OCA CIUDAD UNIVERSITARIA)
Articulos de OFICINA DE COORDINACION ADMINISTRATIVA CIUDAD UNIVERSITARIA
Citación
Abriola, Sergio Alejandro; Figueira, Santiago; Senno, Gabriel Ignacio; Linearizing well quasi-orders and bounding the length of bad sequences; Elsevier Science; Theoretical Computer Science; 603; 10-2015; 3-22
Compartir
Altmétricas
 

Items relacionados

Mostrando titulos relacionados por título, autor y tema.

  • Artículo An update on the distribution and nomenclature of fleas (Order Siphonaptera) of bats (Order Chiroptera) and rodents (Order Rodentia) from La Rioja Province, Argentina
    Lopez Berrizbeitia, Maria Fernanda ; Sánchez, Rocío Tatiana ; Barquez, Ruben Marcos ; Díaz, María Mónica (Pensoft Publishers, 2017-06)
  • Artículo Orden global, orden irracional: El Protocolo de Kyoto, el Mecanismo de Desarrollo Limpio y los bonos de carbono; algunos ejemplos empíricos del caso argentino
    Gomez Lende, Sebastian (Universidade Federal de Pernambuco. Departamento de Ciências Geográficas, 2014-12)
  • Artículo High order eigenvalues for the Helmholtz equation in complicated non-tensor domains through Richardson extrapolation of second order finite differences
    Amore, Paolo; Fernández, Francisco Marcelo ; Boyd, John. P.; Boris, Rösler (Academic Press Inc Elsevier Science, 2016-05)
Enviar por e-mail
Separar cada destinatario (hasta 5) con punto y coma.
  • Facebook
  • X Conicet Digital
  • Instagram
  • YouTube
  • Sound Cloud
  • LinkedIn

Los contenidos del CONICET están licenciados bajo Creative Commons Reconocimiento 2.5 Argentina License

https://www.conicet.gov.ar/ - CONICET

Inicio

Explorar

  • Autores
  • Disciplinas
  • Comunidades

Estadísticas

Novedades

  • Noticias
  • Boletines

Ayuda

Acerca de

  • CONICET Digital
  • Equipo
  • Red Federal

Contacto

Godoy Cruz 2290 (C1425FQB) CABA – República Argentina – Tel: +5411 4899-5400 repositorio@conicet.gov.ar
TÉRMINOS Y CONDICIONES