Language and automata theory and applications

Adrian-Horia Dediu

Carlos Martín-Vide

José-Luis Sierra-Rodríguez

Bianca Truthe (Eds.)

123

LNCS 8370

8th International Conference, LATA 2014

Madrid, Spain, March 10-14, 2014

Proceedings

Language and

Automata Theory

and Applications

Lecture Notes in Computer Science 8370

Commenced Publication in 1973

Founding and Former Series Editors:

Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen

Editorial Board

David Hutchison

Lancaster University, UK

Takeo Kanade

Carnegie Mellon University, Pittsburgh, PA, USA

Josef Kittler

University of Surrey, Guildford, UK

Jon M. Kleinberg

Cornell University, Ithaca, NY, USA

Alfred Kobsa

University of California, Irvine, CA, USA

Friedemann Mattern

ETH Zurich, Switzerland

John C. Mitchell

Stanford University, CA, USA

Moni Naor

Weizmann Institute of Science, Rehovot, Israel

Oscar Nierstrasz

University of Bern, Switzerland

C. Pandu Rangan

Indian Institute of Technology, Madras, India

Bernhard Steffen

TU Dortmund University, Germany

Madhu Sudan

Microsoft Research, Cambridge, MA, USA

Demetri Terzopoulos

University of California, Los Angeles, CA, USA

Doug Tygar

University of California, Berkeley, CA, USA

Gerhard Weikum

Max Planck Institute for Informatics, Saarbruecken, Germany

Adrian-Horia Dediu Carlos Martín-Vide

José-Luis Sierra-Rodríguez BiancaTruthe (Eds.)

Language and

Automata Theory

and Applications

8th International Conference, LATA 2014

Madrid, Spain, March 10-14, 2014

Proceedings

13

Volume Editors

Adrian-Horia Dediu

Rovira i Virgili University, Research Group on Mathematical Linguistics

Avinguda Catalunya, 35, 43002 Tarragona, Spain

E-mail: [email protected]

Carlos Martín-Vide

Rovira i Virgili University, Research Group on Mathematical Linguistics

Avinguda Catalunya, 35, 43002 Tarragona, Spain

E-mail: [email protected]

José-Luis Sierra-Rodríguez

Complutense University of Madrid, School of Computer Science

Department of Software Engineering and Artificial Intelligence

Profesor José García Santesmases, 9, 28040 Madrid, Spain

E-mail: [email protected]

Bianca Truthe

Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik

Institut für Wissens- und Sprachverarbeitung

Universitätsplatz 2, 39106 Magdeburg, Germany

E-mail: [email protected]

ISSN 0302-9743 e-ISSN 1611-3349

ISBN 978-3-319-04920-5 e-ISBN 978-3-319-04921-2

DOI 10.1007/978-3-319-04921-2

Springer Cham Heidelberg New York Dordrecht London

Library of Congress Control Number: 2014930764

LNCS Sublibrary: SL 1 – Theoretical Computer Science and General Issues

© Springer International Publishing Switzerland 2014

This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of

the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation,

broadcasting, reproduction on microfilms or in any other physical way, and transmission or information

storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology

now known or hereafter developed. Exempted from this legal reservation are brief excerpts in connection

with reviews or scholarly analysis or material supplied specifically for the purpose of being entered and

executed on a computer system, for exclusive use by the purchaser of the work. Duplication of this publication

or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher’s location,

in ist current version, and permission for use must always be obtained from Springer. Permissions for use

may be obtained through RightsLink at the Copyright Clearance Center. Violations are liable to prosecution

under the respective Copyright Law.

The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication

does not imply, even in the absence of a specific statement, that such names are exempt from the relevant

protective laws and regulations and therefore free for general use.

While the advice and information in this book are believed to be true and accurate at the date of publication,

neither the authors nor the editors nor the publisher can accept any legal responsibility for any errors or

omissions that may be made. The publisher makes no warranty, express or implied, with respect to the

material contained herein.

Typesetting: Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India

Printed on acid-free paper

Springer is part of Springer Science+Business Media (www.springer.com)

Preface

These proceedings contain the papers that were presented at the 8th Interna￾tional Conference on Language and Automata Theory and Applications (LATA

2014), held in Madrid, Spain, during March 10–14, 2014.

