Mathieu Jeannin

Alberto Artioli

Pamela Rueda-Fonseca

Edith Bellet-Amalric

Kuntheak Kheng

Régis André

Serge Tatarenko

Joël Cibert

David Ferrand

Gilles Nogues

Light-hole Exciton in Nanowire Quantum Dot

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

I. INTRODUCTION

Semiconductor quantum dots are seen as important elements for integrated quantum simulation and communication. [1][2][3] They can act as static qubits, encoding information either onto their orbital or spin state.

They can also serve as a deterministic source of flying qubits using single [START_REF] Santori | Ya-659 mamoto[END_REF]5 or entangled photons. [6][7][8] In this perspective, hole spins are particularly interesting because of their weak hyperfine coupling to surrounding spin bath compared to electrons. 9,10 Furthermore working with light-holes pave the way to new information technology protocols like direct manipulation of the hole spin state with RF fields, 11 efficient control of a magnetic impurity spin coupled to a quantum dot, 12 or spin state tomography of the electron inside the dot. [START_REF] Kosaka | Mit-681 sumori[END_REF] However most of the previous studies have concerned so far heavy-hole states, because they are energetically favored for a majority of quantum dot heterostructures for which confinement and strain lift the degeneracy of the valence band. 14,15 Hence a way to address light-holes is to promote them as the valence band ground state by engineering the strain inside the dot. For epitaxially grown dots this requires technologically intensive methods, such as the fabrication of deformable membranes containing the dots. 16 Another very promising strategy is to embed the dot inside a nanowire. 17 This bottom-up approach produces high quality heterostructures. It offers a way to control both the carriers confinement through the geometrical shape of the dot, and its internal strain by adding a shell of a different material around the nanowire core. 18,19 To be short, in most nanostructures the low-gap material has a larger lattice parameter. In a flat quantum dot as resulting from Stranski-Krastanow growth, it is well known that the hole ground state has a main heavy-hole character. The most frequent case is that of InAs dots in GaAs, but this is true also for CdTe dots in ZnTe. 20 This is due to the stronger effect of confinement along the growth axis, and to the strongest component of the mismatch strain which is compressive in the plane. 45 In a core-shell nanowire made of the same materials, the 46 confinement is stronger in the plane, and the strongest 47 component of the mismatch strain is compressive along 48 the axis. As a result, both confinement and mismatch 49 strain conspire to make the ground state a light-hole 50 state. 19 When increasing the height of a quantum dot 51 in a nanowire, a crossing is expected, from the heavy-52 hole ground state in a flat quantum dot to a light-hole 53 ground state in an elongated quantum dot. 18 Note that 54 nanowire structures are very flexible, and a heavy-hole 55 ground state can be found also in a core-shell nanowire if 56 the lattice mismatch induces a tensile strain in the core. 19 57 An additional important property of a semiconductor 58 nanowire is that it acts as a dielectric antenna, modu-59 lating the coupling of the different exciton transitions to 60 light modes which changes their radiation pattern. 5,21-24 61 Here we provide a complete study of a light-hole quan-62 tum dot (QD) in a core-shell nanowire. The dot con-63 tains a large fraction of magnetic dopants in order to en-64 hance the Zeeman shift for spintronics applications. This 65 prevents a direct spectroscopic evidence of its light-hole 66 character by measuring its fine structure. 16 We show nev- Our system is a single (Cd,Mn)Te QD inserted ). [START_REF] Artioli | [END_REF]30 The dot is largely doped with Mn atoms 183 (Mn concentration ∼10%), making it a dilute magnetic Mg content. 39 The mismatch between CdTe and ZnTe 425 is opposite, so that we expect a LH character for a 426 hole confined in a core-shell nanowire 19 or an elongated 427 dot. 18 For InAs/InP, a local splitting ∆ LH -100 meV 428 is calculated 18 at the center of a cylinder-shape QD with 429 an aspect ratio 2, but due to an inhomogeneous strain 430 the HH state is ∼25 meV above the ground state. In 431 the present case, the aspect ratio is of the same order, 432 the mismatch slightly larger, but the CdTe-ZnTe valence 433 band offset is small so that another competition is ex-434 pected with heavy-holes confined in the shell due to the 435 shear strain around the dot. 19 A full calculation of ∆ LH 436 is beyond the scope of this paper, but our measured value 437 is of the right order or magnitude.

438

We measure a value of the mixing term ρ 0 5 meV.

439

Larger values have been reported for self-assembled 440 (Stranski-Krastanov) quantum dots. 25 Actually, an im- confinement is possible using bottom up approach and 487 semiconducting nanowire growth.

488

of symmetry exists, the hole Hamiltonian is usually written, in the {|3/2 ; |1/2 ; |-1/2 ; |-3/2 } basis quantized along this axis, as:

H =     -1 2 ∆ LH -σe -iχ ρe -2iψ 0 -σe iχ 1 2 ∆ LH 0 ρe -2iψ ρe 2iψ 0 1 2 ∆ LH σe -iχ 0 ρe 2iψ σe iχ -1 2 ∆ LH     (B1)
A zz ) = 0 1 2 ∆ LH = 1 2 A xx + 1 2 A yy -A zz ρe -2iψ = √ 3 2 (A xx -A yy -2iA xy ) σe -iχ = - √ 3(A xz -iA yz ) (B2)
Expressions of the matrix elements of Eq. B1 (hence those of A) for the Luttinger-Kohn of Bir-Pikus Hamiltonian are generally expressed in the cubic basis. [START_REF] Bir | Symmetry and Strain-Induced Ef-713 fects in Semiconductors[END_REF] However other axes can be chosen; for instance, in the case of a nanowire oriented along the < 111 > axis, as in the present study, it is useful to choose this axis as the z quantization axis. 19 If H represents the coupling to a uniform strain (the Bir-Pikus Hamiltonian) for an isotropic system, ∆ LH is proportional to the axial shear strain

( 1 2 ε xx + 1 2 ε yy -ε zz ), ρe -2iψ to the shear strain in the xy plane, √ 3
2 (ε xx -ε yy -2iε xy ), and σe -iχ to the combination -√ 3(ε xz -iε yz ) of the shear strains in planes containing z. However, it must be kept in mind that such a spin Hamiltonian is general and can describe other features governing the hole states, such as for instance the inhomogeneous strain expected in a quantum dot, or the effect of a confinement potential with a low symmetry. Now, as the matrix A is real and symmetric, a mere rotation makes it diagonal, with the three (real) eigenvalues on the diagonal. Using these eigenaxes (x 0 , y 0 , z 0 ), the spin Hamiltonian still writes J .A.J , and it still develops as in Eq. B1, but Eq. B2 shows that now all matrix elements are real (including ρ), and σ = 0:

H =     -1 2 ∆ LH0 0 ρ 0 0 0 1 2 ∆ LH0 0 ρ 0 ρ 0 0 1 2 ∆ LH0 0 0 ρ 0 0 -1 2 ∆ LH0     (B3) with A z0z0 = 1 3 ∆ LH0 , A x0x0 = -1 6 ∆ LH0 + 1 √ 3 ρ 0 and A y0y0 = -1 6 ∆ LH0 -1 √ 3 ρ 0 .
If the z 0 axis is chosen so that A z0z0 is the eigenvalue with the largest absolute value, then ρ 0 < |∆ LH0 |/2 √ 3; the two Kramers doublet will be considered as light holes and heavy holes quantized along z 0 , with some mixing due to ρ 0 .

To sum up, the most general spin Hamiltonian describing the hole states is given by Eq. B1, where diagonal elements are real numbers but non-diagonal elements are complex numbers. Diagonalizing the corresponding matrix A determines a rotation (i.e., three Euler angles)

to a new set of axes where ∆ LH0 but also ρ 0 are real numbers and σ=0, Eq. B3. As the principal axes of A are those where the Hamil-608 tonian H is real with a vanishing σ, so that the hole states

67

  ertheless that the detailed observation of the polarisation 68 state of the QD far field radiation pattern is enough to 69 prove its light-hole nature and provides a wealth of in-70 formation about its mixing with heavy-hole states. Our 71 results are in agreement with numerical simulations of 72 the QD emission within the full nanowire structure. It 73 is confirmed by studying the giant Zeeman shift and the 74 polarisation of the excitonic transition under an external 75 magnetic field. The magneto-optical spectroscopy reveals 76 a heavy-hole excited state at high field, thus providing an 77 order of magnitude for the valence band splitting. Our 78 method is simple, and requires no extra processing of the 79 sample 16,25 as far as the nanowire is isolated from its 80 neighbours.

Figure 1 .

 1 Figure 1. (a), Energy levels inside the QD participating to the luminescence, along with the corresponding transitions with their oscillator strength and polarisation. (b), Schematic of the experiment. The light emission is mapped onto the Fourier plane to allow polarisation analysis of the photons with respect to the direction (θ, ϕ). The inset present a zoom of the nanowire in the vicinity of the quantum dot. (c,d), Theoretical far field intensity maps for the σ or π transition, respectively. The QD is assumed to be in an infinite space made of ZnTe. The green lines in (c) and (d) represent the time evolution the electric field in the (x, y) plane for a set of directions. For each direction the electric field origin is centered on the (θ, ϕ) coordinate.

Figure 2 .

 2 Figure 2. (a), µPL spectrum of ZnTe core and CdTe quantum dot luminescence, along with the integrated spectral range for cathodoluminescence imaging. (b), SEM image of the nanowire along with (c), spectrally resolved CL image and SEM image superimposed and (d), cut profile of the spectrally resolved CL signal along the nanowire axis. The contribution of each part of the spectrum is coloured according to the spectrum in (a).

