How to Correctly Prune Tropical Trees

DOI10.1007/978-3-642-14128-7_10MaRDI QIDQ3582700zbMATH OpenOpenAlexFDO

Authors Jean-Vincent Loddo, Luca Saiu

Publication date 24 August 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1005.1475

zbMATH Keywords

alpha-beta pruningcombinatorial gamelogicparsingrational gamesearchterm rewritingtropical algebratropical game

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Combinatorial games (91A46) Applications of game theory (91A80)

Abstract: We present tropical games, a generalization of combinatorial min-max games based on tropical algebras. Our model breaks the traditional symmetry of rational zero-sum games where players have exactly opposed goals (min vs. max), is more widely applicable than min-max and also supports a form of pruning, despite it being less effective than alpha-beta. Actually, min-max games may be seen as particular cases where both the game and its dual are tropical: when the dual of a tropical game is also tropical, the power of alpha-beta is completely recovered. We formally develop the model and prove that the tropical pruning strategy is correct, then conclude by showing how the problem of approximated parsing can be modeled as a tropical game, profiting from pruning.

Recommendations

• How to prune a horseshoe
• Tropical geometric variation of tree shapes
• Tree topologies along a tropical line segment
• Fringe analysis of plane trees related to cutting and pruning
• Pruning moves
• Fuzzy decision aid for pruning forest trees
• A guide to tropicalizations
• Growing conditioned trees
• scientific article; zbMATH DE number 4213470

This page was built for publication: How to Correctly Prune Tropical Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3582700)