The scope of LATA is rather broad, including: algebraic language theory;

algorithms for semi-structured data mining; algorithms on automata and words;

automata and logic; automata for system analysis and program verification; au￾tomata, concurrency, and Petri nets; automatic structures; cellular automata;

codes; combinatorics on words; compilers; computability; computational com￾plexity; data and image compression; decidability issues on words and languages;

descriptional complexity; digital libraries and document engineering; DNA and

other models of bio-inspired computing; foundations of finite state technology;

foundations of XML; fuzzy and rough languages; grammars (Chomsky hierarchy,

contextual, unification, categorial, etc.); grammatical inference and algorithmic

learning; graphs and graph transformation; language varieties and semigroups;

language-based cryptography; language-theoretic foundations of artificial intelli￾gence and artificial life; natural language and speech automatic processing; par￾allel and regulated rewriting; parsing; patterns; power series; quantum, chemical

and optical computing; semantics; string and combinatorial issues in computa￾tional biology and bioinformatics; string processing algorithms; symbolic dynam￾ics; symbolic neural networks; term rewriting; transducers; trees, tree languages

and tree automata; weighted automata.

LATA 2014 received 116 submissions. Each one was reviewed by three Pro￾gram Committee members, many of whom consulted with external referees. After

a thorough and vivid discussion phase, the committee decided to accept 45 pa￾pers (which represents an acceptance rate of 38.79%). The conference program

also included four invited talks and one invited tutorial. Part of the success in

the management of such a large number of submissions is due to the excellent

facilities provided by the EasyChair conference management system.

We would like to thank all invited speakers and authors for their contri￾butions, the Program Committee and the reviewers for their cooperation, and

Springer for its very professional publishing work.

December 2013 Adrian-Horia Dediu

Carlos Mart´ın-Vide

Jos´e-Luis Sierra

Bianca Truthe

Organization

LATA 2014 was organized by the Research Group on Implementation of Language￾Driven Software and Applications, ILSA, from Complutense University of Madrid

and the Research Group on Mathematical Linguistics, GRLMC, from Rovira i

Virgili University, Tarragona.

Program Committee

Dana Angluin Yale University at New Haven, USA

Eugene Asarin Paris Diderot University, France

Jos Baeten CWI, Amsterdam, The Netherlands

Christel Baier Dresden University of Technology, Germany

Jin-Yi Cai University of Wisconsin at Madison, USA

Marek Chrobak University of California at Riverside, USA

Andrea Corradini University of Pisa, Italy

Mariangiola Dezani University of Turin, Italy

Ding-Zhu Du University of Texas at Dallas, USA

Michael R. Fellows Charles Darwin University, Darwin, Australia

J¨org Flum University of Freiburg, Germany

Nissim Francez Technion-Israel Institute of Technology, Haifa,

Israel

J¨urgen Giesl RWTH Aachen University, Germany

Annegret Habel University of Oldenburg, Germany

Kazuo Iwama Kyoto University, Japan

Sampath Kannan University of Pennsylvania, Philadelphia, USA

Ming-Yang Kao Northwestern University, Evanston, USA

Deepak Kapur University of New Mexico, Albuquerque, USA

Joost-Pieter Katoen RWTH Aachen University, Germany

S. Rao Kosaraju Johns Hopkins University, Baltimore, USA

Evangelos Kranakis Carleton University, Ottawa, Canada

Gad M. Landau University of Haifa, Israel

Andrzej Lingas Lund University, Sweden

Jack Lutz Iowa State University, Ames, USA

Ian Mackie Ecole Polytechnique, Palaiseau, France ´

Carlos Mart´ın-Vide Rovira i Virgili University, Tarragona, Spain

Giancarlo Mauri University of Milano-Bicocca, Milan, Italy

Faron G. Moller Swansea University, UK

Paliath Narendran University at Albany, SUNY, USA

Enno Ohlebusch Ulm University, Germany

Helmut Prodinger Stellenbosch University, South Africa

Jean-Fran¸cois Raskin Free University of Brussels, Belgium

VIII Organization

Wolfgang Reisig Humboldt University, Berlin, Germany

Marco Roveri Bruno Kessler Foundation, Trento, Italy

Micha¨el Rusinowitch LORIA, Nancy, France