180

  along a <111> ZnTe/(Zn,Mg)Te core/shell nanowire 181 grown by molecular beam epitaxy (see Supplemental 182 Material 28

184S = 5 / 2 36 322Figure 3 .LH 2 3%

 523632 Fig.1(b). We also note that there is a ∼20% intensity 264

Figure 4 .Fig. 2 (

 42 Figure 4. (a), Zeeman diagram of the electron and hole confined levels split by the exchange interactions with Mn atoms. The dashed arrows labeled XLH (resp. XHH ) corresponds to the LH (resp. HH) exciton transitions. The lowenergy transition involving a LH creates a |-1/2 electron in the conduction band and a |+1/2 hole in the valence band, hence it is linearly polarized along the z-axis. The low-energy transition involving a HH creates a |-1/2 electron in the conduction band and a |+3/2 hole in the valence band, hence it is σ + -polarized. (b), Photoluminescence spectra of the QD emission line recorded at 10K in zero field and at B=11T (corresponding to a QD magnetic moment M/Msat = 0.84). The magnetic field is applied along the nanowire axis oriented parallel to the optical axis. Both circular polarisations (σ + in green and σ -in dashed blue) are shown. The intensity of the zero field spectrum has been multiplied by 2.5. (c), Zeeman shift of the LH and HH exciton lines proportional to the QD magnetic moment M/Msat. The continuous lines correspond to the theoretical shift expected for a (Cd,Mn)Te quantum dot with a Mn concentration of 10% (see text). (d), Circular polarisation rates of the LH and HH exciton lines under magnetic field. The continuous lines corresponds to the expected values taking into account the valence band mixing induced by a constant perturbation term |σ| = 3.9 meV.

441We have performed measurements on a set of ∼ 40 466

 40 portant feature is the symmetry of the principal axis, and 442 switching from the < 001 > to the < 111 > orientation 443 dramatically reduces in-plane asymmetry expected, 40 444 and measured. 41,42 Our dots are embedded in nanowires 445 grown along the < 111 > axis. However the section of 446 such nanowires easily feature some ellipticity, of the or-447 der of a few %, easily detected on the shell 32 (although 448 well beyond the resolution on the dot). A first evaluation 449 of the strain in an elongated (aspect ratio ∼ 2) ellipsoid 450 with some in-plane ellipticity can be done using the Es-451 helby calculation: 43,44 using the Bir-Pikus Hamiltonian, 452 an ellipticity of 5% gives the right order of magnitude 453 for ρ 0 . Note that the same orientation of the ellipticity 454 will change the phase of ρ with the sign of the mismatch, 455 as observed between the dot and the ZnTe core. Finally, 456 writing the stiffness matrix with the < 111 > axis as 457 z-axis 19 reveals that the presence of an in-plane shear 458 (ε xx -ε yy ) induces an axial shear stress, and hence a 459 strain ε yz , of similar order of magnitude. This strain 460 gives rise to a non-zero σ, which is not a tilt, but can be 461 compensated by a tilt. Such a term is evidenced on the 462 emission diagram of the quantum dot, while it is partly 463 screened by guiding effect in the case of the ZnTe emis-NWQDs from the same sample mechanically deposited 467 on a substrate. As they lie horizontally and close to a 468 reflecting substrate which significantly disturbs the far-469 field radiation pattern, we could not perform the same 470 characterization as for the as-grown wire. Nevertheless 471 polarization studies reveal that the sample is actually 472 close to the threshold between light-hole and heavy-hole 473 ground state, 18 thus leading to a large dispersion in emis-474 sion properties. A majority of the QDs (∼ 70%) emit 475 light linearly polarized along the NW axis, which in our 476 system is a good indication of a LH ground state. The re-477 maining 30% emit light polarized perpendicularly to the 478 NW axis, thus clearly indicating a HH character. 479 To conclude, complementary experiments on a single 480 nanowire unambiguously demonstrate a LH exciton emis-481 sion. They allow to evaluate the splitting ∆ LH as well 482 as the valence band mixing parameters. The results are 483 in agreement with the predictions of strain effects due 484 to the presence of a shell around the wire. We demon-485 strate that valence band engineering through strain and 486

Figure 5 .

 5 Figure 5. Magneto-optical spectroscopy. (a) Photoluminescence spectra at T = 10 K with a magnetic field applied along the nanowire axis, from B = 0 to 11 T by steps of 1 T. The spectra at 0 and 11 T are displayed in Fig. 4a of main text. (b) Plot of the position of the low energy line as a function of 5µBB/kB(T + TAF )

  552spin, with real coefficients. In the case of a J = 3/2 553 quadruplet, powers of the J operators up to 3 are enough, 554 and in the absence of an applied magnetic field, only 555 even powers have to be considered in order to fulfill the 556 Kramers degeneracy. As a result, the most general spin 557 Hamiltonian which describes the quadruplet at the top 558 of the valence band can be written J .A.J , where the 559 vectorial operator J is the (pseudo)-moment and A is a 560 real 3 × 3 matrix. In addition, due to the commutation 561 rules of J , A is symmetric. Note that the contribution of 562 order zero to the spin Hamiltonian is redundant with the 563 trace of A; both represent a rigid shift of the quadruplet, 564 and a proper choice of the zero of energy allows us to 565 set the trace of H (hence that of A) to zero, as done in 566 Eq. B1. Using the 4 × 4 matrices representing the second powers of J in the | 3 2 , | 1 2 , | -1 2 and | -3 2 basis of the Γ 8 quadruplet, with the third axis z as the quantization axis 45 , the matrix elements of H are T r(H) = 5 4 (A xx + A yy +

Figure 6 .

 6 Figure 6. Light Hole exciton dipole radiation (a) Principal axes (x0, y0, z0) of the ellipsoid defined by Eq. B6 and calculated for ψ = 40 • , χ = 110 • , ρ/∆LH = 0.1, σ/∆LH = 0.3 and E0/∆LH = 2. They are obtained by 3 rotations with the Euler angles α = 40 • , β = 19 • and γ = 0 • . (b) Orientation of the 3 elementary orthogonal linear dipoles associated to the light hole exciton. They are oriented along the axes (x0, y0, z0). The π (resp. σ) polarized exciton transitions are associated to the dipole along z0 (resp. x0 and y0). The figure is calculated for the same Euler angles as above and for the hole anisotropy parameters = 0.214 (ρ0/∆LH0 = 0.0406).The lengthes of the colored lines are proportional to the dipole magnitudes dx 0 , dy 0 and dz 0 (see text).

609 2 ∆

 2 are most simple to write, it is useful to write the effect 610 of a rotation on A and H. We apply to A or H the ro-611 tation exp(-iγJ z ) exp -i βJ y exp(-iαJ z ) defined by 612 three Euler angles (α, β, γ), see Fig. 6. It is particularly 613 interesting -and technically simpler -to consider small 614 values of β, so that we keep only the first order in β or 615 sin β. In this case, (α + γ) is the total angle of rotation 616 around the z axis (which has an effect only if the system 617 does not feature circular symmetry, with non vanishing 618 ρ 0 and different values of A x0x0 and A y0y0 ), while β is the 619 angle of the tilt and γ its direction. The rotation matrix 620 γ) -sin(α + γ) sin β cos γ sin(α + γ) cos(α + γ) sin β sin γ -sin β cos α sin β sin α 1   (B4) and the matrix elements of A in the laboratory frame 622 are obtained by a straightforward calculation of RA t R.623H is derived using Eq. B2, or calculated directly using 624 the rotation exp(-iγJ z ) (1 -i βJ y ) exp(-iαJ z ) , where 625 the operator of rotation around y (the tilt) is linearized.626The result is quite simple. The hamiltonian assumes the 627 form of Eq. B1, where:ρe -2iψ = ρ 0 e -2i( α+γ)σe -iχ = β( √ 3 LH0 + ρ 0 e -2i α)e -iγ (B5)These expressions have been used to fit the experimen-629 tal data.

630 2 .

 2 Geometrical visualizing of the anisotropy tensor 631 Since in the case of the Bir-Pikus Hamiltonian, the 632 anisotropy matrix A is proportional to the strain tensor

  The parameter σ mea-

	164	our objective [see Fig. 1(d)]. A more precise description
	165	of the radiated field comes from the polarisation of the
	166	light emitted in a given direction. It is projected by the
	167	objective onto a state of polarisation in the (x, y) plane,
	168	represented in Fig. 1(c-d) by the green curves which fol-
	169	low the electric field vector E(θ, ϕ, t) over one optical pe-
	170	riod. It results in an ellipse whose aspect ratio changes
	171	from a perfect circle for a pure σ ± to a single line for a
		pure linear polarisation state. Here again, striking differ-
	173	ences exist between π and σ transitions. One important
	174	message of our work is that this polarisation analysis for
	175	a large set of emission directions provides unambiguous,
	176	quantitative informations about the hole character and
		the valence band mixing.
		136
		137	sured in the laboratory axes does not really represent a
		138	mixing, but the result of the tilt β between z and z 0 .
		139	We stress this physical interpretation of the two "mixing
		140	parameters" measured in the laboratory frame, because
		141	it has direct practical consequences: ρe -2iψ describes a
		142	real mixing, which requires that a shear strain be applied
		143	in order to compensate for it. 16 On the other hand the
		144	effect of σ (which can also be due to strain and confine-
		145	ment anisotropy) can be compensated by an appropriate
		146	tilt of the optical axis.
		147	In our setup we collect the nanowire light by placing a
		148	microscope objective (numerical aperture NA=0.72) on
		149	the z axis [Fig. 1(b)]. A set of additional optical elements
		150	allows to image onto a CCD camera the intensity I(θ, ϕ)
		151	emitted in a direction (θ, ϕ). 23,24 Figures 1(c-d) represent
		152	the theoretical colormaps of I(θ, ϕ) for a σ and π transi-
		153	tion respectively, assuming that the QD is surrounded by
		154	an infinite medium made of ZnTe for illustration purpose
		155	first. The radial coordinate is equal to sin θ and the polar
		156	angle is equal to ϕ. The two radiation patterns differ dra-
		157	matically, and could be enough to discriminate light-and
		158	heavy-hole emission. Nevertheless, they are significantly
		159	affected by the nanowire geometry and by the imperfec-
		160	tion of the collection objective. Note that while the π
		161	dipole emission does not radiate along the optical axis,
		162	it does generate light towards larger angles within our

ACKNOWLEDGMENTS We acknowledge the help of Institut Néel optical engineering team (CL, Fabrice Donatini). This work was supported by the French National Research Agency under contracts ANR-11-BS10-013, ANR-15-CE24-0029 and ANR-10-LABX-51-01, and Institut Universitaire de France.

A. Sample fabrication

The second salient feature is the strongly σ + -polarized line, visible at high field only. A weaker line is observed at high field, with a small Zeeman shift, which we did not identify (the nanowire is still on the substrate and parasitic growth takes place between the nanowires). Finally, the spectra at low fields appear as quite complex, but this is expected by the proximity of several hole sublevels at these field values (in particular, |+3/2 and |-1/2 which are expected to (anti)-cross at these field values, see Fig. 4b of the main text, and probably excited states of the |+1/2 hole).

Appendix B: Theoretical background 1. Anisotropy of the holes

In a bulk semiconductor with the zinc-blende or diamond structure, the hole quadruplet is degenerate (representation Γ 8 of the cubic group). The presence of strain or confinement lifts this degeneracy. If a principal axis (possibly weighted by the deformation potential parame-634 ters), it is often quite illuminating to pursue the analogy 635 and to consider an ellipsoid defined in real space using 636 the matrix A, as an easy way to view the anisotropy 637 within the hole quadruplet. One possibility is to con-638 sider a sphere of radius unity, to which we apply a strain 639 -A ij /E 0 , with an arbitrary scaling factor E 0 . If E 0 is 640 larger than the largest eigenvalue of A, the result is an 641 ellipsoid which admits the x 0 , y 0 , z 0 eigen-axes of A as 642 principal axes, with a half-axis length 1-A x0x0 /E 0 along 643 x 0 , and so on.

644

To first order in A ij /E 0 , the equation of such a solid

where the x i 's are the coordinates x, y, z of an arbitrary 647 frame.

648

The principal axes of the ellipsoid are those where H


Riko Jacob
email: rjacob@inf.ethz.ch

Tobias Lieber
email: lieberto@inf.ethz.ch

Matthias Mnich
email: m.mnich@mmci.uni-saarland.de

Treewidth Computation and Kernelization in the Parallel External Memory Model

We present a randomized algorithm which computes, for any fixed k, a tree decomposition of width at most k of any input graph. We analyze it in the parallel external memory (PEM) model that measures efficiency by counting the number of cache misses on a multi-CPU private cache shared memory machine. Our algorithm has sorting complexity, which we prove to be optimal for a large parameter range.

We use this algorithm as part of a PEM-efficient kernelization algorithm. Kernelization is a technique for preprocessing instances of size n of NP-hard problems with a structural parameter κ by compressing them efficiently to a kernel, an equivalent instance of size at most g(κ). An optimal solution to the original instance can then be recovered efficiently from an optimal solution to the kernel. Our main results here is an adaption of the linear-time randomized protrusion replacement algorithm by Fomin et al. (FOCS 2012). In particular, we obtain efficient randomized parallel algorithms to compute linear kernels in the PEM model for all separable contraction-bidimensional problems with finite integer index (FII) on apex minor-free graphs, and for all treewidth-bounding graph problems with FII on topological minor-free graphs.

Introduction

Many practically relevant computational problems are NP-hard. Many decision problems on graphs become efficiently solvable in the RAM model if the input graph has bounded treewidth. By now, there is the linear time algorithm to compute a tree decomposition [START_REF] Bodlaender | Efficient and constructive algorithms for the pathwidth and treewidth of graphs[END_REF], working in the classical RAM model. This algorithm has been adapted to the PRAM model [START_REF] Bodlaender | Parallel algorithms with optimal speedup for bounded treewidth[END_REF] and to serial models that take the caches of the memory hierarchy into account [START_REF] Maheshwari | I/O-efficient algorithms for graphs and bounded treewidth[END_REF]. Here, we present an adaption of the algorithm that is simultaneously parallel and cache efficient, as modeled by the PEM model, which is defined in Section 1.1.

Another common technique for solving NP-hard problems is pruning easy parts of an instance in a preprocessing step. In the field of parameterized complexity this is formalized as kernelization. It is known that every decidable fixedparameter tractable problem Π for a parameter κ admits a kernelization, which is an algorithm that in polynomial time reduces any instance of Π of size n to an equivalent instance (the kernel ) of size g(κ) for some computable function g. Here, equivalent means that the original instance is a "yes"-instance if and only if the kernel is. For example for the vertex cover problem, Nemhauser and Trotter have shown that any graph G on n vertices can be kernelized efficiently into a graph G on at most 2κ vertices, where κ denotes the size of a minimum vertex cover of G [START_REF] Flum | Parameterized complexity theory[END_REF]. Recent meta-results show that large classes of combinatorial optimization problems admit kernels of linear size on planar graphs [START_REF] Bodlaender | On problems without polynomial kernels[END_REF], and, more generally, classes of graphs excluding a fixed minor [START_REF] Fomin | Planar F-deletion: Approximation, kernelization and optimal FPT algorithms[END_REF][START_REF] Kim | Linear kernels and single-exponential algorithms via protrusion decompositions[END_REF]. On the other hand, not every fixed-parameter tractable problem admits a polynomial sized kernel, unless the polynomial hierarchy collapses to the third level [START_REF] Bodlaender | On problems without polynomial kernels[END_REF][START_REF] Drucker | New limits to classical and quantum instance compression[END_REF].

The classical view on kernelization in the RAM model is to solve an instance I of a hard problem Π in two phases: the first phase, kernelization, transforms in polynomial time the instance I of size n into a kernel I whose size g(κ) depends solely on the structural parameter κ. The second phase solves the problem Π on the kernel I in time f (g(κ)) for some function f , which is often at least exponential due to a brute force algorithm. Thus, this leads in total to a running time of O (p(n) + f (g(κ))) to decide I in the RAM model.

Given the abundance of practically relevant NP-hard problems where input instances are large, it would be nice to have this approach efficiently implemented. Recently, efficient kernelization algorithms have been proposed, for example by Hagerup [START_REF] Hagerup | Simpler linear-time kernelization for planar dominating set[END_REF] and van Bevern et al. [START_REF] Van Bevern | Linear-time computation of a linear problem kernel for dominating set on planar graphs[END_REF], where linear time RAM algorithms are presented. Further, meta-results by Fomin et al. provide randomized linear-time kernelizations for many combinatorial optimization problems on graph classes excluding a fixed minor [START_REF] Fomin | Planar F-deletion: Approximation, kernelization and optimal FPT algorithms[END_REF]. There are some reservations against the practicability of the algorithms implied by these meta-results, namely very large constant factors hidden in the O-notation, and some difficulties in actually creating certain constant sized structures.

To obtain efficient algorithms on modern computers, parallelism and hierarchical memories have to be exploited. Such a parallel and memory efficient implementation is frequently possible for the second phase of kernelization. On the other hand, due to the exponential work that is done, this only moderately extends the size of I , which can be handled. We show that the randomized kernelization algorithms of Fomin et al. can be efficiently implemented in the PEM model, i.e., in parallel and taking the memory hierarchy into account. While this algorithm does not improve the large constant factors in the runtime, it shows that there are no fundamental obstacles when implementing this kind of algorithm in the PEM model. We expected that concrete algorithms for the problems covered by the meta-results can also be implemented efficiently in the PEM model.

Model of Computation: The Parallel External Memory Model

For using modern computers optimally, two architectural features require special consideration: parallelism and the memory hierarchy. To capture these two fundamental features, the parallel external memory (PEM) model was introduced [START_REF] Arge | Fundamental parallel algorithms for private-cache chip multiprocessors[END_REF]. It is based on the external memory (EM) model which captures cache efficiency of algorithms [START_REF] Aggarwal | The input/output complexity of sorting and related problems[END_REF]. The EM model extends the RAM model by a cache, located between CPU and memory (see Figure 1a). The cache can store up to M elements, on which the CPU can perform any computations for free. The conceptually infinite (external) memory is partitioned in blocks, each holding up to B elements. A block can be transferred as a unit by an input/output operation (I/O) between the cache and the memory. The memory initially holds the input of size n in the first n/B blocks. The PEM model (see Figure 1b) is a parallel extension of the EM model. It has P CPUs which all have their own (private) cache of size M . In one parallel I/O each processor can perform one I/O operation for moving data between its cache and the shared memory. Similar to the PRAM model, this requires a policy for simultaneous access to the same block. Here, we work with the CREW policy that allows concurrent read but disallows concurrent write. The complexity of an algorithm in the PEM model is the number of parallel I/Os it performs. An algorithm is called PEM-efficient if its complexity is matched by a lower bound for the problem in the PEM model.

• • • B Cache M CPU (Shared) Memory read write (a) The EM Model • • • CPU 1 CPU 2 CPU P • • • (b) The PEM Model
The easiest non-trivial task in the (P)EM model is that of permuting: given a permutation π, create from the input (x 1 , . . . , x n ) the output (x π(1) , . . . , x π(n) ). While in the (P)RAM model the complexity of permuting is the same as for scanning the input, Θ(n/P ), in the (P)EM model it is not. For many settings of the parameters, the optimal solution in the PEM model for permuting is to sort in sort P (n) = Θ( n P B log M B n B ) parallel I/Os, where log x equals max{1, log x}. In the PRAM model one important goal is to obtain work optimal algorithms for a maximal number of processors. For the PEM model, one strives similarly to use as many processors as possible, while still using the optimal number of parallel I/Os. We define a PEM-efficient kernelization for a parameterized problem Π as an algorithm A that computes for any instance x of size n with parameter κ a kernel (x , κ ), and A is PEM-efficient. In our case this means A executes with O (sort P (n)) parallel I/Os.

Related Work

A tree decomposition of a graph G is a tree T and for each node i of T there is a bag B i of vertices of G such that (i) for each vertex v of G there is at least one bag containing v; (ii) for each edge e of G there is at least one bag containing both its endpoints; and (iii) for each v of G, the set {i | v ∈ B i } induces a subtree of T . The width of a tree decomposition is defined as the maximum bag size minus one. The treewidth of G, denoted by tw(G), is the minimum width over all tree decompositions of G.

There are several fixed-parameter algorithms to compute the treewidth of a graph in different computational models. The most important to this paper are the following: Bodlaender and Kloks introduced in 1993 the first linear time algorithm to efficiently compute a tree decomposition of fixed width k of a graph G in the RAM model [START_REF] Bodlaender | A linear-time algorithm for finding tree-decompositions of small treewidth[END_REF]. Later Bodlaender and Hagerup introduced a work optimal algorithm for the PRAM model for up to p ≤ n log 2 n processors [START_REF] Bodlaender | Parallel algorithms with optimal speedup for bounded treewidth[END_REF]. An I/O efficient algorithm for computing the treewidth in the EM model has been presented by Maheshwari and Zeh [START_REF] Maheshwari | I/O-efficient algorithms for graphs and bounded treewidth[END_REF].

Recently numerous problems have been shown to admit linear kernels on generalizations of planar graphs, including graphs of bounded genus, and graphs of bounded maximum degree [START_REF] Fomin | Planar F-deletion: Approximation, kernelization and optimal FPT algorithms[END_REF][START_REF] Kim | Linear kernels and single-exponential algorithms via protrusion decompositions[END_REF]. The results are briefly summarized:

Throughout the paper, let H denote a fixed graph and let G H be the graph class that excludes H as a minor. For any class G H , where H is an apex graph (so H \ {v} is planar for some vertex v), we deal with essentially all problems Π that are "contraction-bidimensional". Roughly speaking, a parameterized problem Π is contraction-bidimensional if contracting an edge cannot increase the objective value κ, and on square grids the objective value grows proportionally with the size of the vertex set of the grid.

Lemma 1 ([14]

). On any class of graphs excluding a fixed apex graph as a minor, all separable contraction-bidimensional problems with finite integer index, parameterized by solution size κ admit kernels of size O (κ).

Graph classes excluding a fixed graph H as a minor can be generalized to classes excluding H as a topological minor. A graph problem Π, parameterized by κ is called treewidth-bounding if all "yes"-instances (G, κ) of Π admit an O (κ)-sized set S ⊆ V (G) such that the graph G \ S has constant treewidth.

Lemma 2 ([7]

). On any class of graphs excluding a fixed graph as a topological minor, all treewidth-bounding graph problems with finite integer index, parameterized by solution size κ have a kernels of size O (κ).

Recently, Hagerup [START_REF] Hagerup | Simpler linear-time kernelization for planar dominating set[END_REF] and van Bevern et al. [START_REF] Van Bevern | Linear-time computation of a linear problem kernel for dominating set on planar graphs[END_REF] argued that not only the size g(κ) of the produced kernel, but also lowering the running time of the kernelization algorithm is an important research direction. Another strong case for designing kernels that are as efficient as possible is made by Komusiewicz and Niedermeier [START_REF] Komusiewicz | New races in parameterized algorithmics[END_REF].

Neither of the approaches considers kernelization in a context of parallel I/O algorithms, but only in the classical RAM model. Thus the approach of designing PEM-efficient algorithms for kernelization is completely new.

Most proofs are omitted due to space limitations and will be published in a full version of this paper.

Our Contributions

Our first contribution is for every fixed k ∈ N a randomized PEM-efficient algorithm which for a given graph G computes a tree decomposition of width at most k, or decides that the treewidth of G is larger than k. Our algorithm is based on the treewidth algorithm for the PRAM model [START_REF] Bodlaender | Parallel algorithms with optimal speedup for bounded treewidth[END_REF] and the treewidth algorithm for the EM model [START_REF] Maheshwari | I/O-efficient algorithms for graphs and bounded treewidth[END_REF]. While the first algorithm yields a framework for load balancing in treewidth computations, the latter yields an EM efficient implementation of the dynamic programming approach of Bodlaender and Kloks [START_REF] Bodlaender | Efficient and constructive algorithms for the pathwidth and treewidth of graphs[END_REF]. The combination yields a rather technical implementation of the load balancing part of Bodlaender and Hagerup, and a parallelized version of the algorithm of Maheshwari and Zeh. The fundamental building block for our algorithm, which is given in Section 2, is list ranking. Furthermore, the fundamental data structure flippable DAG for the EM model, introduced by Maheshwari and Zeh [START_REF] Maheshwari | I/O-efficient algorithms for graphs and bounded treewidth[END_REF], is replaced by a simpler construction as it appears to be hardly parallelizable. Theorem 3. For every k, t ∈ N, the expected number of parallel I/Os needed to compute a tree decomposition of width at most k, if such exists, for a graph G of size n in the CREW PEM model with P ≤ n/(B 2 log B log n log (t) n) and

M = B O(1) is O (sort P (n)).
Throughout this paper, t is a fixed constant which can be chosen arbitrary, influencing only the constant in the sort P (n) term. Furthermore, it is defined log (1) x = log x and log (k) x = log log (k-1) x.

Observe that the bound on the I/O complexity is tight for a wide range of the number of processors, which is shown in Section 5.

Our second contribution is a PEM-efficient implementation of the randomized fast protrusion replacer of Fomin et al. [START_REF] Fomin | Planar F-deletion: Approximation, kernelization and optimal FPT algorithms[END_REF]. Their fast protrusion replacer works by replacing large protrusions, which are subgraphs of small treewidth and small attachment to the rest of the input graph, by smaller, constant-sized protrusions. It can be used to provide efficient randomized kernelization algorithms for the (linear) kernels mentioned in Lemma 1 and Lemma 2. Using our PEM-efficient algorithm for computing the treewidth of a graph we argue in Section 3 that this protrusion replacer can be implemented efficiently in the PEM model. Using the randomized fast protrusion replacer, in Section 4 the following theorem is shown.

Theorem 4. The expected number of parallel I/Os to compute a linear kernel for each of the problems of Lemma 1 and Lemma 2 is O (sort P (n)) in the CREW PEM model with P ≤ n/(B 2 log B log 2 n log (t) n) and M = B O (1) .

By Lemma 1, PEM-efficient kernelizations to linear kernels exist, among others, for Dominating Set, Connected Dominating Set, and Induced Matching on all classes of apex-minor free graphs. Furthermore, by Lemma 2 there exist PEM-efficient parallel randomized kernelizations on H-topologicalminor free graphs for, among others, Chordal Vertex Deletion, Interval Vertex Deletion, Treewidth-w Vertex Deletion, and Edge Dominating Set. Moreover, the Width-b Vertex Deletion problem admits a linear kernel in the PEM model on H-topological minor-free graphs, where the width measure is either treewidth, branchwidth, rankwidth, or cliquewidth.

Computing Tree Decompositions in the PEM Model

In this section we present for every k a randomized PEM-efficient algorithm to decide the Treewidth-k problem. More precisely, for every k the algorithm computes a tree decomposition of a graph G of width k if there exists one.

We briefly state the I/O-complexities of the most important algorithmic problems in the PEM model. Sorting n records can be done by a multi-way merge sort with sort P (n) = Θ( n P B log d n B ) parallel I/Os for d = max{2, min{ n P B , M B }}, and P ≤ n B [START_REF] Greiner | Sparse Matrix Computations and their I/O Complexity[END_REF]. The problem of ranking a list of size n is fundamental in the (P)EM model and implies an efficient algorithm for the prefix sums problem [START_REF] Chiang | External-memory graph algorithms[END_REF][START_REF] Katriel | Elementary graph algorithms in external memory[END_REF][START_REF] Arge | Parallel external memory graph algorithms[END_REF]. Both can be solved with listRank P (n) = sort P (n) parallel I/Os if P ≤ n B 2 log B log (t) n , and M = B O(1) [START_REF] Arge | Parallel external memory graph algorithms[END_REF]. Note that we assume in this paper that all graphs are given by edge lists and each undirected edge {u, v} is represented by two directed edges (u, v) and (v, u).

A Framework for Parallel Treewidth Computation

Most tree decomposition algorithms follow a recursive approach [1,2,3]: by recursive application of a reduction rule, the input graph G is reduced to constant size for which a tree decomposition of width k can be given easily. By revoking a round of the application of the reduction rules, a tree decomposition is obtained which is only slightly too large. By using dynamic programming the width of this tree decomposition can be reduced to k, again. Our algorithm follows the approach presented by Bodlaender and Hagerup [START_REF] Bodlaender | Parallel algorithms with optimal speedup for bounded treewidth[END_REF] for dealing with the load balancing in the PRAM model. Its pseudo code, which also indicates a load balancing step, is presented in Algorithm 1.

In the following, for the three methods, reduce, treeDecompostionOfAtMost, and balance, the most important properties and implementation details are presented. They are presented in detail in the full version of this paper. Note that the correctness for all these algorithms follows directly from the original works [START_REF] Bodlaender | Parallel algorithms with optimal speedup for bounded treewidth[END_REF][START_REF] Maheshwari | I/O-efficient algorithms for graphs and bounded treewidth[END_REF].

Algorithm 1: Computing a Tree Decomposition in a parallel Model

1 G0 ← G 2 r ← d • log n 3 for 1 ≤ i ≤ r do 4 Gi ← reduce(Gi-1) 5 Tr ← treeDecompostionOfAtMost(Gr, k) 6 for r ≥ j ≥ 1 do 7 Tj-1 ← Tj ∪ (Gj-1 \ Gj)
// revoking changes of reduce round j The reduce Method: It was first presented by Bodlaender and Hagerup [START_REF] Bodlaender | Parallel algorithms with optimal speedup for bounded treewidth[END_REF]. One call (in round i) to the reduce method decreases the size of the input graph by a constant fraction 1 d ≥ 1 8 k by identifying disjoint pairs of vertices, so called acquainted twins. Therefore, after d• log n rounds, the resulting graph has constant size and thus a tree decomposition of constant width can be computed by brute force. Furthermore, revoking the vertex identifications of round i increases the width of the tree decomposition T i for G i+1 by at most k + 1.

The implementation is mostly a straight forward, but technical and careful, of the PRAM algorithm in the PEM model. It uses rounds of local operations, and information exchange, implemented by scanning and sorting. For finding vertices which can be identified in parallel a conflict graph of bounded degree, which represents if acquainted twins can be reduced in parallel, is computed. A fractional independent set (FIS) in the conflict graph then yields the vertices which are reduced in parallel. For computing a FIS of the conflict graph we observe that the PRAM algorithm of Dadoun and Kirkpatrick [START_REF] Dadoun | Parallel construction of subdivision hierarchies[END_REF] can be implemented efficiently in the PEM model.

Balancing a Tree Decomposition:

The method balance obtains from an arbitrary tree decomposition T = (T , B) of a graph G of width k a tree decomposition T b = (T , B ) of width at most = 7k . The most important property of T b is that T is balanced , meaning it is suited for processing computations on its nodes in a bottom up manner with at most O (listRank P (n)) parallel I/Os. To this end, a contraction tree T of T is computed. Based on the randomized algorithm for computing an independent set of Vishkin [START_REF] Vishkin | Randomized speed-ups in parallel computation[END_REF] an algorithm to compute a T can be obtained with at most O (listRank P (n)) parallel I/Os. Finally, the bags for T b can be computed in a bottom-up manner on the vertices of T .

The implementation of the balance method is a simplified version of the algorithm of Bodlaender and Hagerup [START_REF] Bodlaender | Parallel algorithms with optimal speedup for bounded treewidth[END_REF], yielding = 7k , instead of = 3k . However this affects only constants hidden in the asymptotic notation.

Computing a Tree Decomposition of Width k: Bodlaender and Hagerup [START_REF] Bodlaender | Parallel algorithms with optimal speedup for bounded treewidth[END_REF] use in their PRAM algorithm the algorithm of Bodlaender and Kloks [START_REF] Bodlaender | Efficient and constructive algorithms for the pathwidth and treewidth of graphs[END_REF] to compute from a tree decomposition of width for G, a tree decomposition of width k for a graph G. This is possible since the dynamic programming approach [START_REF] Bodlaender | Efficient and constructive algorithms for the pathwidth and treewidth of graphs[END_REF] is straight forward parallelizable.

Similar to their approach, in our algorithm, a modification of the algorithm for the EM model [START_REF] Maheshwari | I/O-efficient algorithms for graphs and bounded treewidth[END_REF] is used to implement treeDecompostionOfAtMost. For efficient parallelization, the algorithm obtains a balanced tree decomposition of width for a graph of size n.

Large parts of the algorithm of Maheshwari and Zeh can be reused, since it heavily uses scanning, sorting and prefix sum computations. The most challenging part is to return an actual tree decomposition, and not a corresponding implicit (intermediate) representation. Their data structure "Flippable DAG", which represents a DAG such that its entire edge set can be flipped (implicitly) with one I/O, is used in this process fundamentally. Precisely, their procedure to extract from a flippable DAG an explicit DAG uses time forward processing (TFP) [START_REF] Chiang | External-memory graph algorithms[END_REF]. Since it is not clear how TFP can be implemented efficiently in the PEM model we observe the following: in the case of computing a tree decomposition it is possible to store instead of one flippable DAG data structure a DAG and its "flip" explicitly. Therefore treeDecompostionOfAtMost does not rely on TFP anymore and can be implemented PEM-efficiently.

Analysis: The I/O-complexity of the three methods sketched in this section, reduce, balance, and treeDecompostionOfAtMost, are dominated asymptotically by sorting or list ranking. The methods are applied in the loops of Algorithm 1 repeatedly to different sizes of inputs, which geometrically decrease (respectively increase) from the initial input size n to constant size. Thus, the number of available processors increases relatively to the input size and the runtimes sort P (n) and listRank P (n) are not applicable anymore due to their processor bounds. The I/O complexity of list ranking equals the I/O complexity of sorting in a large parameter range but when applied with many processors (in relation to the input size) it dominates sorting. A detailed analysis yields the following term to capture the complexities of all loops:

O log n-(log(P B 2 log (t) n)-1) j=0 sort P n d j + log B =0 B log B log (t) n log M B n B + log(P B log (t) n) m=0 B log (t) n + log B log M B n B
The first sum can be bound by O (sort P (n)) since the input sizes are geometrically decreasing. The last sums can be bound by O (sort P (n)) due to the restrictions on P ≤ n/(B 2 log B log n log (t) n) and M = B O (1) , as stated by Theorem 3. This yields in total O (sort P (n)) parallel I/Os for computing a tree decomposition. Note that improvements of the parameter range would directly imply improvements on the parameter range of this algorithm.

Furthermore, observe that the bound on P is compared to the list ranking bound decreased by another log n factor. This seems natural, since the PRAM algorithm [START_REF] Bodlaender | Parallel algorithms with optimal speedup for bounded treewidth[END_REF] requires P ≤ n log 2 n , opposed to P ≤ n log n for sorting or list ranking in the PRAM model.

Replacing Protrusions

Let G be a graph, and

X ⊆ V (G), then ∂ G (X) is defined as the set of vertices in X having a neighbor in V \ X. Furthermore X is a r-protrusion of G if |∂ G (X)| ≤ r and tw(G[X]) ≤ r.
In this section we present PEM-efficient implementations of the (randomized) large protrusion finder, and the protrusion replacer of Fomin et al. [START_REF] Fomin | Planar F-deletion: Approximation, kernelization and optimal FPT algorithms[END_REF]. Both, protrusion finder and protrusion replacer, are be applied to n-vertex graphs G from classes G There is only one reduction rule which is applied repeatedly on the input graph G to reduce its size. This rule was introduced by Fomin et al. [START_REF] Fomin | Bidimensionality and kernels[END_REF]:

If G has a τ -protrusion X, then X is replaced by a constant sized graph Y ∈ R Π,τ , which is equivalent to X with respect to a relation ≡ Π,τ .

( )

An instance (G, κ) is called reduced if the reduction rule cannot be applied anymore to it. By [7, Lemma 1] for any parameterized problem Π which has finite integer index (FII) in a graph class G there exists for every fixed τ ∈ N such a finite set R Π,τ of representatives for the problem Π restricted to the graph class G. The safety of the reduction rule ( ) is proven in [7, p. 620].

Since R Π,τ depends on τ , our kernelization algorithm (as well as the known polynomial-time kernelizations of [START_REF] Kim | Linear kernels and single-exponential algorithms via protrusion decompositions[END_REF][START_REF] Fomin | Planar F-deletion: Approximation, kernelization and optimal FPT algorithms[END_REF]) is non-uniform in κ. On the other hand, in the following we may assume that R Π,τ is known explicitly to the algorithms.

By definition, R Π,τ is finite for every fixed τ and for every Π which has FII. Thus, the protrusion limit of Π restricted to a graph class G is well-defined as ρ Π,G (τ ) = max G∈R Π,τ |V (G)| [START_REF] Kim | Linear kernels and single-exponential algorithms via protrusion decompositions[END_REF].

The key result to be proven in this section is a PEM-efficient implementation of the reduction rule ( ). To this end, a randomized PEM-efficient protrusion finder yielding a set P of protrusions, and a PEM-efficient protrusion replacer, replacing constant sized protrusions, is presented. Since not all protrusions of P are of constant size, in Lemma 7, a PEM-efficient algorithm for replacing protrusions of unbound size, by constant sized protrusions, is presented.

PEM-Efficient Protrusion Finder

The protrusion finder is an algorithm that finds τ -protrusions such that every τ -protrusion X has size at least ρ Π,G (2τ ). The complexity of our PEM-efficient protrusion finder is the following: Lemma 5. The randomized fast protrusion finder of Fomin et al. [START_REF] Fomin | Planar F-deletion: Approximation, kernelization and optimal FPT algorithms[END_REF], for a input graph G of size n, can be implemented in the CREW PEM model with P ≤ n/(B 2 log B log n log (t) n) and M = B O (1) taking an expected number of O (sort P (n)) parallel I/Os. It yields a set P of τ -protrusions such that for every X ∈ P holds |X| > ρ Π,G (2τ ).

The proof of Lemma 5 is given in the full version of this paper. The algorithm is a straight forward implementation of the algorithm of Fomin et al. with special considerations on load balancing, using the connected components algorithm for graphs which are sparse under contraction of Arge et al. [START_REF] Arge | Parallel external memory graph algorithms[END_REF] and our new algorithm for tree decompositions (Section 2).

PEM-Efficient Protrusion Replacer

In this section, based on the ideas of Bodlaender et al. [START_REF] Bodlaender | Meta) kernelization[END_REF], a PEM-efficient algorithm is given for replacing all τ -protrusions in parallel. in which the lemma does not provide optimal bounds for the remaining graphs of size at most x = P B 2 log B log n log (t) n: The second term is in O (sort P (n)), since x P B log n is in O n P B by the processor bound P ≤ n/(B 2 log B log 2 n log (t) n). Since the sorting terms are geometrically decreasing, the first term is in O (sort P (n)), yielding the theorem.

A Permuting Lower Bound

To show a lower bound in the PEM model, we need a standard indivisibility assumption [START_REF] Aggarwal | The input/output complexity of sorting and related problems[END_REF]. More precisely, we assume that the node-identifiers that are used to describe the edges of the graph are atomic [START_REF] Jacob | On the complexity of list ranking in the parallel external memory model[END_REF].

A well known problem to which many computational problems can be reduced to is the Proximate Neighbors problem [START_REF] Chiang | External-memory graph algorithms[END_REF]. The input of the Proximate Neighbors problem are 2n atoms representing x 1 , . . . , x n , y π(1) , . . . , y π(n) . For solving the problem, a program which may be perfectly adapted to the permutation π, has to move the pair x i , y i into the same main memory at some time (and compare them on some CPU). Chiang et al. [START_REF] Chiang | External-memory graph algorithms[END_REF] have shown a permuting lower bound on the number of I/Os needed to solve this task in the EM model. Despite the absence of a speed up theorem [START_REF] Greiner | Sparse Matrix Computations and their I/O Complexity[END_REF] the lower bound can be extended to the PEM model [START_REF] Jacob | On the complexity of list ranking in the parallel external memory model[END_REF].

Hence, for reasonably big B, this justifies sorting for solving the proximate neighbors problem. Based on this result the following lower bound can be obtained easily: Theorem 5. Every randomized algorithm that can decide if a connected planar input graph is a tree must use Ω (min{n/P, sort P (n)}) parallel I/Os.

A connected graph G is a tree if and only if G has a tree-decomposition of width 1. This yields a lower bound of Ω (min{n/P, sort P (n)}) parallel I/Os for tree decomposition algorithms. Similarly, the problem Treewidth-1 Vertex Deletion on a planar graph, for the special case that there is no vertex deletion necessary has the same bound. This problem is covered by Lemma 1 and Lemma 2. Thus, we have matching upper and lower bounds for a large parameter range of Theorem 3 and Theorem 4.

Fig. 1 :

 1 Fig. 1: The Sequential and the Parallel EM Model for M = 12 and B = 3

8 Tj- 1 ← 9 Tj- 1 ←

 8191 balance(Tj-1) treeDecompostionOfAtMost(Tj-1, k) 10 return T0

  fixed graph H. Thus, all handled graphs G have E(G) = O(|V (G)|) edges, and our implementations run with O (sort P (|E(G)|))) = O (sort P (n)) parallel I/Os.

  x) ≤ O (sort P (n)) + sort P (x) log n

