Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Completely Reachable Automata Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Heapability, Interactive Particle Systems, Partial Orders: Results and Open Problems

Authors : Gabriel Istrate, Cosmin Bonchiş

Published in: Descriptional Complexity of Formal Systems

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We outline results and open problems concerning partitioning of integer sequences and partial orders into heapable subsequences (previously defined and established by Byers et al.).

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Completely Reachable Automata
next chapter Self-Verifying Finite Automata and Descriptional Complexity
Literature
1.
Byers, J., Heeringa, B., Mitzenmacher, M., Zervas, G.: Heapable sequences and subseqeuences. In: Proceedings of ANALCO, pp. 33–44 (2011)
2.
Romik, D.: The Surprising Mathematics of Longest Increasing Subsequences, vol. 4. Cambridge University Press, New York (2015)MATH
3.
Istrate, G., Bonchiş, C.: Partition into heapable sequences, heap tableaux and a multiset extension of hammersley’s process. In: Cicalese, F., Porat, E., Vaccaro, U. (eds.) CPM 2015. LNCS, vol. 9133, pp. 261–271. Springer, Heidelberg (2015)CrossRef
4.
5.
6.
7.
Brightwell, G.: Models of random partial orders. In: Surveys in Combinatorics, pp. 53–83 (1993)
8.
9.
Schrijver, A.: Theory of linear and integer programming. Wiley, New York (1998)MATH
10.
Hammersley, J.M., et al.: A few seedlings of research. In: Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Theory of Statistics (1972)
11.
12.
Vershik, A., Kerov, S.V.: Asymptotics of plancherel measure of symmetrical group and limit form of Young tables. Doklady Akademii Nauk SSSR 233(6), 1024–1027 (1977)MathSciNetMATH
13.
Aldous, D., Diaconis, P.: Hammersley’s interacting particle process and longest increasing subsequences. Probab. Theory Relat. Fields 103(2), 199–213 (1995)MathSciNetCrossRefMATH
14.
15.
Bollobás, B., Winkler, P.: The longest chain among random points in euclidean space. Proc. Am. Math. Soc. 103(2), 347–353 (1988)MathSciNetCrossRefMATH
16.
Bollobás, B., Brightwell, G.: The height of a random partial order: Concentration of measure. Ann. Appl. Probab. 2(4), 1009–1018 (1992)MathSciNetCrossRefMATH
17.
Groeneboom, P.: Hydrodynamical methods for analyzing longest increasing subsequences. J. Comput. Appl. Math. 142(1), 83–105 (2002)MathSciNetCrossRefMATH
18.
19.
20.
Cardinal, J., Fiorini, S., van Assche, G.: On minimum entropy graph colorings. In: Proceedings of ISIT 2004, The International Symposium on Information Theory, p. 43 (2004)
21.
Halperin, E., Karp, R.: The minimum entropy set cover problem. Theor. Comput. Sci. 348(2–3), 340–350 (2005)MathSciNetMATH
22.
23.
24.
Cardinal, J., Fiorini, S., Joret, G.: Minimum entropy combinatorial optimization problems. In: Ambos-Spies, K., Löwe, B., Merkle, W. (eds.) CiE 2009. LNCS, vol. 5635, pp. 79–88. Springer, Heidelberg (2009)CrossRef
25.
26.
Istrate, G., Bonchiş, C., Dinu, L.P.: The minimum entropy submodular set cover problem. In: Dediu, A.-H., Janoušek, J., Martín-Vide, C., Truthe, B. (eds.) LATA 2016. LNCS, vol. 9618, pp. 295–306. Springer, Heidelberg (2016)CrossRef
27.
28.
Doshi, V., Shah, D., Médard, M., Effros, M.: Functional compression through graph coloring. IEEE Trans. Inf. Theory 56(8), 3901–3917 (2010)MathSciNetCrossRef
29.
Barbay, J., Munro, J.I.: Succinct encoding of permutations : Applications to text indexing. In: Encyclopedia of Algorithms, pp. 915–919. Springer (2008)
30.
Metadata
Title
Heapability, Interactive Particle Systems, Partial Orders: Results and Open Problems
Authors
Gabriel Istrate
Cosmin Bonchiş
Copyright Year
2016
Book
Descriptional Complexity of Formal Systems

Print ISBN: 978-3-319-41113-2

Electronic ISBN: 978-3-319-41114-9

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-41114-9_2

Premium Partner

    Image Credits