Navegar

Colección

Datos Estadísticas

Artículo

Abriola, S.; Figueira, S.; Senno, G. "Linearizing bad sequences: Upper bounds for the product and majoring well quasi-orders" (2012) 19th International Workshop on Logic, Language, Information and Computation, WoLLIC 2012. 7456 LNCS:110-126
La versión final de este artículo es de uso interno. El editor solo permite incluir en el repositorio el artículo en su versión post-print. Por favor, si usted la posee enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

Well quasi-orders (wqo's) are an important mathematical tool for proving termination of many algorithms. Under some assumptions upper bounds for the computational complexity of such algorithms can be extracted by analyzing the length of controlled bad sequences. We develop a new, self-contained study of the length of bad sequences over the product ordering of ℕ n , which leads to known results but with a much simpler argument. We also give a new tight upper bound for the length of the longest controlled descending sequence of multisets of ℕ n, and use it to give an upper bound for the length of controlled bad sequences in the majoring ordering of sets of tuples. We apply this upper bound to obtain complexity upper bounds for decision procedures of automata over data trees. In both cases the idea is to linearize bad sequences, i.e. transform them into a descending one over a well-order for which upper bounds can be more easily handled. © 2012 Springer-Verlag.

Registro:

Documento: Artículo
Título:Linearizing bad sequences: Upper bounds for the product and majoring well quasi-orders
Autor:Abriola, S.; Figueira, S.; Senno, G.
Ciudad:Buenos Aires
Filiación:Dto. Matemática, FCEN, Universidad de Buenos Aires, Argentina
Dto. Computación, FCEN, Universidad de Buenos Aires, Argentina
CONICET, Argentina
Palabras clave:Data tree; Decision procedure; Mathematical tools; Multi-sets; Product ordering; Upper Bound; Algorithms; Trees (mathematics)
Año:2012
Volumen:7456 LNCS
Página de inicio:110
Página de fin:126
DOI: http://dx.doi.org/10.1007/978-3-642-32621-9_9
Título revista:19th International Workshop on Logic, Language, Information and Computation, WoLLIC 2012
Título revista abreviado:Lect. Notes Comput. Sci.
ISSN:03029743
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v7456LNCS_n_p110_Abriola

Referencias:

  • Abriola, S.A., (2011) Sobre la Longitud de Las Secuencias Malas Controladas en Cuasi-órdenes Buenos, , MSc thesis, Universidad de Buenos Aires, Argentina
  • Clote, P., On the finite containment problem for Petri nets (1986) Theoretical Computer Science, 43, pp. 99-105
  • Dershowitz, N., Manna, Z., Proving termination with multiset orderings (1979) Communications of the ACM, 22 (8), pp. 465-476
  • Figueira, D., (2010) Reasoning on Words and Trees with Data, , PhD thesis, Laboratoire Spécification et Vérification, ENS Cachan, France December
  • Figueira, D., Figueira, S., Schmitz, S., Schnoebelen, P., Ackermannian and primitive-recursive bounds with Dickson's lemma (2011) LICS, pp. 269-278
  • Finkel, A., Schnoebelen, P., Well-structured transition systems everywhere? (2001) Theoretical Computer Science, 256 (1-2), pp. 63-92
  • Harwood, W., Moller, F., Setzer, A., Weak Bisimulation Approximants (2006) LNCS, 4207, pp. 365-379. , Ésik, Z. (ed.) CSL 2006. Springer, Heidelberg
  • Jancar, P., A note on well quasi-orderings for powersets (1999) Information Processing Letters, 72 (5-6), pp. 155-160
  • Jurdziński, M., Lazić, R., Alternating automata on data trees and XPath satisfiability (2011) ACM Transactions on Computational Logic (TOCL), 12 (3), p. 19
  • Löb, M.H., Wainer, S.S., Hierarchies of number theoretic functions, I (1970) Archive for Mathematical Logic, 13, pp. 39-51
  • McAloon, K., Petri nets and large finite sets (1984) Theoretical Computer Science, 32 (1-2), pp. 173-183
  • Péter, R., (1967) Recursive Functions, , Academic Press
  • Schmitz, S., Schnoebelen, P., Multiply-Recursive Upper Bounds with Higman's Lemma (2011) LNCS, 6756, pp. 441-452. , Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. Springer, HeidelbergA4 - Univ. Buenos Aires, Fac. Cienc. Exactas Nat., Dep. Comput.; Universidad de Buenos Aires, Facultad de Ciencias Economicas; Universidade Federal de Pernambuco, Centro de Informatica; Interest Group in Pure and Applied Logics (IGPL); Association for Logic, Language and Information (FoLLI)

Citas:

---------- APA ----------
Abriola, S., Figueira, S. & Senno, G. (2012) . Linearizing bad sequences: Upper bounds for the product and majoring well quasi-orders. 19th International Workshop on Logic, Language, Information and Computation, WoLLIC 2012, 7456 LNCS, 110-126.
http://dx.doi.org/10.1007/978-3-642-32621-9_9
---------- CHICAGO ----------
Abriola, S., Figueira, S., Senno, G. "Linearizing bad sequences: Upper bounds for the product and majoring well quasi-orders" . 19th International Workshop on Logic, Language, Information and Computation, WoLLIC 2012 7456 LNCS (2012) : 110-126.
http://dx.doi.org/10.1007/978-3-642-32621-9_9
---------- MLA ----------
Abriola, S., Figueira, S., Senno, G. "Linearizing bad sequences: Upper bounds for the product and majoring well quasi-orders" . 19th International Workshop on Logic, Language, Information and Computation, WoLLIC 2012, vol. 7456 LNCS, 2012, pp. 110-126.
http://dx.doi.org/10.1007/978-3-642-32621-9_9
---------- VANCOUVER ----------
Abriola, S., Figueira, S., Senno, G. Linearizing bad sequences: Upper bounds for the product and majoring well quasi-orders. Lect. Notes Comput. Sci. 2012;7456 LNCS:110-126.
http://dx.doi.org/10.1007/978-3-642-32621-9_9