We first deduct an algorithm to replace constant sized τ -protrusions. For this task, there is a constant time algorithm ([23, Lemma 5]) in the RAM model. A trivial simulation of this algorithm requires not more than O (1) I/Os, which yields the following lemma: Corollary 6. Let H be a graph and let Π be a parameterized graph problem with finite integer index in G Recall that the protrusion finder of Fomin et al. finds a collection P of τprotrusions X of size |X| > ρ Π,G (2τ ). Since Corollary 6 can handle only protrusions of constant size, a PEM-efficient implementation of an algorithm [START_REF] Fomin | Planar F-deletion: Approximation, kernelization and optimal FPT algorithms[END_REF] is presented, which replaces protrusions which are larger than 2ρ Π,G (2τ ) by smaller (2τ + 1)-protrusions.

Since R Π,τ exists for a problem Π for all τ , the resulting protrusions can then be replaced by Corollary 6.

Lemma 7. Let τ ∈ N and let Π be a graph problem with finite integer index on a graph class G. Given for a graph G ∈ G, of size n, a set of τ -protrusions P, the expected number of parallel I/Os to find for all

The algorithm of Fomin et al. [START_REF] Fomin | Planar F-deletion: Approximation and optimal FPT algorithms[END_REF] used for Lemma 7 can be implemented by evaluating a tree expression evaluation on the nodes of a tree decomposition.