Yasubumi Sakakibara Keio University, Japan

Davide Sangiorgi University of Bologna, Italy

Colin Stirling University of Edinburgh, UK

Jianwen Su University of California at Santa Barbara, USA

Jean-Pierre Talpin IRISA, Rennes, France

Andrzej Tarlecki University of Warsaw, Poland

Rick Thomas University of Leicester, UK

Sophie Tison University of Lille 1, France

Rob van Glabbeek NICTA, Sydney, Australia

Helmut Veith Vienna University of Technology, Austria

External Reviewers

Aldinucci, Marco

Amit, Mika

Anantharaman, Siva

Arana, Andrew

Artale, Alessandro

Beccuti, Marco

Bednarczyk, Marek A.

Belkhir, Walid

Beller, Timo

Bernardinello, Luca

Blunsom, Phil

Bollig, Benedikt

Bouchard, Christopher

Brenguier, Romain

Bruni, Roberto

Carle, Benjamin

Chaiken, Seth

Chrz

astowski-Wachtel, Piotr

Clemente, Lorenzo

Dang, Zhe

Dehnert, Christian

Delbot, Fran¸cois

de’Liguoro, Ugo

Dennunzio, Alberto

Devillers, Raymond

Didier, Gilles

Dubslaff, Clemens

Fat`es, Nazim

Filiot, Emmanuel

Flick, Nils Erik

Floderus, Peter

Frosini, Andrea

Fuhs, Carsten

Furia, Carlo A.

Gadducci, Fabio

Genet, Thomas

Gero, Kimberly

Gierds, Christian

Griggio, Alberto

Haar, Stefan

Hagge Cording, Patrick

Hai, Zhao

Hertrampf, Ulrich

Hibbs, Peter

Ibarra, Oscar H.

Iosif, Radu

Joosten, Joost J.

Joshi, Prachi

Kaminski, Michael

Kari, Jarkko

Kestler, Hans

Khomenko, Victor

Klein, Joachim

Kl¨uppelholz, Sascha

Kowaluk, Miroslaw

Kˇret´ınsk´y, Jan

Organization IX

Krishnamoorthy, Mukkai

Kutsia, Temur

Lecroq, Thierry

Leporati, Alberto

Levcopoulos, Christos

Linker, Sven

Lundell, Eva-Marta

Mairesse, Jean

Manea, Florin

Martyugin, Pavel

Mayr, Richard

Mazza, Damiano

Minkov, Einat

Moelle, Andre

Monmege, Benjamin

Moreira, Nelma

Mover, Sergio

Mukund, Madhavan

M¨uller, David

Naldi, Aur´elien

Nepomnyachiy, Sergey

Niehren, Joachim

N´u˜nez Queija, Rudesindo

Palano, Beatrice

Paparo, Omer

Persson, Mia

Pin, Jean-Eric ´

Plandowski, Wojciech

Porreca, Antonio E.

Pr¨ufer, Robert

Radke, Hendrik

Ranise, Silvio

Roos, Yves

Rozenberg, Liat

Sammartino, Matteo

Sankowski, Piotr

Sankur, Ocan

Schneider-Kamp, Peter

Servais, Fr´ed´eric

Shavrukov, Volodya

Shoukourian, Hayk

Shukla, Sandeep

Sledneu, Dzmitry

Sokol, Dina

Sun, Yutian

S¨urmeli, Jan

Swaminathan, Mani

Szczuka, Marcin

Tarasenko, Sergey

Thomas, Wolfgang

Titov, Ivan

Tonetta, Stefano

Tuosto, Emilio

Turuani, Mathieu

Valiron, Benoˆıt

Vandin, Andrea

Vigneron, Laurent

Vinju, Jurgen

Vouillon, J´erˆome

Vuillon, Laurent

Wintner, Shuly

Organizing Committee

Adrian-Horia Dediu, Tarragona

Ana Fern´andez-Pampill´on, Madrid

Carlos Mart´ın-Vide, Tarragona (Co-chair)

Antonio Sarasa, Madrid

Jos´e-Luis Sierra, Madrid (Co-chair)

Bianca Truthe, Magdeburg

Lilica Voicu, Tarragona

Table of Contents

Invited Talks

A Brief History of Strahler Numbers ............................... 1

Javier Esparza, Michael Luttenberger, and Maximilian Schlund

On the Parikh Membership Problem for FAs, PDAs, and CMs ......... 14

Oscar H. Ibarra and Bala Ravikumar

Matchings, Random Walks, and Sampling ........................... 32

Sanjeev Khanna

Interprocedural Information Flow Analysis of XML Processors ......... 34

Helmut Seidl and M´at´e Kov´acs

Regular Papers

Computing Optimal Reachability Costs in Priced Dense-Timed

Pushdown Automata ............................................. 62

Parosh Aziz Abdulla, Mohamed Faouzi Atig, and Jari Stenman

Formulae for Polyominoes on Twisted Cylinders ..................... 76

Gadi Aleksandrowicz, Andrei Asinowski, Gill Barequet, and

Ronnie Barequet

Picture Codes with Finite Deciphering Delay ........................ 88

Marcella Anselmo, Dora Giammarresi, and Maria Madonia

Networks of Polarized Evolutionary Processors Are Computationally

Complete ....................................................... 101

Fernando Arroyo, Sandra G´omez Canaval, Victor Mitrana, and

S¸tefan Popescu

Two Double-Exponential Gaps for Automata with a Limited

Pushdown....................................................... 113

Zuzana Bedn´arov´a and Viliam Geffert

Covering Pairs in Directed Acyclic Graphs .......................... 126

Niko Beerenwinkel, Stefano Beretta, Paola Bonizzoni,

Riccardo Dondi, and Yuri Pirola

Efficient List-Based Computation of the String Subsequence Kernel .... 138

Slimane Bellaouar, Hadda Cherroun, and Djelloul Ziadi

XII Table of Contents

Channel Synthesis Revisited ....................................... 149

B´eatrice B´erard and Olivier Carton

Characterisation of the State Spaces of Live and Bounded Marked

Graph Petri Nets ................................................ 161

Eike Best and Raymond Devillers

Computing Depths of Patterns .................................... 173

Francine Blanchet-Sadri, Andrew Lohr, Sean Simmons, and

Brent Woodhouse

Solving Equations on Words with Morphisms and Antimorphisms ...... 186

Alexandre Blondin Mass´e, S´ebastien Gaboury, Sylvain Hall´e, and

Micha¨el Larouche

On the Arithmetics of Discrete Figures ............................. 198

Alexandre Blondin Mass´e, Amadou Makhtar Tall, and

Hugo Tremblay

On the List Update Problem with Advice ........................... 210

Joan Boyar, Shahin Kamali, Kim S. Larsen, and

Alejandro L´opez-Ortiz

Shift-Reduce Parsers for Transition Networks ........................ 222

Luca Breveglieri, Stefano Crespi Reghizzi, and Angelo Morzenti

Optimal Sorting Networks ........................................ 236

Daniel Bundala and Jakub Z´avodn´y

Satisfiability for MTL and TPTL over Non-monotonic Data Words ..... 248

Claudia Carapelle, Shiguang Feng, Oliver Fern´andez Gil, and

Karin Quaas

(k,l)-Unambiguity and Quasi-Deterministic Structures: An Alternative

for the Determinization ........................................... 260

Pascal Caron, Marianne Flouret, and Ludovic Mignot

Solutions to the Multi-dimensional Equal Powers Problem Constructed

by Composition of Rectangular Morphisms .......................... 273

Anton Cern´ ˇ y

Succinct Encodings of Graph Isomorphism .......................... 285

Bireswar Das, Patrick Scharpfenecker, and Jacobo Tor´an

Extremal Combinatorics of Reaction Systems ........................ 297

Alberto Dennunzio, Enrico Formenti, and Luca Manzoni

Stochastic k-Tree Grammar and Its Application in Biomolecular

Structure Modeling .............................................. 308

Liang Ding, Abdul Samad, Xingran Xue, Xiuzhen Huang,

Russell L. Malmberg, and Liming Cai

Table of Contents XIII

Weighted Automata and Logics for Infinite Nested Words ............. 323

Manfred Droste and Stefan D¨uck

Algebraic Tools for the Overlapping Tile Product .................... 335

Etienne Dubourg and David Janin

Reachability Analysis with State-Compatible Automata ............... 347

Bertram Felgenhauer and Ren´e Thiemann

Counting Models of Linear-Time Temporal Logic .................... 360

Bernd Finkbeiner and Hazem Torfah

ω-rational Languages: High Complexity Classes vs. Borel Hierarchy .... 372

Enrico Formenti, Markus Holzer, Martin Kutrib, and

Julien Provillard

On Context-Diverse Repeats and Their Incremental Computation ...... 384

Matthias Gall´e and Mat´ıas Tealdi

Ordered Counter-Abstraction: Refinable Subword Relations for

Parameterized Verification ........................................ 396

Pierre Ganty and Ahmed Rezine

On SAT Representations of XOR Constraints........................ 409

Matthew Gwynne and Oliver Kullmann

Minimal Triangulation Algorithms for Perfect Phylogeny Problems ..... 421

Rob Gysel

On Computability and Learnability of the Pumping Lemma Function... 433

Dariusz Kaloci´nski

Interval Temporal Logic Semantics of Box Algebra ................... 441

Hanna Klaudel, Maciej Koutny, and Zhenhua Duan

Are Good-for-Games Automata Good for Probabilistic

Model Checking? ................................................ 453

Joachim Klein, David M¨uller, Christel Baier, and Sascha Kl¨uppelholz

Top-Down Tree Edit-Distance of Regular Tree Languages ............. 466

Sang-Ki Ko, Yo-Sub Han, and Kai Salomaa

DFA with a Bounded Activity Level ................................ 478

Marius Konitzer and Hans Ulrich Simon

Learning Sequential Tree-to-Word Transducers....................... 490

Gr´egoire Laurence, Aur´elien Lemay, Joachim Niehren,

Slawek Staworko, and Marc Tommasi

XIV Table of Contents

Probabilistic Simulation for Probabilistic Data-Aware Business

Processes ....................................................... 503

Haizhou Li, Fran¸cois Pinet, and Farouk Toumani

Expressiveness of Dynamic Networks of Timed Petri Nets ............. 516

Mar´ıa Martos-Salgado and Fernando Rosa-Velardo

Distinguishing Pattern Languages with Membership Examples ......... 528

Zeinab Mazadi, Ziyuan Gao, and Sandra Zilles

Extended Two-Way Ordered Restarting Automata for Picture

Languages ...................................................... 541

Friedrich Otto and Frantiˇsek Mr´az

Weight-Reducing Hennie Machines and Their Descriptional

Complexity ..................................................... 553

Daniel Pr˚uˇsa

Computing with Catalan Families .................................. 565

Paul Tarau

Complexity of a Problem Concerning Reset Words for Eulerian Binary

Automata ....................................................... 576

Vojtˇech Vorel

Probabilistic ω-Regular Expressions ................................ 588

Thomas Weidner

On the State Complexity of Semi-quantum Finite Automata .......... 601

Shenggen Zheng, Jozef Gruska, and Daowen Qiu

Author Index .................................................. 613

A Brief History of Strahler Numbers

Javier Esparza, Michael Luttenberger, and Maximilian Schlund

Fakult¨at f¨ur Informatik, Technische Universit¨at M¨unchen, Germany

Abstract. The Strahler number or Horton-Strahler number of a tree,

originally introduced in geophysics, has a surprisingly rich theory. We

sketch some milestones in its history, and its connection to arithmetic ex￾pressions, graph traversing, decision problems for context-free languages,

Parikh’s theorem, and Newton’s procedure for approximating zeros of

differentiable functions.

1 The Strahler Number

In 1945, the geophysicist Robert Horton found it useful to associate a stream

order to a system of rivers (geophysicists seem to prefer the term ‘stream”) [20].

Unbranched fingertip tributaries are always designated as of order 1, trib￾utaries or streams of the 2d order receive branches or tributaries of the

1st order, but these only; a 3d order stream must receive one or more

tributaries of the 2d order but may also receive 1st order tributaries. A

4th order stream receives branches of the 3d and usually also of lower

orders, and so on.

Several years later, Arthur N. Strahler replaced this ambiguous definition by

a simpler one, very easy to compute [26]:

The smallest, or ”finger-tip”, channels constitute the first-order seg￾ments. [. . . ]. A second-order segment is formed by the junction of any

two first-order streams; a third-order segment is formed by the joining of

any two second order streams, etc.

Streams of lower order joining a higher order stream do not change the order

of the higher stream. Thus, if a first-order stream joins a second-order stream,

it remains a second-order stream. Figure 1 shows the Strahler number for a

fragment of the course of the Elbe river with some of its tributaries. The stream

system is of order 4.

From a computer science point of view, stream systems are just trees.

Definition 1. Let t be a tree with root r. The Strahler number of t, denoted by

S(t), is inductively defined as follows.

– If r has no children (i.e., t has only one node), then S(t)=0.

– If r has children r1,...,rn, then let t1,...,tn be the subtrees of t rooted at

r1,...,rn, and let k = max{S(t1),...,S(tn)}: if exactly one of t1,...,tn has

Strahler number k, then S(t) = k; otherwise, S(t) = k + 1.

A.-H. Dediu et al. (Eds.): LATA 2014, LNCS 8370, pp. 1–13, 2014.

c Springer International Publishing Switzerland 2014

2 J. Esparza, M. Luttenberger, and M. Schlund

1

1

1

1

1

1

1

1

1

1

1 1

1

1

1

1

1

1

1

1

1

1

1

1

2 2

2

2

2 2

2 2

3

3

4

1

1

Fig. 1. Strahler numbers for a fragment of the Elbe river

Note that in this formal definition the Strahler number of a simple chain (a

”finger-tip”) is zero, and not one. This allows another characterization of the

Strahler number of a tree t as the height of the largest minor of t that is a

perfect binary tree (i.e., a rooted tree where every inner node has two children

and all leaves have the same distance to the root): Roughly speaking, such a

binary tree is obtained by, starting at the root, following paths along which the

Strahler number never decreases by more than one unit at a time, and then

contracting all nodes with only one child. If t itself is a binary tree, then this

minor is unique. We leave the details as a small exercise.

Figure 2 shows trees with Strahler number 1, 2, and 3, respectively. Each node

is labeled with the Strahler number of the subtree rooted at it.

1

0 1

0 1

0 0

2

1

0 0

1

1

0 0

0

3

2

1

0 1

0 0

1

0 1

0 0

2

1

0 0

1

1

0 1

0 0

0

Fig. 2. Trees of Strahler number 1, 2, and 3

A Brief History of Strahler Numbers 3

Together with other parameters, like bifurcation ratio and mean stream length,

Horton and Strahler used stream orders to derive quantitative empirical laws for

stream systems. Today, geophysicists speak of the Strahler number (or Horton￾Strahler number) of a stream system. According to the excellent Wikipedia ar￾ticle on the Strahler number (mainly due to David Eppstein), the Amazon and

the Mississippi have Strahler numbers of 10 and 12, respectively.

2 Strahler Numbers and Tree Traversal

The first appearance of the Strahler number in Computer Science seems to be

due to Ershov in 1958 [8], who observed that the number of registers needed to

evaluate an arithmetic expression is given by the Strahler number of its syntax

tree. For instance, the syntax tree of (x + y · z) · t, shown on the left of Figure

3, has Strahler number 2, and indeed can be computed with just two registers

R1, R2 by means of the code shown on the right.

×

+

x ×

y z

w

R1 ← y

R2 ← z

R2 ← R1 × R2

R2 ← x

R1 ← R1 + R2

R2 ← w

R1 ← R1 × R2

Fig. 3. An arithmetic expression of Strahler number 2

The strategy for evaluating a expression e = e1 op e2 is easy: start with the

subexpression whose tree has lowest Strahler number, say e1; store the result in

a register, say R1; reuse all other registers to evaluate e2; store the result in R2;

store the result of R1opR2 in R1.

Ershov’s observation is recalled by Flajolet, Raoult and Vuillemin in [16],

where they add another observation of their own: the Strahler number of a bi￾nary tree is the minimal stack size required to traverse it. Let us attach to each

node of the tree the Strahler number of the subtree rooted at it. The traversing

procedure follows again the “lowest-number-first” policy (notice that arithmetic

expressions yield binary trees). If a node with number k has two children, then

the traversing procedure moves to the child with lowest number, and pushes the

(memory address of the) other child onto the stack. If the node is a leaf, then

the procedure pops the top node of the stack and jumps to it. To prove that

the stack size never exceeds the Strahler number, we observe that, if a node of