Quasi-Monotonic Sequences: Theory, Algorithms and Applications

DOI10.1137/0608034zbMath0692.06011OpenAlexW1965038831MaRDI QIDQ3033808

Andrzej Ehrenfeucht, Jeffrey Haemer, David Haussler

Publication date: 1987

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0608034

zbMATH Keywords

algorithmsalgebraic theoryfactorizationsamortized complexityordered treesLyndon wordsballot problemconvex hulls in two dimensionscyclic conjugatesTrip Around the Moon

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Enumerative combinatorics (05A99) Convex sets in (2) dimensions (including convex curves) (52A10) Ordered structures (06F99) Discrete mathematics in relation to computer science (68R99)

Related Items

Lyndon + Christoffel = digitally convex, Grammatical codes of trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On some results of Takacs in ballot problems
• Another efficient algorithm for convex hulls in two dimensions
• Enumerations of ordered trees
• On a problem of cyclic permutations of integers
• The design and analysis of a new hybrid sorting algorithm
• On generalised Catalan numbers
• Divide and conquer for linear expected time
• A Combinatorial Lemma and Its Application to Probability Theory
• Factorizing words over an ordered alphabet
• A Lower Bound to Finding Convex Hulls
• An O(n log n) unidirectional distributed algorithm for extrema finding in a circle
• Some Catalan Correspondences
• An optimal real-time algorithm for planar convex hulls
• An Elementary Evaluation of the Catalan Numbers
• Generating Trees and Other Combinatorial Objects Lexicographically
• Ballot problems
• A Combinatorial Theorem for Partial Sums