Applying the Protrusion Replacer

The randomized fast protrusion replacer of Fomin et al. [START_REF] Fomin | Planar F-deletion: Approximation, kernelization and optimal FPT algorithms[END_REF], respectively its PEM-efficient implementation, does not yield a kernelization yet. By Fomin et al. [START_REF] Fomin | Planar F-deletion: Approximation and optimal FPT algorithms[END_REF]Theorem 10] one application, transforming G into G , reduces, with high probability, the size of G by at least a constant fraction r > 0. Thus, for obtaining a linear kernel it has to be applied O (log n) times. We restate Theorem 4 and prove it. Proof. The value τ of the randomized fast protrusion replacer is chosen depending on κ as described by Fomin et al. [START_REF] Fomin | Planar F-deletion: Approximation, kernelization and optimal FPT algorithms[END_REF] and Kim et al. [START_REF] Kim | Linear kernels and single-exponential algorithms via protrusion decompositions[END_REF], respectively.

Using the I/O complexities given by Lemma 5, Lemma 7, and Corollary 6 the complexity of the algorithm is split up in a term when the number of processors is bigger than the processor bound of Lemma 5 and a term capturing the part


Tomoyuki Yamakami

Not All Multi-Valued Partial CFL Functions Are Refined by Single-Valued Functions (Extended Abstract)

Keywords: multi-valued partial function, CFL function, NFA function, refinement, pushdown automaton, context-free language, stack history

We give an answer to a fundamental question, raised by Konstantinidis, Santean, and Yu [Act. Inform. 43 (2007) 395-417], of whether all multi-valued partial CFL functions can be refined by single-valued partial CFL functions. We negatively solve this question by presenting a special multi-valued partial CFL function as an example function and by proving that no refinement of this particular function becomes a singlevalued partial CFL function. This contrasts an early result of Kobayashi [Inform. Control 15 (1969) 95-109] that multi-valued partial NFA functions are always refined by single-valued NFA functions. Our example function turns out to be unambiguously 2-valued, and thus we obtain a stronger separation result, in which no refinement of unambiguously 2valued partial CFL functions can be single-valued. Our proof consists of manipulations and close analyses of underlying one-way one-head nondeterministic pushdown automata equipped with write-only output tapes.

Resolving a Fundamental Question

Since early days of automata and formal language theory, multi-valued partial functions, ⋆ which are also known as transductions, computed by various types of automata equipped with supplemental write-only output tapes have been investigated extensively. Among them, we intend to spotlight CFL functions (also known as algebraic transductions), which are computed by one-way onehead nondeterministic pushdown automata (succinctly abbreviated as npda's) with write-only output tapes. These functions naturally inherit certain distinctive traits from context-free languages; however, their behaviors are in essence quite different from the behaviors of the language counterpart. Intriguing properties of those functions have been addressed in the past literature (e.g., [1-3, 6, 14]).

When the number of output values is restricted to at most one, we obtain single-valued functions. Concerning a relationship between multi-valued and single-valued partial functions, multi-valued partial functions in general cannot be single-valued; therefore, it is more appropriate to ask a question of whether multi-valued partial functions can be refined by single-valued partial functions, where "refinement" refers to a certain natural restriction on the outcomes of multi-valued functions. To be more precise, we say that a function g is a refinement of another function f [START_REF] Selman | A taxonomy of complexity classes of functions[END_REF] (which was also called "uniformization" [START_REF] Konstantinidis | Representation and uniformization of algebraic transductions[END_REF]) if and only if (i) f and g have the same domain and (ii) for every input x in the domain of f , all output values of g on x are also output values of f on the same input x. When g is particularly single-valued, g acts as a "selecting" function that picks exactly one value from a set of output values of f on x. This refinement notion is known to play a significant role in language recognition. In a polynomial-time setting, for instance, if we can effectively find an accepting computation path of any polynomial-time nondeterministic Turing machine, then every multi-valued partial NP function (computed by a certain polynomial-time nondeterministic Turing machine) has a refinement in the form of single-valued NP function. The "no-refinement" claim therefore leads to a negative answer to the long-standing P =?NP question.

We intend to discuss the same refinement question regarding CFL functions. In this line of research, the first important step was taken by Kobayashi [START_REF] Kobayashi | Classification of formal langauges by functional binary transductions[END_REF] in 1969. He gave an affirmative answer to the refinement question for multi-valued partial NFA functions, which are computed by one-way one-head nondeterministic finite automata (or nfa's, in short) with write-only output tapes; namely, multi-valued partial NFA functions can be refined by certain single-valued partial NFA functions. Konstantinidis, Santean, and Yu [START_REF] Konstantinidis | Representation and uniformization of algebraic transductions[END_REF] discussed the same question for CFL functions. They managed to obtain a partial affirmative answer but left the whole question open, probably due to a technical limitation of their algebraic treatments of CFL functions.

This paper is focused on CFL functions whose output values are particularly produced by npda's running in linear time ⋆⋆ (that is, all computation paths terminate in time O(n), where n is the size of input) with write-only output tapes. By adopting succinct notations from [START_REF] Yamakami | Immunity and pseudorandomness of context-free languages[END_REF], we express as CFLMV a collection of all such CFL functions and we also write CFLSV for a collection of all singlevalued functions in CFLMV. As a concrete example of our CFL function, let us consider f defined by setting f (1 n #x) to be a set of all substrings of x of length between 1 and n exactly when 1 ≤ n ≤ |x|. This function f is a multi-valued partial CFL function and the following function g is an obvious refinement of f : let g(1 n #x) consist only of the first symbol of x whenever 1 ≤ n ≤ |x|. Notice that g belongs to CFLSV.

Given two classes F and G of multi-valued partial functions, the notation F ⊑ ref G means that every function in F can be refined by a certain function in G. Using these notations, the aforementioned refinement question regarding CFL functions can be neatly rephrased as follows.

Question 2 Does Σ CFL k MV ⊑ ref Σ CFL k SV hold for each index k ≥ 1?
Yamakami [START_REF] Yamakami | Structural complexity of multi-valued partial functions computed by nondeterministic pushdown automata[END_REF] also shed partial light on this general question when k ≥ 3. He showed that, for every index k ≥ 3,

Σ CFL k-1 = Σ CFL k implies Σ CFL k MV ⊑ ref Σ CFL k SV, where Σ CFL k
is the kth level of the CFL hierarchy [START_REF] Yamakami | Oracle pushdown automata, nondeterministic reducibilities, and the hierarchy over the family of context-free languages[END_REF], which is a natural analogue of the well-known polynomial(-time) hierarchy. Since the collapse of the CFL hierarchy is closely related to that of the polynomial hierarchy, an answer to Question 2 (when k ≥ 3) could be quite difficult to obtain. Nevertheless, the remaining cases of k = 1, 2 have been left unsolved.

In this paper, without relying on any unproven assumptions, we solve Question 2 negatively when k = 1; therefore, our result completely settles Question 1. Our solution actually gives an essentially stronger statement than what we have discussed so far. To clarify this point, we first introduce a function class CFL2V as a collection of all functions f in CFLMV satisfying the condition that the number of output values of f on each input should be at most 2.

Theorem 3. CFL2V ̸ ⊑ ref CFLSV.
Since CFLSV ⊆ CFL2V ⊆ CFLMV holds, Theorem 3 clearly leads to a negative answer to Question 1. The proof of the theorem is essentially a manifestation of the following intuition: an npda relying on limited functionality of its memory device cannot simulate two independent computation paths simultaneously.

Instead of providing a detailed proof for Theorem 3, we wish to present a simple and clear argument to demonstrate a slightly stronger result regarding a subclass of CFL2V. To explain such a subclass, we first address that even if a function f is single-valued, its underlying npda may have numerous computation paths producing the same value of f on each input. Let us call an npda N with a write-only output tape unambiguous if, for every input x and any output value y, N has exactly one accepting computation path producing y. Let UCFL2V denote a class of all 2-valued partial functions computed in linear time by unambiguous npda's with output tapes. Succinctly, those functions are called unambiguously 2-valued. Obviously, UCFL2V ⊆ CFL2V holds.

Throughout this paper, we wish to show the following stronger separation result (than Theorem 3), which is referred to as the "main theorem."

Theorem 4 (main theorem). UCFL2V ̸ ⊑ ref CFLSV.
Following a brief explanation of key notions and notations in Section 2, we give in Section 3 the proof of Theorem 4, completing the proof of Theorem 3 as well. Our proof starts in Sections 3.1 with a presentation of our example function h 3 , a member of UCFL2V. The proof then proceeds, by contradiction, with an assumption that a certain refinement, say, g of h 3 belongs to CFLSV. In Section 3.2, the proof requires an introduction of "colored" automaton-a new type of automaton having no output tape-which simulates any npda equipped with an output tape that computes g. To lead to the desired contradiction, the proof further exploits special properties of such a colored automaton by analyzing the behaviors of its stack history (i.e., time transitions of stack contents) generated by this colored automaton. The detailed analysis is presented in Sections 3.3-3.6. All proofs omitted here will appear in a forthcoming complete paper.

Preliminaries

We wish to explain key notions and notations necessary to read through the rest of this paper.

Let N denote a set of all nonnegative integers and define N + = N-{0}. Given a number n ∈ N + , the notation [n] expresses an integer set {1, 2, 3, . . . , n}. An alphabet is a finite nonempty set of "symbols" or "letters." Given alphabet Σ, a string over Σ is a finite series of symbols taken from Σ and |x| denotes the length (or size) of string x. We use λ for the empty string. A language over Σ is a subset of Σ * , where Σ * is a set of all strings over Σ. Given two strings x and y over the same alphabet, x ⊑ y indicates that x is a substring of y; namely, for certain two strings u and v, y equals uxv. Moreover, given a string x and an index i ∈ [|x|], the notation (x) i expresses a unique substring made up only of the first i symbols of x. Clearly, (x) i ⊑ x holds. The notation |C| for a finite set A refers to its cardinality.

Let us consider multi-valued partial functions, each of which maps elements of a given set to subsets of another set. Slightly different from a conventional notation (e.g., [START_REF] Selman | A taxonomy of complexity classes of functions[END_REF][START_REF] Selman | Much ado about functions[END_REF]), we write f : A → P(B) for two sets A and B to refer to a multi-valued partial function that takes an element in A as input and produces a certain number of elements in B, where P(A) denotes the power set of A. In particular, when f (x) = Ø, we briefly say that f (x) is undefined. The domain of f , denoted by dom(f ), is the set

{x ∈ A | f (x) is not undefined }. Given a constant k ∈ N + , f is k-valued if |f (x)| ≤ k holds for every input x in A.
For two multi-valued partial functions f, g : A → P(B), we say that g is a refinement of f (or f is refined by g), denoted f ⊑ ref g, if (i) dom(f ) = dom(g) and (ii) g(x) ⊆ f (x) (set inclusion) holds for every x ∈ dom(g). For any function classes F and G, the succinct notation F ⊑ ref G means that every function in F has a refinement in G.

Our mechanical model of computation is a one-way one-head nondeterministic pushdown automaton (or an npda, in short) with/without a write-only output tape, allowing λ-moves (or λ-transitions). We use an infinite input tape, which holds two special endmarkers: the left endmarker | c and the right endmarker $. In addition, we use a semi-infinite output tape on which its tape head is initially positioned at the first (i.e., the leftmost) tape cell and moves in one direction to the right unless it stays still. Formally, an npda M with an output tape is a tuple (Q, Σ, {| c, $}, Γ, Θ, δ, q 0 , Z 0 , Q acc , Q rej ) with a finite set Q of inner states, an input alphabet Σ, a stack alphabet Γ , an output alphabet Θ, the initial state q 0 ∈ Q, the bottom marker Z 0 ∈ Γ , a set Q acc (resp., Q rej ) of accepting (resp., rejecting) states with Q halt ⊆ Q, and a transition function

δ : (Q -Q halt ) × ( Σ ∪ {λ}) × Γ → P(Q × Γ * × (Θ ∪ {λ})), where Σ = Σ ∪ {| c, $} and Q halt = Q acc ∪ Q rej .
We demand that M should neither remove Z 0 nor replace it with any other symbol at any step of its computation. Furthermore, the output tape is write-only; namely, whenever M writes a non-blank symbol on this tape, its tape head must move to the right. It is important to recognize two types of λ-move. When δ is applied to (q, λ, γ), M modifies the current contents of its stack and its output tape while neither scanning input symbols nor moving its input-tape head. When (p, w, λ) ∈ δ(q, σ, γ) holds, M neither moves its output-tape head nor writes any non-blank symbol onto the output tape.

Whenever we need to discuss an npda having no output tape, we automatically drop "Θ" as well as "Θ ∪ {λ}" from the above definition of M and δ. As stated in Section 1, we consider only npda's whose computation paths are all terminate within O(n) steps, where n refers to any input size, and this particular condition concerning the termination of computation is conventionally called the termination condition [START_REF] Yamakami | Oracle pushdown automata, nondeterministic reducibilities, and the hierarchy over the family of context-free languages[END_REF]. Throughout this paper, all npda's are implicitly assumed to satisfy this termination condition.

In general, an output (outcome or output string) of M along a given computation path refers to a string over Θ written down on the output tape when the path terminates. Such an output is classified as being valid (or legitimate) if the corresponding computation path is an accepting computation path (i.e., M enters an accepting state along this path). We say that an npda M with an output tape computes function f if, on every input x, M produces exactly all the strings in f (x) as valid outputs; namely, for every pair x, y, y ∈ f (x) if and only if y is a valid outcome of M on input y. Notice that an npda can generally produce more than one valid output strings, its computed function inherently becomes multi-valued. Because invalid outputs produced by M are all discarded from our arguments in the subsequent sections, we will refer to valid outputs as just "outputs" unless otherwise stated.

The notation CFLMV (resp., CFLkV for a fixed k ∈ N + ) stands for a class of multi-valued (resp., k-valued) partial functions that can be computed by npda's with write-only output tapes in linear time. When k = 1, we customarily write CFLSV instead of CFL1V. In addition, we define UCFLkV as a collection of all functions f in CFLkV for which a certain npda with an output tape computes f with the extra condition (called the unambiguous computation condition) that, for every input x and every value y ∈ f (x), there exists exactly one accepting computation path producing y on input x. It then follows that UCFLkV ⊆ CFLkV ⊆ CFLMV. Since any function producing exactly k + 1 values cannot be in CFLkV by definition, CFLkV ̸ = CFL(k + 1)V holds; thus, in particular, we obtain CFLSV ̸ = CFLMV. Notice that this inequality does not directly lead to the desired conclusion CFLMV ̸ ⊑ ref CFLSV.

To describe behaviors of an npda's stack, we closely follow terminology from [START_REF] Yamakami | Swapping lemmas for regular and context-free languages[END_REF][START_REF] Yamakami | Pseudorandom generators against advised context-free languages[END_REF]. A stack content is formally a series z m z m-1 • • • z 1 z 0 of stack symbols sequentially stored into a stack in such a way that z 0 is the bottom marker Z 0 and z m is a symbol at the top of the stack. We sometimes refer to a stack content obtained just after the tape head scans and moves off the ith cell of the input tape as a stack content at the ith position.

Proof of the Main Theorem

Our ultimate goal is to solve negatively a question that was posed in [START_REF] Konstantinidis | Representation and uniformization of algebraic transductions[END_REF] and reformulated in [START_REF] Yamakami | Structural complexity of multi-valued partial functions computed by nondeterministic pushdown automata[END_REF] as in the form of Question 1. In what follows, we will present an example function, called h 3 , which belongs to UCFL2V, and then give an explanation of why no refinement of this function is found in CFLSV, resulting in the main theorem, namely, UCFL2V ̸ ⊑ ref CFLSV.

An Example Function

Our example function h 3 is a natural extension of a well-recognized deterministic context-free language {x#x R | x ∈ {0, 1} * } (marked even-length palindromes), where # is a distinguished symbol not in {0, 1}. Let us define two supporting languages Proof. Obviously, h 3 is 2-valued. Let us consider the following npda M equipped with a write-only output tape. On any input w, M checks whether w is of the form x 1 #x 2 #x 3 in L by moving its input-tape head from left to right by counting the number of # in w. At the same time, M nondeterministically chooses a pair (i, j) ∈ I 3 , writes 0 i 1 j onto its output tape, stores x i into a stack, and then checks whether x R i matches x j by retrieving x i in reverse from the stack. If x R i = x j holds, then M enters an accepting state; otherwise, it enters a rejecting state. It follows by this definition that, for each choice of (i, j) in I 3 , there is at most one accepting computation path producing 0 i 1 j . It is not difficult to show that M computes h 3 . Therefore, h 3 belongs to UCFL2V.

L = {x 1 #x 2 #x 3 | x 1 , x 2 , x 3 ∈ {0, 1} * } and L 3 = {w | w = x 1 #x 2 #x 3 ∈ L, ∃(i, j) ∈ I 3 [x R i = x j ]}, where I 3 = {(i, j) | i, j ∈ N + , 1 ≤ i < j ≤ 3}. We then introduce the desired function h 3 by setting h 3 (w) = {0 i 1 j | (i, j) ∈ I 3 , x R i = x j } if w = x 1 #x 2 #x 3 ∈ L,
To complete the proof of the main theorem, it suffices to verify the following proposition regarding the existence of refinements of the function h 3 .

Proposition 2. The function h

3 has no refinement in CFLSV.

Colored Automata

Our proof of Proposition 2 proceeds by contradiction. To lead to the desired contradiction, we first assume that h 3 has a refinement, say, g in CFLSV. Since g is single-valued, we rather write g(x) = y instead of g(x) = {y} for x ∈ dom(f ). Take an npda N computing g with a write-only output tape. Let N have the form

(Q, Σ, {| c, $}, Γ, Θ, δ, q 0 , Z 0 , Q acc , Q rej ) with δ : (Q -Q halt ) × ( Σ ∪ {λ}) × Γ → P(Q × Γ * × (Θ ∪ {λ})), where Σ = Θ = {0, 1}.
Unfortunately, we find it difficult to directly analyze the moves of its outputtape head. To overcome this difficulty, we then try to modify N into a new variant of npda having no output tape, say, M . As seen later, this modification is possible because g's output values are limited to strings of constant lengths. Now, let us introduce this new machine, dubbed as "colored" automaton, which has no output tapes but uses "colored" stack symbols. Using a finite set C of "colors," a

colored automaton M = (Q ′ , Σ, {| c, $}, Γ ′ , C, δ ′ , q ′ 0 , Z 0 , Q ′ acc , Q ′ rej )
partitions its stack alphabet Γ ′ , except for the bottom marker, into sets {Γ ξ } ξ∈C ; namely,

∪ ξ∈C Γ ξ = Γ -{Z 0 } and Γ ξ ∩ Γ ξ ′ = Ø for any distinct pair ξ, ξ ′ ∈ C. We define a color of stack symbol γ to be ξ in C if γ is in Γ ′ ξ (= Γ ξ ∪ {Z 0 }).
Notice that Z 0 has three colors. Given a color ξ ∈ C, we call a computation path of M a ξ-computation path if all configurations along this computation path use only stack symbols in color ξ. An output of M on input x is composed of all colors ξ in C for which there is an accepting ξ-computation path of M on x. Lemma 1. There exists a colored automaton M that computes g. Proof Sketch. Recalling the set I 3 , we introduce a set Ī3 = {0 i 1 j | (i, j) ∈ I 3 } and another set Īpart 3 composed of all substrings of any strings in Ī3 . Recall the given npda N with a write-only output tape. Now, we want to define a new colored automata M = (Q ′ , Σ, {| c, $}, Γ ′ , Ī3 , δ ′ , q ′ 0 , Z 0 , Q ′ acc , Q ′ rej ) that simulates N as follows. Roughly speaking, on any input x, M first guesses (i.e., nondeterministically chooses) an output string t of g(x). Whenever N pushes u, M pushes its corresponding color-t symbol u (t) into a stack. Further along this computation path, M keeps using only color-t stack symbols. Instead of having an output tape, M remembers the currently produced string on N 's output tape. Whenever N enters an accepting state with an output string that matches the firstly guessed string t of M , M also enters an appropriate accepting state. In other cases, M rejects the input.

2

To simplify notations in our argument, we describe the colored automaton M guaranteed by Lemma 1 as (Q, Σ, {| c, $}, Γ, I 3 , δ, q 0 , Z 0 , Q acc , Q rej ). It is also useful to restrict the "shape" of M . A colored automaton M is said to be in an ideal shape if M satisfies all of the following six conditions. 1. There are only one accepting state q acc and one rejecting state q rej . Moreover, the set Q of inner states equals {q 0 , q, q acc , q rej }. The machine M is in state q during its computation except for the initial and final configurations. 2. The input-tape head of M always moves.

3. The machine M never aborts its computation; that is, δ is a total function (i.e., δ(q, σ, γ) ̸ = Ø holds for any (q, σ, γ) ∈ (Q -Q halt ) × Σ × Γ ). 4. Every stack operation either modifies a single top stack symbol or pushes extra one symbol onto the top of the stack after (possibly) altering the thentop symbol; that is, δ's range is P(Q × (Γ ∪ Γ 2 ) × (Θ ∪ {λ})). 5. The stack never becomes empty (excluding the bottom marker Z 0 ) at any step of the computation except for the initial and the final configurations.

In addition, at the first step of reading | c, M must push a stack symbol onto Z 0 and this stack symbol determines the stack color in the rest of its computation path. After reading $, M 's stack becomes empty. 6. The machine never enters any halting state before scanning the endmarker.

It is well-known that, for any context-free language L, there always exists an npda (with no output tape) in an ideal shape that recognizes L (see, e.g., [START_REF] Hopcroft | Introduction to Automata Theory, Languages, and Computation. Second Edittion[END_REF]). Similarly, we can assert the following statement for colored automata. Lemma 2. Given any colored automaton, there is always another colored automaton in an ideal shape that produces the same set of output values.

In the rest of this paper, we fix a colored automaton in an ideal shape, guaranteed by Lemma 2, which computes g correctly.

Hereafter, let us focus on inputs of the form x#x R #y for x, y ∈ {0, 1} * . For any x ∈ {0, 1} * , we abbreviate the set {y ∈ {0,

1} |x| | y ̸ ∈ {x, x R }} as H x . Given n ∈ N + , D (n)
(i,j) denotes a set of all strings x ∈ {0, 1} n for which there exists an accepting (i, j)-computation path of M on input x#x R #x. Obviously, it holds that D

(n) (1,2) ∪ D (n) (2,3) = {0, 1} n . It therefore holds, for every length n, that either |D (n) (1,2) | ≥ 2 n /2 or |D (n)
(2,3) | ≥ 2 n /2. We will discuss the case of |D

Case 1: D (2,3) is Large

Let us consider the first case where the inequality |D (n) (2,3) | ≥ 2 n /2 holds for infinitely many lengths n ∈ N. Take an arbitrary number n ∈ N that is significantly larger than 3 |Q|+|Σ|+|Γ | and also satisfies |D

(n) (2,3) | ≥ 2 n /2.
We fix such a number n throughout our proof and we thus tend to drop script "n" whenever its omission is clear from the context; for instance, we often write D (2,3) instead of D (n) [START_REF] Evey | Application of pushdown-store machines[END_REF][START_REF] Fisher | On computability by certain classes of restricted Turing machines[END_REF] . By the property of the colored automaton M computing g, it follows that, for any pair x, y ∈ {0, 1} n , if y / ∈ {x, x R }, then there always exists a certain accepting (1, 2)-computation path on input x#x R #y; however, there is no accepting (1, 2)-computation path on input x#x R #x for every x in D [START_REF] Evey | Application of pushdown-store machines[END_REF][START_REF] Fisher | On computability by certain classes of restricted Turing machines[END_REF] . In addition, no accepting (1, 2)-computation path exists on input x#z#y if z ̸ = x R . Since there could be a large number of accepting (1, 2)-computation paths of M on x#x R #y, we need to choose one of them arbitrarily and take a close look at this particular path.

For convenience, let P AT H n denote a set of all possible accepting (1, 2)computation paths of M on inputs of the form x#x R #y for certain strings x, y ∈ {0, 1} n . We arbitrarily fix a partial assignment π : D (1,2) × {0, 1} n → P AT H n that, for any element (x, y), if y ∈ H x , then π picks an accepting (1, 2)computation path of M on input x#x R #y; otherwise, let π(x, y) be undefined for simplicity. For brevity, we abbreviate π(x, y) as p x,y . Note that p x,y is uniquely determined from (x, y) whenever π(x, y) is defined.

Given an accepting (1, 2)-computation path p x,y of M on input x#x R #y, the notation γ (x) i,y denotes a stack content obtained by M just after reading off the first i symbols of x#x R #y along this particular path p x,y . Furthermore, we abbreviate as γ Proposition 3 gives a lower bound of the number of strings in (1), whereas Propositions 4 and 5 provide lower bounds for [START_REF] Evey | Application of pushdown-store machines[END_REF]. Those bounds, moreover, guarantee the existence of a string that satisfies both conditions, clearly leading to the desired contradiction.

Fundamental Properties of a Stack History

In the following series of lemmas and propositions, we will explore fundamental properties of a stack history of M along computation path p x,y on input of the form x#x R #y. Those properties are essential in proving the main theorem. Lemma 3. Fix x, y ∈ {0, 1} n . For any accepting (1, 2)-computation path p x,y of M on input x#x R #y, there is no pair (i 1 , i 2 ) of positions such that |x| < i 1 < i 2 ≤ |x#x R #| and γ i2,y2 . Now, we start estimating the lower bound of the number of strings x in D [START_REF] Evey | Application of pushdown-store machines[END_REF][START_REF] Fisher | On computability by certain classes of restricted Turing machines[END_REF] for which their corresponding stack contents γ (x) y are small in size for an arbitrary string y in H x . More specifically, we will verify the following statement.

and h 3 Proposition 1 .

 31 (w) = Ø if w is not in L. It thus follows that L 3 = {w ∈ L | h 3 (w) ̸ = Ø}. Now, let us claim the following assertion. The above function h 3 is in UCFL2V.

  3) | ≥ 2 n /2 in Section 3.3 and the case of |D (n) (1,2) | ≥ 2 n /2 in Section 3.6.

  |x#x R #|,y , which is produced just after reading x#x R # of the input x#x R #y. Note that, for each x ∈ D[START_REF] Evey | Application of pushdown-store machines[END_REF][START_REF] Fisher | On computability by certain classes of restricted Turing machines[END_REF] and any y ∈ H x , along an accepting (1, 2)-computation path p x,y on input x#x R #y, M produces unique stack contents γ (x) |x#|,y and γ (x) y . In Sections 3.4-3.6, we plan to evaluate how many strings in D (2,3) satisfy each of the following conditions. 1. Strings x in D (2,3) that make γ (x) y small in size for all y ∈ H x . 2. Strings x in D (2,3) that make γ (x) y relatively large in size for certain strings y ∈ H x .

  i2,y . Moreover, the same statement is true when1 ≤ i 1 < i 2 ≤ |x|.Lemma 3 can be generalized as follows.

Lemma 4 .

 4 Let x 1 , x 2 , y 1 , y 2 ∈ {0, 1} n , i 1 , i 2 ∈ N with 1 ≤ i 1 , i 2 ≤ |x 1 #x R 1 #|.Assume that one of the following conditions holds: (i) i 1 ̸ = i 2 , (ii) 1 ≤ i 1 = i 2 ≤ |x 1 #| and (x 1 ) i1 ̸ = (x 2 ) i2 , and (iii) (x 1 ) |x1#| = (x 2 ) |x1#| , |x 1 #| < i 1 = i 2 ≤ |x 1 #x R 1 #|, and (x 1 ) i1 ̸ = (x 2 ) i2 . It then holds that γ (x1) i1,y1 ̸ = γ (x2)

Question 1

 1 Is it true that CFLMV ⊑ ref CFLSV?Various expansions of CFLMV are possible. Yamakami[START_REF] Yamakami | Structural complexity of multi-valued partial functions computed by nondeterministic pushdown automata[END_REF], for instance, introduced a hierarchy {Σ CFL

			k	MV, Π CFL k	MV | k ≥ 1} of multi-valued partial
	functions built upon CFL functions by applying Turing relativization and a
	complementation operation. Its single-valued version is customarily denoted by
	{Σ CFL k	SV, Π CFL k	SV | k ≥ 1}. Our focal question, Question 1, can be further
	generalized to the following.

Proposition 3. There exist two constants d 1 , d 2 ∈ N + , independent of (n, x, y), such that |{x ∈ D [START_REF] Evey | Application of pushdown-store machines[END_REF][START_REF] Fisher | On computability by certain classes of restricted Turing machines[END_REF]

Hereafter, we will aim at proving Proposition 3. Given two strings u, v ∈ (Γ (1,2) ) * and a string z ∈ {0, 1} * , we say that M transforms u to v while reading z (along computation (sub)path p) if M behaves as follows along this subpath p: (i) M starts in state q with uZ 0 in stack, scanning the leftmost input symbol of z, (ii) M then reads z, with no endmarkers, from the input tape, (iii) after reading off z, M enters state q with vZ 0 in stack, and (iv) M does not empty the stack (except for Z 0 ). The notation T F M (τ, σ) expresses a set of all strings of the form z#z ′ for z, z ′ ∈ {0, 1} * such that M transforms τ to σ while reading z#z ′ . Lemma 5. Given any pair (u, v), there is at most one string x ′ such that x ′ is a substring of a certain string x in D [START_REF] Evey | Application of pushdown-store machines[END_REF][START_REF] Fisher | On computability by certain classes of restricted Turing machines[END_REF] and M transforms u to v while reading x ′ along a subpath of p x,y for a certain y ∈ {0, 1} n .

Next, we will show a key lemma, necessary to prove Proposition 3. Given a pair (x, y), we define M SC x,y (minimal stack contents) to be a collection of all stack contents γ satisfying the following: there exists a position ℓ with

indicates that the size of γ is minimum. Note that, when y ∈ H x , M SC x,y cannot be empty. In addition, by Lemma 4, all elements in {γ

There exists a constant d > 0, independent of (n, x, y), that satisfies the following statement. Let x ∈ {0, 1} n , y ∈ H x , and γ

|r|,y = τ vZ 0 , and γ (x) ℓ,y = σvZ 0 for an appropriate tuple (r, r ′ , z, s, σ, τ, u, v).

Assuming that Lemma 6 is true, we can prove Proposition 3 in the following manner. Since M SC x,y is non-empty, take an element γ

ℓ,y , there exists an appropriate tuple (r, r ′ , z, s, σ, τ, u, v) that satisfies

By the second part of Lemma 6, except for a certain constant number of x's, it always holds that ℓ ̸ = |x#|. The first part of Lemma 6 provides the desired constant d 1 that upper-bounds |γ (x) y |. We therefore obtain the proposition. To complete the proof of Proposition 3, we still need to verify Lemma 6. This lemma follows from Lemmas 7 and 8. In the first lemma, we want to show that the size of s in (*) is bounded from above by a certain absolute constant. Lemma 7. There exists a constant d 1 > 0, independent of (n, x, y), satisfying the following statement. Let x ∈ {0, 1} n , y ∈ H x , and γ

|r|,y = τ vZ 0 , and γ

|r|,y = τ vZ 0 , and γ

ℓ,y ∈ M SC x,y and z#z R s ∈ T F M (τ, σ). We first claim that s can be uniquely determined from (τ, σ).

Let us show this claim. Toward a contradiction, we assume that s ̸ = s 1 . Assume that M has an accepting (1, 2)-computation path p 1 while reading rz#z R sr ′ . Replace a portion of this path associated with z#z R s by a subpath corresponding to

We then obtain a new accepting (1, 2)-computation path on rz 2 #z R 2 s 2 r ′ . However, we obtain (rz

Therefore, the claim is true. The above claim helps us define a map from (τ, σ) to s. Thus, the number of all possible strings s is at most

This implies that |s| is upper-bounded by an appropriately chosen constant, independent of (n, x, y). 2

In the second lemma, we want to show that the size of r ′ in (*) is also upper-bounded by a certain absolute constant. Lemma 8. There exists a constant d 2 > 0, independent of (n, x, y), that satisfies the following statement. Let x ∈ {0, 1} n , y ∈ H x , and γ

ℓ,y = σvZ 0 , and γ

Finally, we will prove Lemma 6 with the help of Lemmas 7 and 8. In the subsequent argument, the notation E x expresses a collection of all stack contents γ (x) y at the |x#x R #|-th position (i.e., just after reading off x#x R #) along any accepting (1, 2)-computation path p x,y of M on input x#x R #y for an

Proof of Lemma 6. Let x = rz and x

Before proceeding further, we want to prove a useful lemma.

Proof. Assume that such a position i actually exists. We then swap between substrings x 1 #(x R 1 ) j and x 2 #(x R 2 ) j , where j = |x 1 #x R 1 #| -i, and we then obtain another accepting (1, 2)-computation path on input

2 #x 2 must be a rejecting path by the choice of x 2 ∈ D (2,3) , a contradiction. 2

Size of Stack Contents

Notice that |E x | ≥ 1 holds for all x ∈ D [START_REF] Evey | Application of pushdown-store machines[END_REF][START_REF] Fisher | On computability by certain classes of restricted Turing machines[END_REF] . Prior to a discussion on this general case, we intend to consider a special case, which exemplifies an essence of our proof, where |E x | = 1 holds for any x ∈ D [START_REF] Evey | Application of pushdown-store machines[END_REF][START_REF] Fisher | On computability by certain classes of restricted Turing machines[END_REF] .

Since the choice of y ∈ H x is irrelevant, it is possible to drop subscript "y" and express γ

y , and u x,y , as γ

, and u x , respectively. To lead to the desired contradiction, let us examine two stack contents, γ

To prove Proposition 4, let us consider two stack contents γ for any distinct pair x 1 , x 2 ∈ D [START_REF] Evey | Application of pushdown-store machines[END_REF][START_REF] Fisher | On computability by certain classes of restricted Turing machines[END_REF] . Lemma 9 implies that γ

x1 . We thus obtain the following.

Lemma 10. For every distinct pair

The function h is 1-to-1 on Bd and also 1-to-1 on at least a half of elements in B d -Bd by Lemma 10. Hence, it follows that

With the help of Lemma 11, Proposition 4 can be easily proven as follows.

Proof of Proposition 4. For simplicity, write d for (n

To complete the proof for the special case, let x = rz, x R = z R sr ′ , γ (x) = uvZ 0 , and γ

Assume that M transforms σ to u while reading r ′ . Proposition 3 shows that, for most of x's, |uvZ 0 | is upperbounded by a certain constant, independent of (n, x, y). However, by setting, e.g., ϵ = 98, Proposition 4 implies that |uvZ 0 | ≥ (n -100)/ log |Γ ′ (1,2) | for at least the 2/3-fraction of x's in D [START_REF] Evey | Application of pushdown-store machines[END_REF][START_REF] Fisher | On computability by certain classes of restricted Turing machines[END_REF] . Since n is sufficiently large, we obtain a clear contradiction.

II) General Case of |E

We have already shown how to deal with the case where |E x | = 1 holds for all x ∈ D [START_REF] Evey | Application of pushdown-store machines[END_REF][START_REF] Fisher | On computability by certain classes of restricted Turing machines[END_REF] . Now, let us discuss a general case where |E x | ≥ 1 holds for any x ∈ D [START_REF] Evey | Application of pushdown-store machines[END_REF][START_REF] Fisher | On computability by certain classes of restricted Turing machines[END_REF] . Our goal is to show the following statement.

Proposition 5. There are at least the |D

We start with the following lemma regarding E x 's, which can be seen as a generalization of Lemma 10.

Proof. Assume to the contrary that E x1 = E x2 holds for two particular elements

along an appropriate accepting (1, 2)-computation path p x2,y on x 2 #x R 2 #y. By swapping two parts of the above computation paths p x1,x2 and p x2,y properly, we then obtain another accepting (1, 2)-computation path of M on

x2 . This is an obvious contradiction against the choice of

. By taking an arbitrary x ∈ U n , we want to claim that a certain stack content τ ∈ E x must be made up of more than log |Γ | n/2 symbols. For this purpose, let us assume otherwise. Since any τ in E x has at most log |Γ | n/2 symbols, there must be at most n/2 different elements in E x . This implies that x / ∈ U n , a contradiction against the choice of x. Hence, we obtain |τ | > log |Γ | n/2, as stated in Proposition 5.

Case 2: Next, we assume that |U n | < |D (2,3) | 1/2 . We first prove the following combinatorial lemma. Lemma 13. Let n ∈ N + be sufficiently large and let X, Y satisfy X ⊆ Y . Let A be an X × Y matrix whose entries are taken from Θ * , where Θ is an alphabet. Assume that (i) |X| ≥ 2 n-2 and |Y | = 2 n , (ii) for any (x, y) ∈ X ×Y , A (x,y) = λ iff y ∈ {x, x R }, and (iii) for any x, y ∈ X, if A (x,y) ̸ = λ, then A (x,y) ̸ = A (y,z) for any z ∈ Y . Then, the set

Proof. Let us assume that the premise of the lemma is satisfied. For convenience, we define

x and set α = |E|. Notice that α ≥ 2. Hereafter, we want to claim that α ≥ 2 (n-3)/(2 log |Θ| n) . Toward a contradiction, we assume that α < 2 (n-3)/(

, where the second inequality comes from i < n/2 and ( α i ) ≤ α i /i!. This is a clear contradiction against |X ′ | ≥ 2 n-3 . Therefore, we obtain α ≥ 2 (n-3)/(2 log |Θ| n) .

However, this contradicts the bound of |E| ≤ log |Θ| n. 2

Let us return to the proof of Proposition 5. To apply Lemma 13, we simply set X to be D [START_REF] Evey | Application of pushdown-store machines[END_REF][START_REF] Fisher | On computability by certain classes of restricted Turing machines[END_REF] , {0, 1} n to be Y , and γ(x) y to be A (x,y) , where γ(x) y is obtained from γ (x) y by simply deleting Z 0 . It is not difficult to show that the obtained triplet (A, X, Y ) satisfies Conditions (i)-(iii) of the lemma. The lemma ensures that there are at least 2 n/3 x's in D [START_REF] Evey | Application of pushdown-store machines[END_REF][START_REF] Fisher | On computability by certain classes of restricted Turing machines[END_REF] satisfying |γ We then obtain a contradiction, as requested, and therefore this closes Case 1.

Case 2: D (1,2) is Large

We have already proven Case 1 in Sections 3.3-3.5. To complete the proof of Proposition 2, however, we still need to examine the remaining case where {n ∈ N + | |D [START_REF] Evey | Application of pushdown-store machines[END_REF][START_REF] Fisher | On computability by certain classes of restricted Turing machines[END_REF] | ≥ 2 n /2} is a finite set; in other words, |D (1,2) | > 2 n /2 holds for all but finitely many n. Recall from Section 3.2 the introduction of our colored automaton M = (Q, Σ, {| c, $}, Γ, I 3 , δ, q 0 , Z 0 , Q acc , Q rej ) with Q acc = {q acc } and Q rej = {q rej } that computes g. Before starting the intended proof, we will present a general lemma regarding inputs in reverse form. Lemma 14. There exists a colored automaton M R that satisfies the following: M accepts x 1 #x 2 #x 3 along an accepting (i, j)-computation path if and only if M R accepts x R 3 #x R 2 #x R 1 along an accepting (4 -j, 4 -i)-computation path. Let us return to our proof for the case of |D (1,2) | > 2 n /2. Note that, by running M on inputs of the form x#y#z for x, y, z ∈ {0, 1} n , we then obtain |D (1,2) | > 2 n /2. We consider a counterpart of D [START_REF] Choffrut | Properties of finite and pushdown transducers[END_REF][START_REF] Evey | Application of pushdown-store machines[END_REF] , denoted by D R

(2,3) , which is obtained by running M R instead of M . Lemma 14 also implies that |D R

(2,3) | > 2 n /2. Apply to D R (2,3) an argument used for Case 1. This is an obvious contradiction. We have therefore completed the proof of Proposition 2.