Gorka Aguirre

Aitor Pérez De Nanclares

Harkaitz Urreta

FAST CALIBRATION TOOLS AND STRATEGY FOR FIVE-AXIS MILLING MACHINE

INTRODUCTION

Geometrical accuracy is a key performance criterion for machine tools, with ever increasing requirements pushing machine builders to search for alternatives to keep the pace of the market. The trend to include workpiece measuring and validation functionalities in the machines emphasizes the need for accurate and traceable machines. Accuracy is typically limited by thermal effects (positioning errors dependent on temperature) in the first place, and geometric errors (positioning errors not dependent on temperature) in the second place. In five-axis machines, geometric errors gain relevance due to higher errors in rotary axes [START_REF] Schwenke | Geometric error measurement and compensation of machines-An update[END_REF][START_REF] Bringmann | Model-based "Chase-the-Ball" Calibration of a 5-Axes Machining Center[END_REF].

Software compensation of geometric errors has long been studied as a cost effective way of improving machine accuracy up to matching its repeatability [START_REF] Schwenke | Geometric error measurement and compensation of machines-An update[END_REF]. A wide variety of calibration methods have been proposed, based on different measurement tools and strategies and compensation models.

The focus of this work is on developing a fast and simple calibration solution for five-axis milling machines of medium to large working volume (a few m 3 of working volume). The goal is to enable the machine user to verify and calibrate the machine regularly with minimum machine occupation time, with relatively inexpensive equipment that can be integrated in the machine and operated by a regular machine operator.

FIGURE 1. 5 axis milling machine

The work will be demonstrated on a large milling machine, with three linear axes with moving column and two rotary axes in the spindle head.

STATE OF THE ART

A wide variety of methods have been proposed for measuring the accuracy of machine tools. Direct methods address error components individually. Positioning errors are typically measured with laser interferometers, straightness errors can be measured against straight references, such as taut wires or laser beams, or with laser interferometers and more complex optical paths. Angular errors can be measured with similar methods as straightness errors, but also electronic levels are a popular option. Finally, squareness errors can be measured against an angle standard, such as a granite or ceramic square, but also with laser systems [START_REF] Schwenke | Geometric error measurement and compensation of machines-An update[END_REF]. Direct methods provide good information on individual axis performance, but a full measurement of a machine would require a very long time and much equipment. Indirect methods involve simultaneous movements of all machine axes and provide an alternative which is typically better when all machine errors need to be measured. These methods are mostly based on physical calibrated artifacts and on laser tracking devices. Physical artifacts with features to be measured in 1D, 2D and 3D have been presented, and the error mapping is based on comparing the calibration of the artifact in a CMM and the measurement of the same features by the machine.

Laser trackers have gained popularity in the last years, mainly for the calibration of large machines, where artifacts face many limitations. Laser trackers measure directly 3D coordinates of a reflector mounted as a tool, providing a fast a convenient measurement. Their accuracy (typically tens of microns) is however not sufficient for high precision machines. This lead to the implementation of multilateration algorithms, where the workspace is measured sequentially from three or four different positions, improving significantly the calibration accuracy [START_REF] Schwenke | Error Mapping of CMMs and Machine Tools by a Single Tracking Interferometer[END_REF].

CALIBRATION STRATEGY

An artifact based calibration strategy is proposed here, adapted to fast and simple operation. The type of machines addressed here has a larger workspace than the workspace covered by the two rotations of the spindle head, and thus a sequential approach to error mapping is found most convenient.

In a first step, the workspace of the three linear axes will be mapped. A measuring head is installed on the machine, and it is used to measure the position of several spheres on an artifact. The artifact is placed on different positions in the machine workspace, and the different distances between the spheres measured by the machine are compared with the calibrated distances in order to obtain the 21 parametric errors of a 3 axis machine.

In order to minimize the measuring time, the calibration based on measurements in only two orthogonal planes is proposed here.

FIGURE 3. (left) errors in linear axis (right) errors in rotary axis

Once the compensation model of the linear axes is implemented, the measurements performed by moving the three linear axes can be considered precise enough, and remaining errors would come from the rotary axes. Taking advantage of this, the calibration of the two axes can be performed in a chase-the-ball style, but measuring against a fixed sphere and moving the two rotary axes. The measuring head allows for very fast measurement, and therefore a large number of positions can be measured. This allows the identification of more parametric errors that can be obtained with other measuring methods, and therefore a more precise compensation.

CALIBRATION INSTRUMENTS

The successful implementation of this strategy is based on the development of some measurement equipment that ensures high accuracy and fast and automated operation. The main development is a self-centering measuring head, which can measure on two adapted artifacts with precision spheres, one for calibration of linear axes and the other for rotary axes. The artifacts are presented first.

linear axes calibration artifact

"1D ball array" has been selected as the most suitable artifact for machine tool calibration, considering accuracy, usability, cost and possibility of automation and machine integration. This artifact contains 11 precision spheres evenly distributed over a length of 1500mm, thus with 150mm distance between them. As imposed by the measuring head that is presented later, the spheres are made of ferromagnetic material, stainless steel in this case. The spheres are of precision grade G25, which requires roundness error below 0.6 μm, for a diameter of 20mm.

The main requirement for its use as calibration reference is the stability of the relative positions between the spheres. The position of the spheres is calibrated on a CMM, and the measurements on the machine are compared to the CMM measurements, and therefore, this should not change with time, temperature or position and orientation in the machine.

A carbon fiber reinforced plastic (CFRP) tube has been chosen as structural material for the artifact, given the low weight, high stiffness and thermal stability it provides. The spheres are rigidly mounted onto the carbon fiber tube. The coefficient of thermal expansion of the tube is of 1μm/(m K) (approx. ten times lower than steel or cast iron), and thus for a 1.5m distance between spheres, the relative distance between them changes at most 1.5μm/K. Since the artifact changes very little with temperature, the effect of the temperature changes on the machine will be seen in the machine calibration, and it will be considered as part of the calibration uncertainty.

FIGURE 3. CFRP artifact in machine

In order to minimize the deformation of the artifact when it is mounted on the machine, the tube is always supported on two fixed points, located on the airy points of the tube. This means that the support points are symmetrically arranged around the center of the tube of length L and are separated by a distance d, defined by: d =L/√3=1.6/√ 3=0.923 m

rotary axes calibration artifact

The calibration of the rotary axes comes after the compensation of the errors of the linear axes. Thanks to this, the calibration can be done by measuring against a fixed sphere, and covering the whole workspace of the rotary axes. A tool for aligning the sphere with the rotary axis of the spindle is needed.

FIGURE 4. Setup for angular axis tests

Measuring head

Calibrated artifacts for the error mapping of CMMs and machine tools have been long used. One important limitation for its extensive use is the long time it takes to perform all necessary measurements. Standard touch probes are used, which require to contact the sphere in several points, making it a slow process. Contact force can also produce displacements on the artifact, which would add uncertainty to the calibration.

Measuring heads with three sensors arranged orthogonally have been developed, both based on contacting and non-contacting sensors, which can locate the center of the sphere in a single step. The machine is moved to a position where the sensors are in range, and the reading of the three sensors is process to find the machine coordinates where the sphere would be centered relative to the head.

In this case, the accuracy of the measurement depends on the accuracy of the measuring head. The three sensors need to accurately measure the distance to the sphere, and their position and orientation needs to be known accurately for the transformation of coordinates. In this work, an evolution of this measuring principle is presented which adds a selfcentering functionality. The accuracy of the measurement only relies then on the repeatability of the sensors and on an approximate knowledge of their orientation.

Configuration and self-centering principle

The measuring head proposed in this work contains three displacement sensors that measure the distance from the sensor to a target sphere. Non-contacting inductive sensors are used, which give an analogue voltage signal related to the distance to a ferromagnetic target.

The main innovation with this measuring head is the implementation of a self-centering function [5] that reduces the accuracy requirements on the measuring head without reducing the accuracy of the calibration. This is based on an iterative algorithm that moves the machine following the reading from the measuring head, bringing it to a nominal relative position between the sphere and the head.

Following this procedure, the position of the center of the sphere is taken from the machine axes positions. Therefore the accuracy of the measuring head does not influence the calibration, only the repeatability of the sensors in finding the nominal position with respect to the sphere. This allows for using simpler and cheaper displacement sensors, since the electronics for linearizing their output is not needed.

Standard measurement

CNC position X0, Y0, Z0

Control implementation

The control implementation of the self-centering functionality is summarized in Figure 7. There is a central control unit which governs all the calibration test. This is currently an external PC but could be integrated in the machine control if necessary. This control unit communicates with the measuring head, receiving continuously the reading from the three displacement sensors. The control unit is also in continuous communication with the machine control, reading axes positions. The PC is also able to send movement commands to the machine. Thanks to this, all the tests shown in this work are fully commanded from the external PC. A dedicated software has been developed which handles all the communication between the devices, runs all measurements and process the results.

Fig. 7: (A) Measuring head control implementation

The self-centering algorithm is implemented in the control unit. It follows the iterative diagram shown in Figure 10.

FIGURE 8. Self-Centering algorithm

Self-centering repeatability

The repeatability in reaching the nominal position around a sphere when the selfcentering function is activated is the best performance measure for the measuring head, and self-centering function, and it indicates the uncertainty that it adds to the machine calibration system. In this test, starting from the nominal position, random displacements are applied on the machine, within the range of the sensors, and the centering function is activated afterwards, which should lead the machine back to its nominal position. The variation in the machine coordinates to which the centering function converges is shown in Figure 9. High repeatability in the centering function is observed. FIGURE 9. Self-Centering repeatability

CONCLUSIONS AND FUTURE WORK

A new solution for five axis machine tool error mapping has been presented. Classical artifact based indirect calibration with 1D ball array has been selected as optimal solution for industrial application. The main novelty relies on the use of a low cost self centering measuring head and algorithm with micron range repeatability, and thus its validity for this application. Future work involves the practical implementation of the error mapping and compensation strategy on the machine.

FIGURE 2 .

 2 FIGURE 2. (left) ETALON Laser Tracer[START_REF] Schwenke | Error Mapping of CMMs and Machine Tools by a Single Tracking Interferometer[END_REF] (right) 3D ball plate artifact[START_REF] Bringmann | Machine tool calibration: Geometric test uncertainty depends on machine tool performance[END_REF]

  T E R I N G S T E P S C E N T E R V A R I A B I L I T Y ( M I C R O N S ) X Y Z


Factor structure evaluation of the French DNAS

Keywords:

Introduction: 'Digital natives' concept defines young adults particularly familiar with emerging technologies such as computers, smartphones or Internet. This notion is still controversial and so far the primary identifying criterion was to consider their date of birth. However, literature highlighted the need to describe specific characteristics. The purpose of this research was to evaluate the factor structure of a French version of the Digital Natives Assessment Scale (DNAS). Materials and methods: The sample of this study includes 590 participants from a six-week massive open online course and from websites, electronic forums and social networks. The DNAS was translated in French, then back-translated to English. Results: A principal component analysis with orthogonal rotation followed by a confirmatory factorial analysis showed that a 15-item-four-correlated-component model provided the best fit for the data of our sample. Discussion: Factor structure of this French-translated version of the DNAS was rather similar than those found in earlier studies. This study provides evidence of the DNAS robustness through cross-cultural and cross-generational validation. The French version of the DNAS appears to be appropriate as a quick and effective questionnaire to assess digital natives. More Factor structure evaluation of the French DNAS studies are needed to better define further features of this particular group.

Introduction

Digital natives concept was first introduced by Prensky [START_REF] Prensky | Digital natives, digital immigrants[END_REF] in 2001. They are defined as young adults familiar with digital technologies. With information and communication technologies growth in the early 2000, one has thought that youth surrounded by those new media may "think and process information fundamentally differently from their predecessors".

Digital natives can receive and deal with information quicker, are more used to multi-tasking, or are more sensitive to shortterm gratifications [START_REF] Selwyn | The digital nativemyth and reality[END_REF] . By contrast, Prensky opposed digital immigrants, older individuals who understand technology value but have to make the effort to immerse themselves in this new field as they know other ways of work, learn, live. As a consequence, a generation, digital-type, gap exists between digital natives and digital immigrants.

Since, existence of digital natives was particularly discussed in the literature. In this debate, lack of sound empirical evidence emerged as a major issue [START_REF] Jones | Describing or debunking? The net generation and digital natives[END_REF][START_REF] Bennett | The "digital natives" debate: A critical review of the evidence[END_REF][START_REF] Bennett | Beyond the "digital natives" debate: Towards a more nuanced understanding of students' technology experiences[END_REF][START_REF] Helsper | Digital natives: where is the evidence?[END_REF][START_REF] Watson | Digital Natives or Digital Tribes?[END_REF][START_REF] Demirbilek | Digital Natives" debate: An investigation of the digital propensities of University students[END_REF] . Some researchers argue that all digital natives do not share the same level of competencies and knowledge about technologies. They may differ according to habits and access to technologies 2,4-6,9- 14 . Even if one grows up with opportunities to use digital media, it does not mean that one will actually take advantage of this favorable context and use them. About this fact, Kennedy and collaborators stated that digital natives are comparable to a people speaking several dialects [START_REF] Kennedy | First year students' experiences with technology: Are they really digital natives[END_REF] . Furthermore, literature includes a set of relatively similar but interchangeably used labels: digital natives, generation Y, Net generation, millennials, etc. Watson proposed the term digital tribes as technology uses may be radically different with regard of numerous factors: countries, sociocultural environment, education, family context, etc. [START_REF] Watson | Digital Natives or Digital Tribes?[END_REF] . Lastly, Prensky himself changed his stance and spoke of a digital wisdom born from technology utilization and which will drive its reasoned use [START_REF] Prensky | Sapiens Digital: From digital immigrants and digital natives to digital wisdom[END_REF] .

Although critics remain to challenge this concept, many authors agreed that digital natives have advanced knowledge and abilities on emerging technologies. They share a unique relationship with these media, with significant consequences on their everyday life and even, for example, their cognitive processes (e.g., information processing, memory, attention, decision-making, etc.) [START_REF] Selwyn | The digital nativemyth and reality[END_REF][START_REF] Prensky | Sapiens Digital: From digital immigrants and digital natives to digital wisdom[END_REF][START_REF] Vasile | Digital era psychologystudies on cognitive changes[END_REF] . More than a revolution, one may however prefer thinking of an evolution. Nowadays, young people may learn and function differently, but not so far from their older counterparts [START_REF] Bennett | The "digital natives" debate: A critical review of the evidence[END_REF] . Some authors stand for a digital competence that everyone can acquire and develop through lifetime [START_REF] Hatlevik | Digital diversity among upper secondary students: A multilevel analysis of the relationship between cultural capital, self-efficacy, strategic use of information and digital competence[END_REF] .

Existing literature on digital natives echoes the variety of emerging technologies uses in young people, as well as their benefits and risks [START_REF] Bennett | Beyond the "digital natives" debate: Towards a more nuanced understanding of students' technology experiences[END_REF] . Research pointed specific risks faced by digital natives: higher inclination to engage in risky behaviors, to be unable to regulate their technology utilization, lesser efficiency of learning strategies when faced with diversity in content and sources, loss of critical thinking, etc. [START_REF] Selwyn | The digital nativemyth and reality[END_REF][START_REF] Dhir | Predicting adolescent Internet addiction: The roles of demographics, technology accessibility, unwillingness to communicate and sought Internet gratifications[END_REF][START_REF] Hayes | Understanding Facebook use and the psychological affects of use across generations[END_REF] .

However, other studies highlighted that children, adolescents and young adults keep a noticeable critical thinking on their technology uses [START_REF] Brito | Tweens' characterization of digital technologies[END_REF][START_REF] Mäntymäki | Digital natives in social virtual worlds: A multi-method study of gratifications and social influences in Habbo Hotel[END_REF][START_REF] Gurung | Digital learners and the overlapping of their personal and educational digital engagement[END_REF][START_REF] Borca | Internet use and developmental tasks: Adolescents' point of view[END_REF] . Other authors documented changes introduced by new media emergence on individuals, on their self-image or on relationships to objects or people [START_REF] Davis | Young people's digital lives: The impact of interpersonal relationships and digital media use on adolescents' sense of identity[END_REF][START_REF] Deal | Millennials at Work: What We Know and What We Need to Do (If Anything)[END_REF] .

Joiner and collaborators sought differences in attitudes and Internet utilization between first (i.e., born between 1980 and 1993) and second generation (i.e., born after 1993) of digital natives [START_REF] Joiner | Comparing first and second generation digital natives' Internet use, Internet anxiety, and Internet identification[END_REF] . They noticed that second generation members were more frequently committed in online activities, especially recreational activities. Other studies compared digital natives to digital immigrants, or even to older generations (i.e., baby boomers born between 1946 and 1964), looking to significant differences in digital technology adoption. [START_REF] Hayes | Understanding Facebook use and the psychological affects of use across generations[END_REF][START_REF] Joiner | Comparing first and second generation digital natives' Internet use, Internet anxiety, and Internet identification[END_REF][START_REF] Magsamen-Conrad | Bridging the divide: Using UTAUT to predict multigenerational tablet adoption practices[END_REF][START_REF] Moore | Interactive media usage among millennial consumers[END_REF][START_REF] Rasalingam | The Acceptance and Use of Online Shopping by the Digital Natives and Digital Immigrants[END_REF][START_REF] Suša | Digital Immigrants and Digital Natives: Learning Business Informatics at Higher Educational Level[END_REF] . However, identification of digital natives remains at stake. So far, the main criterion was to consider the date of birth, with individuals born after 1980 being digital natives [START_REF] Prensky | Digital natives, digital immigrants[END_REF][START_REF] Helsper | Digital natives: where is the evidence?[END_REF][START_REF] Prensky | Digital natives, digital immigrants Part 2 : Do they really think differently ? On the Horizon[END_REF] .

Later on, a second generation of digital natives was designated with Web 2.0 arrival in the second half of the 1990s [START_REF] Helsper | Digital natives: where is the evidence?[END_REF][START_REF] Joiner | Comparing first and second generation digital natives' Internet use, Internet anxiety, and Internet identification[END_REF] .

However, some authors stated that age is not a sufficient criterion. Of course, if many digital natives are young, every young people are not digital natives. Moreover, many individuals born before 1980 have integrated digital technology in their life to the extent they became as familiar if not more with it than youth [START_REF] Helsper | Digital natives: where is the evidence?[END_REF] . Factors like gender, education, technology experience (i.e., years of practice and age of first exposition) and habits have to be taken into account [START_REF] Helsper | Digital natives: where is the evidence?[END_REF][START_REF] Demirbilek | Digital Natives" debate: An investigation of the digital propensities of University students[END_REF][START_REF] Deal | Millennials at Work: What We Know and What We Need to Do (If Anything)[END_REF][START_REF] Drabowicz | Gender and digital usage inequality among adolescents: A comparative study of 39 countries[END_REF] .

To that end, Teo [START_REF] Teo | An initial development and validation of a Digital Natives Assessment Scale (DNAS)[END_REF] designed a scale to assess digital natives dimensions: the Digital Natives Assessment Scale (DNAS). Several adaptations of this scale already exist in other languages, but not in French [START_REF] Teo | Do digital natives differ by computer self-efficacy and experience? An empirical study[END_REF][START_REF] Teo | Exploring the digital natives among pre-service teachers in Turkey: a cross-cultural validation of the Digital Native Assessment Scale[END_REF] . This questionnaire includes characteristics likely to represent digital natives. Given the extent of the digital in our society, and especially in France, it is interesting to efficiently assess characteristics of these digital natives. Therefore, the aim of this study is to assess the factorial structure of a French-translated version of the DNAS. MOOC's subscribers were invited to take part in this project.

Materials and Methods

Setting

Participants had to give their consent on the first page of the dedicated online formulary designed for the assessment via LimeSurvey. Moreover, additional recruitments were organized on several websites and electronic forums focusing on digital media, as well as social networks.

Participants

The final sample includes 590 participants, with 62.7% of women. Participants are mainly students (48.6%) aged between 19 to 29 years (58.8%), single (49.8%) and without children (77.1%). Full sociodemographic details of the sample are available in Table 1.

(Insert Table 1 here Total score ranges from 21 to 147, with higher score indicating a higher likelihood to be a digital native.

Given that this questionnaire does not exist in French, we sought original author's approval before translating the scale in French. The DNAS was translated by the main author, then reviewed by the second, both with good knowledge of English. Iterations were discussed as long as there was not an agreement between both authors. A common version was then revised by an external bilingual person and was back-translated in English.

Statistical analysis

In order to increase confidence in the results and as we could not cross-validate results with two independent samples, we chose to randomly split the sample in half. The first subsample (n = 297) was used for the exploratory analysis and the second (n = 293) for the confirmatory analysis. Exploration of the factor structure of the questionnaire included a principal component analysis with orthogonal-varimax rotationaccording to analysis initially done by Teo [START_REF] Teo | An initial development and validation of a Digital Natives Assessment Scale (DNAS)[END_REF] . To determine the number of components to extract, the Kaiser rule of selecting eigenvalues greater than 1, the scree test and parallel analysis were used [START_REF] Nunnally | Psychometric Theory[END_REF][START_REF] Connor | SPSS and SAS programs for determining the number of components using parallel analysis and Velicer's MAP test[END_REF] . A confirmatory factor analysis was then undertaken on the model derived from the exploratory analysis.

Quality of the model, as well as comparison between potential models, was assessed with various indices [START_REF] Hu | Cutoff criteria for fit indexes in covariance structure analysis: Conventional criteria versus new alternatives[END_REF][START_REF] Schreiber | Reporting Structural Equation Modeling and Confirmatory Factor Analysis Results: A Review[END_REF] . Table 2 shows original and translated items labels from the DNAS as well as factor loadings after rotation. To be part of a component, an item had to have a cross loading ≥ .4, with minimal to no cross loadings with other factors [START_REF] Field | Discovering Statistics Using IBM SPSS Statistics[END_REF][START_REF] Costello | Best practices in exploratory factor analysis: Four recommendations for getting the most from your analysis[END_REF] The 20-item four-component model from the PCA was then assessed using a CFA (maximum likelihood). Following original analysis [START_REF] Teo | An initial development and validation of a Digital Natives Assessment Scale (DNAS)[END_REF] , each component was assumed to be correlated and allowed to covary with each other in the model. Moreover, all measurement errors were set to be uncorrelated.

Results

Factor

The chi-squared of this model was 285.82 (df = 164, p < .001).

Indices of fit were: χ 2 /df = 1.74; CFI = 0.921; TLI = 0.909; SRMR = 0.057; RMSEA (90% CI) = 0.050 (0.041-0.060) and AIC = 377.82. These results revealed an acceptable model fit, except for the CFI and TLI indices close but lower than 0.95.

We checked standardized covariances of residuals for values exceeding 2.58 and low values among standardized regression weights and square multiple correlations [START_REF] Byrne | Structural Equation Modeling With AMOS: Basic Concepts, Applications, and Programming[END_REF] . On the 190 standardized residual covariances, three exceeded the absolute value of 2.58 and involved item 10. Therefore, we removed this item. Moreover, we noted that three standardized regression weights were lower than the recommended value of .50, concerning items 4, 5, 7 and 21 [START_REF] Hair | Multivariate Data Analysis[END_REF] . We re-ran the CFA with 15 items. Indices of fit of this corrected model were: χ 2 (84) = 138.75 χ 2 /df = 1.65, CFI = .955; TLI = .944; SRMR = .050; RMSEA (90% CI) = .047 (.033-.061) and AIC = 210.75.

On the basis of Noar's recommendations [START_REF] Noar | The Role of Structural Equation Modeling in Scale Development[END_REF] , we tested and compared alternative models. The choice of models was made using theoretical conceptualizations from Teo [START_REF] Teo | An initial development and validation of a Digital Natives Assessment Scale (DNAS)[END_REF] . Model 1 is the 15-item 4-component model with correlated components previously shown whereas Model 2 assumes that components are uncorrelated. The last model (Model 3) proposed a 15-item factor structure. We compared as well our models to those designed by Teo [START_REF] Teo | An initial development and validation of a Digital Natives Assessment Scale (DNAS)[END_REF] . Results of these CFA are presented in Table 3. Among our three models, Model 1 has the best fit and is retained as final solution. Moreover, when compared to Teo's Model 3 (i.e., a 4-factor correlated, 21-item solution), the closest model to our Model 1, we found similar indices fit.

However, some notable differences exist in χ 2 value, χ 2 /df or RMSEA indices. Model 1 is represented in Figure 1.

(Insert Table 3 here) (Insert Figure 1 here)

Final factor solution examination

For every items, standardized regression weights were relatively large enough (i.e., .57 to .82, p < .001) to provide support for convergent validity within the scale [START_REF] Maruyama | Basics of Structural Equation Modeling[END_REF] 'Comfortable with multitasking' dimension refers to the fact that digital natives are used to attend with ease two or more personal, social, educational or professional activities in parallel [START_REF] Kennedy | First year students' experiences with technology: Are they really digital natives[END_REF] . Emerging technologies widely facilitated running multiple activities at the same time. 'Grow up with technology' dimension stands for digital natives being surrounded by digital media since their childhood [START_REF] Prensky | Digital natives, digital immigrants[END_REF] . Moreover, they often interacted with these technologies so that it becomes for them a natural way of life. By the 'Reliant on graphics for communication' dimension, one may refer to the fact that digital natives have a significant preference and an intuitive use of graphics-rich versus text-only environments. Communication via smartphones includes various graphical contents (e.g., pictures, smileys, movies, etc.) instead of only words and sentences.

Finally, the 'Thrive on instant gratifications and rewards' To conclude, the French version of the DNAS designed during this study seems to be appropriate as a quick and effective scale to assess digital natives. However, a future goal would be to draw a comprehensive profile of digital natives including sociodemographic and/or psychological variables.

The DNAS supports a definition of digital natives based not only on a date of birth but on a set of common characteristics.

Nonetheless, minor differences may still be observed between these digital natives. Another future aim could be to measure such digital natives' subgroups. Deal and colleagues noted that there are often more differences between individuals of the same generation than between individuals of separate generations [START_REF] Deal | Millennials at Work: What We Know and What We Need to Do (If Anything)[END_REF] . Substantial longitudinal studies could also give supplemental data on digital natives' trajectories of technology access and experience.

  This study was associated to a six-week Massive Open Online Course (i.e., MOOC) held by the University of Nantes during the first semester 2015. Main thematic of this course was related to digital use and its consequences on individuals. Beside this MOOC, a research protocol was conceived and declared to the National Commission on Informatics and Freedoms (declaration n°1803694, October 21th 2014).

)

  Digital Natives Assessment Scale (DNAS)The Digital Natives Assessment Scale is a selfassessment tool designed to measure whether an individual may be considered as a digital native. Validation of the scale highlighted a 4-factor structure with 21 items. Those factors are: Grow up with technology (five items, Cronbach's α = .89), Comfortable with multitasking (six items, Cronbach's α = .91), Reliant of graphics for communication (five items, Cronbach's α = .87) et Thrive on instant gratifications and rewards (five items, Cronbach's α = .87). Answers are made on a seven-point Likert scale, from 1 = strongly disagree to 7 = strongly agree.

  structure evaluation of the French DNAS Principal Component Analysis (PCA) We ran a PCA on the 21-item French version of the DNAS with orthogonal rotation (varimax). The Kaiser-Meyer-Olkin (KMO) was equal to .84, indicating a great sampling adequacy for the analysis. Moreover, all KMO values for individual items were superior to .73, above the acceptable limit of .5 39 . Bartlett's test of sphericity (χ 2 (210) = 1865.01, p < .001) meant that correlations between items were sufficiently large for PCA. During the analysis, four components had eigenvalues over Kaiser's criterion of 1 (Component 1 = 5.28; Component 2 = 2.49, Component 3 = 1.78 and Component 4 = 1.38) and explained in combination 52.07% of the variance. As both scree test and parallel analysis suggested a clear fourcomponent solution too, we extracted four components.

  . Correlations between factors were small enough (.25 to .59, p < .001) to suggest that they are sufficiently distinct from each other. This result provides evidence for discriminant validity. Cronbach's α for Component 1, Component 2, Component 3 and Component 4 are, respectively, .78, .70, .77 and .72, which shows good reliability. All item-total correlations are well above .3, as the lowest is .48 for item 12 on Component 3. This last result Factor structure evaluation of the French DNAS provides support for the factorial and construct validity of the DNAS 39 . Lastly, our sample has a mean score at Component 1 of 20.11 (SD = 5.84) with a minimum score of 4 and a maximum score of 28. Participants had as well a mean score on Components 2, 3, 4 of 23.67 (SD = 4.00; Min = 7; Max = 28), 15.13 (SD = 5.53; Min = 4; Max = 28) and 16.14 (SD = 3.41; Min = 3; Max = 21). The global mean score is 75.03 (SD = 13.05), with score able to range from 15 to 105 (Cronbach's α = .82).DiscussionThe main aim of this study was to further explore factor structure validity of a French version of the DNAS. Our analyses highlighted a 15-item 4-correlated-component structure. Factor structure found is relatively similar to the one from original study apart from six items rejection (i.e., items 4, 5, 7, 10, 15, 21). Cronbach's α of this shortened version are lower too. These results may be explained by our statistical analysis procedure which slightly differs from published articles. Nonetheless, the four dimensions representing digital natives according to Teo appeared in the results. Components 1, 2, 3 and 4 respectively correspond to Comfortable with multitasking, Grow up with technology, Reliant on graphics for communication and Thrive on instant gratifications and rewards dimensions. Moreover, correlations between each dimension testify of an underlying link.

  . All factor loadings but one (i.e., item 15) met these criteria. We removed this item from the final solution. Therefore, Component 1

	Factor structure evaluation of the French DNAS
	Confirmatory Factor Analysis (CFA)
	includes items 1, 3, 7, 11, 19; Component 2, items 2, 6, 10, 14,
	18; Component 3, items 4, 8, 12, 16, 20; and Component 4
	gathers items 5, 9, 13, 17 and 21.
	(Insert Table 2 here)

  For its part, education system knew how to change according to its students' affinity with technology1,15,16 .

	media. Therefore, digital natives may crave for immediate of a common nature of digital natives and their characteristics. useful as well for educational and health professionals for
	feedback to be satisfied 1 . Another way to explain this is to remind that emerging clinical and research purposes. It could help to recognize and
	technologies dissemination goes beyond frontiers and age better understand patients with higher levels of familiarity with
	This study provides evidence of the questionnaire
	groups. Consistent with what is found in the literature, the technology. Innovative and interactive interventions taking into
	solidity and its cross-cultural and cross-generational validity.
	digital gap is less linked to a generational gap than to account digital natives characteristics would be interesting to
	Indeed, original version was designed and tested in a sample of
	differences in technology access and use that can itself be offer.
	adolescents from New Zealand (mean age = 13.5) 32 . Later on, conditioned by age, socioeconomic or cultural groups 2,6,7,14,48 .
	adaptations were conceived. Yong and Gates administrated the
	Teo and collaborators stated that DNAS scores not really vary
	questionnaire to adolescents aged from 16 to 18 in Malaysia 45 .
	according to gender or age but more to years of technology
	Teo, Kabakçı Yurdakul, and Ursavaş designed a Turkish experience and perceived computer self-efficacy 33,34 . Akçayir
	version of the DNAS they used in a sample of 557 students
	et al. shared this finding and added that sociocultural context
	about age 20 34 . This translated version was later used in several
	has an impact on such scores 46 . Therefore, being a digital native
	other Turkish students samples 46,47 . Last, Teo developed a
	is acquired through favorable technology relationship.
	Chinese version of his questionnaire, with a sample of 402
	students 33 . Each study found a similar 21-item 4-factor So far, digital natives concept has mainly been used in
	structure. educational environment 10,16,30,32,49 . Teo himself estimated that
	DNAS would be useful for instructors, teachers, to better
	The present study is the first to assess DNAS validity in
	understand what define their students and how their
	European context. Moreover, our sample differs from those in
	dimension illustrates individuals looking to get without delay relationship with technology would influence learning and
	previous studies. So far, DNAS had been mainly used on young
	what they want/need. For example, to buy in few clicks a gift social collaboration. However, digital technologies spread
	people, from early adolescents to young adults. On the
	via the Internet instead of going physically to a store, searching exceeds educational and formation issues. Changes in practices
	contrary, our sample includes 67.8% of participants aged from
	and comparing goods before buying them. Internet and digital questions about abuses and associated risks especially among
	10 to 29, with a 58.8% of those aged from 19 to 29. Therefore,
	technologies changed how people work, learn or play. For the youngest generations. In 2001, Prensky stated that
	220 participants are older than 30. Despite this, we found a
	instance, large amount of information is now available from the graduates spent an average number of 5'000 hours over their
	factor structure relatively similar to those found in sample from
	Internet and communication is marked by instant messaging life to read versus 20'000 hours to watch TV and 10'000 hours
	separate countries, cultures, age groups. This result is in favor
	to play video games. Therefore, we think that DNAS would be

Table 1

 1 Sociodemographic Characteristics of the Sample

	Variables	n	%
	Age group
	10 -18	53	9.0
	19 -29	347	58.8
	30 -39	91	15.4
	40 -49	54	9.2
	50 and over	45	7.6
	Gender
	Female	370	62.7
	Male	220	37.3
	Education
	Less than 12 years	84	14.2
	12 years	104	17.6
	15 years	185	31.4
	17 years and over	217	36.8
	Current professional situation
	Unemployed	64	10.8
	Student	287	48.6
	With a job	230	39.0
	Retired	9	1.5
	Current marital situation
	Single	294	49.8
	In relationship	282	47.8
	Divorced, widowed	14	2.4
	With children
	Yes	135	22.9
	No	455	77.1
	Current housing
	Single	176	29.8
	With family members	145	24.6
	With spouse, wife, children	225	38.1
	With friends	44	7.5
	Note. N = 590.

Acknowledgements

Factor structure evaluation of the French DNAS This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors.

Author Disclosure Statement

No competing financial interests exist. Factor structure evaluation of the French DNAS


Amelia Carolina Sparavigna

The Ruins of the Buddhist Temples in the Progo Valley, Borobudur, Mendut and Pawon, Described by Isaac Groneman in his Book of 1912

Keywords:

Here we discuss the book entitled Ruins of Buddhistic Temples in Praga Talley: Tyandis Barabudur, Mendut and Pawon (available at archive.org/details/ ruinsofbuddhisti00gronrich), written by Isaac Groneman and published by H.A. Benjamins, Semarang

Isaac Groneman had a profound interest for the religious context of Candi Borobudur [1]. He considered Borobudur as a Buddhist sanctuary, obtaining support by King Chulalongkorn, at that time on his way to Java heading to explore civilization [1]. Groneman invited the king to Borobudur and this was "the beginning of friendship on the way to understanding the ancient Javanese heritage" [1]. And then, we find King Chulalongkorn mentioned in Groneman's book of 1912, published by H.A. Benjamins, Semarang. The book is entitled "Ruins of Buddhistic temples in Prägä valley: Tyandis Barabudur, Mendut and Pawon" (available at archive.org/details/ ruinsofbuddhisti00gronrich). In the title we find the word "tyandi", that is "candi", "temple".

The book is a remarkable discussion of the three temples, which are linked by a ritual relationship and by an alignment of the sites. The temples of Mendut and Pawon are thought to have been early purification temples for pilgrims going to Borobudur [START_REF] Norbert | Encyclopedia of Sacred Places[END_REF]. On the Vesak Day, a procession along the alignment of the temples goes from Mendut to Borobudur. In his book, Groneman is following the same approach, and the first temple he discusses is Candi Mendut.

Here we report only a few of the remarkable observations made by Groneman. The reader finds them quoted in the following sections. I am reporting in particular the discussions concerning the orientation of the temples, in reference to the path of the sun, and the descriptions of the mudras of the statues of Buddha. Actually, as discussed in [START_REF] Sparavigna | A short note about the zenithal sun and the Sewu, Prambanan and Borobudur temples in Java[END_REF][START_REF] Sparavigna | The Zenith Passage of the Sun and the Architectures of the Tropical Zone[END_REF][START_REF] Sparavigna | The Zenith Passage of the Sun at Candi Borobudur[END_REF], the Borobudur temple can be linked to the zenith passage of the sun, and to the zenith is referring a mudra of some of the Buddha's statues at Borobudur. To conclude this introduction, let us stress that the Groneman's book is an outstanding report about the temples of Mendut, Pawon and Borobudur. This book is therefore essential for anyone who is studying these temples, not only for the scholars but also for the persons fascinated by the Javanese antiquity.

Tyandi Mendut

The description of Mendut starts from an observation. "The first striking thing we see is that, in contravention to almost all other buddhistic buildings, the frontage of these ruins have not been placed opposite to the East, the sunrise, but strange enough, opposite to the Northwest". This Groneman's observation leads us to consider that the entrance of the temple is facing the processional walkway to Borobudur. Probably, the walkway started from a royal palace further east of Mendut.

The Mendut temple possesses two sculptures before the entrance. To the left, the sculpture represents a princess in a garden of fruit-trees, with a baby at her breast, and many children all round. To the right, we see "an Indian,not buddhistic -prince with much more children in such another garden". The children have a crescent of the moon on the hind part of their heads, but, as observed by Groneman, "both the children and their parents miss everything that might have spoken of a buddhistic character". Groneman tells that there are Dutch scholars who suppose the prince to be the Buddha's father and the woman to be the Buddha's mother. However, a different explanation of the sculptures was provided by the "buddhistic king of Siam", Chulalongkorn. Before giving the king's explanation, Groneman continues the description of the gigantic images we can see in this temple.

Inside the temple we find an altar-shaped throne, and on the throne sits a colossal Buddha statue, dressed in the manner of the southern Buddhists, having uncovered his right shoulder and arm. The hands before his breast have the posture (mudra) of the Mahayanists, that is, the followers of the "Big Carriage" (Great Vehicle).

Groneman explains that this is the posture that the followers "of the northern church, generally (not always) give to the first of their five Dhyani-Buddhas".

In the Mendut temple, to the right of Buddha, we see a buddhistic prince seated on a throne, which is richly decorated with nagas, lions, and elephants. He wears the monk's hood and a small Buddha image in his crown. This characterises him as a Buddhist. The other prince that we see opposite him, to the left of the Buddha, seating on an equally rich throne, doesn't wear a monk's hood. This characterises him as not buddhistic prince. The two kings wear the prabha, or disk of light, on the back of their heads. The Siam's king, who visited Mendut in 1896, interpreted the images as follow. One of the princes, who is wearing, "like he does himself, a Buddha image in his crown," was "perhaps the king of the buddhistic empire, under whose reign the Barabudur was built". Further the King supposed the other images to represent the not-buddhistic father and predecessor. The explanation of the king "became so comprehensible and logical to me -tells Groneman -that I could not but accept and defend it against others, and so I came to the hypothesis that the ashes of the two kings (but certainly the son's ashes) must have been buried in this tyandi".

Shailendra dynasty

A description of Mendut is given in [6], where we find that the temple was built around early ninth century AD.

Mendut is the oldest of the three temples, so it was built before Pawon and Borobudur [6]. From the Karangtengah inscription, we known that the temple was built and finished during the reign of King Indra of Sailendra dynasty.

The inscription is dated 824 AD. It is telling that King Indra "built a sacred building named Venuvana". The name means "bamboo forest". Archaeologist JG de Casparis has connected the temple mentioned in Karangtengah inscription with the Mendut temple [6,[START_REF] Chihara | Hindu-Buddhist architecture in Southeast Asia[END_REF].

The Shailendra dynasty was the name of an Indonesian dynasty that emerged in 8th century Java, whose reign marked a cultural renaissance in the region [8,[START_REF] Zakharov | The Sailendras Reconsidered[END_REF]. As told in [8], Shailendras were active promoters of Mahayana Buddhism and covered the Kedu Plain, also known as Probo Valley, of the Central Java, with several Buddhist monuments. One is the colossal stupa of Borobudur. The Shailendras are considered to be a thalassocracy, that ruled the maritime Southeast Asia [8]. But they have also promoted intensive rice cultivation on the Kedu Plain.

In [8] we can find that it is suggested that Shailendra was a native Javanese dynasty, and that the Sanjaya

Tyandi Pawon

After a detailed discussion of Mendut, Groneman continues describing Pawon. Leaving Mendut behind us, we cross shortly after a small iron bridge built over the river Elo. Then, after having been ferried over the Progo river, and moving westwards, we arrive at the "little dukuh of Brajanala … where we see the very small tyandi Pawon before our having turned into the broad kenari-avenue which leads" to Barabudur. Groneman tells that in the past this tyandi had been pulled down and afterwards rebuilt again. Its name, which means "kitchen", is "clear enough to make us understand how the Javanese would have shown the striking contrast between this small temple and the other more extensive one, as if it were a kitchen compared with a mansion or temple". Then Groneman explains why the temple was pulled down and then rebuilt.

The small ruin that Groneman sees has some conformity to the many grave temples, which are surrounding the main temple of Candi Sewu, in Prambanan valley. "But this conformity is not a perfect one". At Pawon, we find a small square room with a small porch, "we enter by means of some narrow treads flanked by the Garuda-Naga ornament, but this room is empty and unadorned". Shallow niches exist in each sidewall, in correspondence of the place where "once may have stood a pedestal and image". Like in Candi Mendut, Groneman explains that the niches may have been used to light the inner-part of the temple.

According to Groneman, this temple was a mausoleum built to receive an urn containing the ashes of a guru or monk. As in the case of Mendut, Groneman observes that "It is an extraordinary thing that even the entrance of this incontestably true buddhistic temple had not been made on the east side but to the west". Again we find an observation on the orientation of the temple. As we have already mentioned, this temple is on the processional walkway to Borobudur.

Borobudur Temple in 2013 (Courtesy 22Kartika, Wikipedia) Tyandi Barabudur "After having walked through the umbrageous kenari-avenue and the village of Bara … we shall arrive within half an hour at the hill upon which we see stand the pasanggrahan, and the colossal ruin". It is an "enormous mass of stone gradually developing itself in majestic lines and forms, in all the terraces, following each other in a regular range of succession till we see rise in their centre the high cupola now covered again by a cone with three sunshades".

It is a pilgrimage site and then "He who would approach this dagob to sacrifice his flowers to the Buddha, … was obliged to mount all these terraces, and walk along these sculptures". During this walk, the pilgrim can find in the temple a "revival of the Buddha and his doctrine", which is showing how to reach the nirvana, the "infinite not-to-be as the end purpose of all life, and the deliverance of all the miseries of a sensual existence". And then, let us follow, as Groneman did, "the way the pilgrim took, and mount the hill which carries this heavy mass of stone". So Groneman starts the discussion of first terrace of the temple.

Then we arrive to the doorways.

Four doorways are present in the structure, which are leading to stairs, that according to Groneman are the weak points of the architecture. At the foot of the doorway, there are naqa-heads, that "ended into outward turned mythical monster-heads which, at first sight remind us of elephants rather than of snake-like animals". Wilhelm von Humboldt and other European examiners, like the Dutch scholar Leemans, considered these monstrous figures as elephant's heads, "without perceiving however, that they changed into serpent's bodies when seen on the sideposts of the doorways". Also Groneman had been misguided himself, and defended this error against the King of Siam. But the King succeeded in convincing him, by logical argumentation, that the naga represents a power inimical to Buddhism. The monster, according to the Siam opinion, is Rahu "who also tries to devour the sun during every eclipse". Very interesting this observation linking the temple to astronomy.

As explained in [START_REF] Sarma | When Rahu Swallows the Sun: The Eclipse According to One Hindu Myth[END_REF], eclipses are battles between Rahu and the Sun, Surya. The myth referring to these battles concerns the amrita, the nectar of immortality, produced by the Churning of the Ocean of Milk. After this nectar has been prepared, it is distributed to the gods, the devas. In [START_REF] Sarma | When Rahu Swallows the Sun: The Eclipse According to One Hindu Myth[END_REF], it is told that Rahu. an asura (semi-god), sitting among the gods, was able to drink the amrita. But this fact was observed by Surya and Chandra, the Moon, and Visnu was alerted. Visnu decapitated Rahu. Having drunk "just a bit of the amrita", only Rahu's head was made immortal while his body died. It is the head of Rahu that attacks the Sun during the eclipses. The head swallows it, but Rahu has no body to digest the sun, and then the eclipse ends and the sun appears again [START_REF] Sarma | When Rahu Swallows the Sun: The Eclipse According to One Hindu Myth[END_REF].

After reporting the King's observation on Rahu, Groneman continues describing the first gallery. We see that the two walls of the gallery are decorated with imageries which are richly framed. An "uninterrupted band of exquisite festoons has been affixed above these sculptures under the cornice of the back-wall. … On the back wall we see similar temple-groups, but all of them, even the small niche-temples, are crowned with dagobs and cones".

Moreover we see rosettes and guirlandes with birds. On the five encircling walls of Borobudur, "we see no less than 432 niches provided with Buddha-images … We now turn to the left in order to begin our walk along the sculptures of the upper series of the back-wall. This wall is … showing us a comparatively well explained row of following events which give us an idea about the life of the Buddha Siddharta, Gautama, the Shakyamuni, from beginning to end".

Image courtesy https://pixabay.com/it/users/reggaelooper-3002941/

Here we find a remarkable observation. "Let us begin our walk to the left of the eastern staircase in order to return to our starting-point following the course of the sun of the northern hemisphere (29), going through the South, West and North. This order of succession regulated after this sun, we always find back on these and other Hindu ruins; more or less a witness of the northern origin of Javanese Buddhism". In the note (29), Groneman tells that he was the first (in 1887) to observe this link to the apparent course of the sun seen by the inhabitants of the northern hemisphere. "It is an important fact to those who believe the Buddha a sun-god". Let us stress that Candi Borobudur is placed in the tropical zone and therefore the path of the sun during the year is different from that observed in the northern hemisphere at latitudes above the Tropic of Cancer [START_REF] Sparavigna | A short note about the zenithal sun and the Sewu, Prambanan and Borobudur temples in Java[END_REF][START_REF] Sparavigna | The Zenith Passage of the Sun and the Architectures of the Tropical Zone[END_REF][START_REF] Sparavigna | The Zenith Passage of the Sun at Candi Borobudur[END_REF]. Therefore, the direction of the pilgrimage is honouring the northern origin of Buddha. For moving to reach the top of the monument, also the King of Siam followed this direction.

"For convenience' sake, and in order to assist the visitor in finding" the sculptures, Groneman counts them "from the preceding staircase or from the first till the ninth wall-angle, and begin with the eastern staircase". And then Groneman starts discussing the scenes related to Buddha's life.

The discussion of all the other statues continues in the Chapters VIII and IX.

In Chapter X we arrive at the top of the monument, where we find three circular terraces. On the first "we see stand 32 open worked dagobs or tyaityas; on the second there are 24, -and on the third and highest 16, so altogether 72. And within this circle rises the majestic middledagob as the only real dagob or stupa representing the leading idea, the final purpose of the whole ruin". We can also admire the surrounding mountainous landscape. The valley of Progo river lies westward "at the foot of mount Menoreh, … and, to the east, of the high twin volcanoes Merbabu and Merapi, and, to the north, of the Sumbing, the highest volcano of this part of Central Java".

Image Courtesy Pandu Adnyana, Wikipedia.

Mudras of Buddha

I found the book of Groneman when searching for some discussion about the statues of Buddha and the fact that they have different mudras, that is, positions of the hands, linked to North, East, South, West and Zenith, which represent the five cardinal compass points according to Mahayana.

As told by Wikipedia [11], at Borobudur, "the first four balustrades have the first four mudras: North, East, South and West, of which the Buddha statues that face one compass direction have the corresponding mudra. Buddha statues at the fifth balustrades and inside the 72 stupas on the top platform have the same mudra: Zenith. Each mudra represents one of the Five Dhyani Buddhas; each has its own symbolism". The reference given for this discussion is [START_REF] Bucknell | The Twilight Language: Explorations in Buddhist Meditation and Symbolism[END_REF].

In the Chapter XI we find what Groneman tells about the statues representing Buddha. We can see that all the statues are in a sitting posture with crossed legs, "almost in the same posture the Javanese call sila, but upright". The statues are dressed with a thin mantle uncovering their right arms and shoulders. They have the tiara, the round hair-knot, "on their heads all covered with short curls. Even the urna, the little tuft of hair on their fronts is still to be seen on many a sculpture, and on the other ones, less accurately hewn, they are forgotten". For what concerns the posture of all the statues, Groneman notes that it is showing resignation and peace, "and may speak of the later final dissolving in the nirvana, the joy and painless not-to-be".

About the mudras of the statues of Buddha we find a detailed discussion. "Among the sculptures placed opposite the five zones of heaven, the East, South, West and North and the Zenith, there is to be seen a slight difference in the posture of the right hands, and something more difference in the posture of the two hands with regard to those sculptures we see on the round terraces".

All the sculptures on the five encircling walls have their left hands in their laps, with the palm on the right foot. Then Groneman describes in details the corresponding postures of the hands, the mudras. For what concerns the sculptures of the open worked tyaityas on the three round terraces, the statues raise their two hands before the epigastric region, "the left one with the palm and the bent finger-tips in an upward direction, the right one with the palm to the left and the fingers bent over those of the other hand". Moreover, these statues "all miss the glory". Groneman is then mentioning Wilhelm Von Humboldt, telling that he was the first who considered five of the six Buddhas, to be the representations of the five Dhyani-Buddhas. "Especially in the posture of the hands there is some conformity between five of the six Barabudur-images and the five Dhyani-Buddhas such as we see them hewed in Asia". Moreover Groneman is mentioning Alfred Foucher.

According to Foucher, there are seven groups of mudras. They are: 1) the bhunisparsya mudra (East); 2) the vara-mudra (South); 3) the dhyani-mudra (West); 4) the abhaya-mudra (North); 5) in the 64 niches on the fifth and highest wall the vitarka-mudra (the gesture of discussion); and among the 72 cupolae of the 3 circular terraces, 6) the dharma-tyakra-mudra (mark of distinction).

Finally, we find the only sculpture from the wholly closed dagob, hewed in the bhumi-sparsyamudra. After referring about these mudras, Groneman stresses that a slight difference exists between Foucher's ideas and his own ideas, which are supported by the observations of King Chulalongkorn.

Let us conclude our article on the Groneman's book -a book essential for anyone who is studying Borobudur -as he concluded his discussion on the mudras. He tells that in Borobudur, we can find Buddha hewed as preacher, "preaching the doctrine to all people, and consequently towards all the regions of heaven". According to Groneman the fact that this preaching preacher "has been placed upon the highest wall" of the monument is easy to understand, because the preaching of the doctrine is the highest expression of Buddhism, "and possibly referred to both the world of the four zones of heaven and to the one of the celestials in the zenith".

  dynasty was a branch of the Shailendras. So the members of the Shailendra family were initially the rulers of the Medang Kingdom. As we can read in [8], the association of Shailendra with Mahayana Buddhism began after the conversion of Panaraban or Panangkaran to Buddhism. The Tale of Parahyangan tells that the King Sanjaya ordered his son, Rakai Panaraban or Panangkaran, to convert to Buddhism, "because their faith in Shiva was feared by the people in favor of the pacifist Buddhist faith" [8]. Actually, this is in agreement to the King Chulalongkorn's observation.

  One of the 72 statues of Buddha in open worked tyaityas on the three round terraces. Photographer Giovanni Boccardi. For the UNESCO Connected Open Heritage project. Groneman tells that there is still another sculpture, unique of its kind. It had been found in the middle-dagob. It is a Buddha image corresponding in size to all other sculptures, but the posture of the hands "tallied with those on the eastern lower walls". After a discussion about this specific statue, Groneman distinguishes the statues into three groups: 1. 432 Buddhas in the open templeniches on the five encircling walls, which are seated on lotus-thrones and crowned with glories. 2. 72 Buddhas in the open worked tyaityas on the three round terraces, without any glory or lotusthrone. 3. The only Buddha of the large dagob entirely sequestered, without glory or throne.


Cristian Dumitrescu
email: cristiand43@gmail.com

A randomized, efficient algorithm for 3SAT

Keywords: NP-complete problems, 3SAT 1 M, 2 M, 3 M, … …

come

A randomized, efficient algorithm for 3SAT

Introduction

The importance of efficiently solving NPcomplete problems is due to the fact that this would imply that all the other problems belonging to the NP class can be efficiently solved in a constructive manner (the algorithms can be generated for all of them through polynomial -time reductions).

It is well known that 3SAT is NP-complete.

Proposition 1. (see [Papadimitriou,94] and [START_REF] Hopcroft | [END_REF]). 3SAT is NPcomplete.

Proof. For the proof, see (see [Papadimitriou,94] and [START_REF] Hopcroft | [END_REF]).

We will first present a well known randomized algorithm for 3SAT. This is Schöning's algorithm from 1991 (see [Schöning, 1991]). We also note that Papadimitriou also discussed a similar algorithm for 2SAT in 1991 (see [Papadimitriou, 1991]).

It is known that Papadimitriou's algorithm finds a solution in quadratic time with high probability for 2SAT. Only exponential bounds are known for Schöning's algorithm for 3SAT.

Stochastic local search algorithms played an important role, related to SAT solvers. This includes the random walk algorithm of Papadimitriou for 2SAT, and Schöning's extension of this algorithm for 3SAT.

Schöning's algorithm for 3SAT

Input: a 3SAT expression in 𝑛 variables.

Guess an initial truth assignment, uniformly at random.

Repeat 3 • 𝑛 times:

If the expression is satisfied by the actual assignment, stop and accept.

Let C be some clause not being satisfied by the actual assignment. Pick one of the three literals in the clause at random, and flip its truth value.

Update.

Stop and reject, the expression is not satisfiable.

Note that these algorithms involve random walks on the boundary of the truth assignment hypercube (the unit hypercube where each vertex represents a truth assignment). The fundamental and new idea in this article is to consider stochastic local search algorithms through the bulk (the interior) of the truth assignment hypercube (which becomes the truth valuation hypercube). This will become clear in section 2, when the concept of truth valuation will be introduced. We will formulkate a conjecture and present strong arguments that the algorithm presented in section 2 is polynomial (even for the worst case instances of 3SAT).

A different type of algorithm (this is a hill climbing algorithm, not directly related to Papadimitriou or Schöning's algorithms), but also based on the concept of truth valuations, is given in [A2].

Still another type of algorithm (the clustered Sparrow algorithm) is presented in [A4].

The extension of Schöning's algorithm

We assume that the reader is familiar with the random walk model (based on the Hamming distance to a solution) associated with the algorithm. This is discussed in detail in [Schöning, 1991], and [Papadimitriou, 1991].

Definition 1. In the following, M will be a natural number, in general smaller than n. A truth valuation v(x) is a function from the set of variables {x 1 ,x 2 , x 3 , … … . x n } to the set of values {0,

rational number from the set {0, 1 M , 2 M , 3 M , … … . , M-1 M , 1}
. We note the difference between a truth valuation and a truth assignment, where the truth assignment for a variable can be only 0 or 1. We also note that in general (as used for the truth valuation of a clause), a truth valuation is a real value in the interval [0, 1]. Definition 2. Given two truth valuations for n variables (𝑣 1 (x 1 ), 𝑣 1 (x 2 ), 𝑣 1 (x 3 ), … … 𝑣 1 (x 𝑛 ) ) , and (𝑣 2 (x 1 ), 𝑣 2 (x 2 ), 𝑣 2 (x 3 ), … … 𝑣 𝑛 (x 𝑛 ) ) , the Hamming distance between these truth valuations is by definition

𝑑(𝑣 1 , 𝑣 2 ) = |𝑣 1 (x 1 ) -𝑣 2 (x 1 )| + |𝑣 1 (x 2 ) -𝑣 2 (x 2 )| + ⋯ … . . + |𝑣 1 (x 𝑛 ) -𝑣 2 (𝑥 𝑛 )|.
The normalized Hamming distance is just the Hamming distance divided by the length of one step, which is

1 M . Definition 3. The truth valuation of 𝑥 ˅ 𝑦 is v(x ˅ y) = v(x) + v(y) -v(x) • v(y).
The valuation of the negation of a variable ¬x is v(¬x) = 1 -v(x). It is clear that if we are given a truth valuation for the n variables that appear in a 3SAT expression, then for any 3SAT clause we can calculate the truth valuation of that clause

v(x ˅ y ˅ z) = v(x) + v(y) + v(z) -v(x) • v(y) -v(x) • v(z) -v(y) • v(z) + v(x) • v(y) • v(z)
. The truth valuation of the whole 3SAT expression is the product of the truth valuations of all the clauses.

Extension of Schöning's algorithm for 3SAT

Input: a 3SAT expression in 𝑛 variables. Initialize all variables with the truth valuation 1 2 (or following a uniform distribution on the states of the class 𝑆 0 , described below).

Repeat 4 • 𝑛 2 • 𝑀 2 times:

If the current truth valuation is a satisfying truth assignment, then stop and return the satisfying truth assignment.

Let C be some clause that has a minimal truth valuation. If there are more than one, then pick one at random. . Choose one of the literals in the clause at random ,and if its current truth valuation is not 0 or 1, then with equal probability

Stop and reject, the expression is not satisfiable.

The purpose of this paper is to prove that this algorithm finds a solution (if it exists) with high probability. We will need some preparatory propositions.

Proposition 2. We consider the case of one dimensional symmetric random walks with one unit steps (like the coin tossing game). For fixed t, the probability that the first passage through r occurs before epoch t

• r 2 tends to √ 2 π • ∫ e -1 2 •s 2 ds ∞ 1 √t = 2 (1 -R( 1 √t
)) , as r → ∞ , where R is the normal distribution.

Proof. For the proof, see [Feller, 1968], chapter 3. This means that the waiting time for the first passage through r increases with the square of r. The expected traveled distance in r 2 steps is r.

We note that similar to the random walk model ( [Schöning, 1991], and [Papadimitriou, 1991]), we have here a Markov chain. At any moment, if the current truth valuation of the variable is not 0 or 1, then the Hamming distance from the current truth valuation (for all the n variables) to the truth assignment solution (if it exists) can increase or decrease by . But at certain moments, the Hamming distance will increase or decrease with probability 1 (when the current truth valuation gives the corresponding variable the value 0 or 1). We do not have a pure random walk, as in the original models. We will call this the primary Markov chain, associated to the Hamming distance to a solution. The states of the primary Markov chain indicate the Hamming distance towards a solution.

We also note that we have n one dimensional symmetric random walks with reflecting barriers at 0 and 1 (each such random walk is associated to the truth valuation of a single variable). We will call these the secondary random walks with reflecting barriers. The states of the n secondary random walks with reflecting barriers indicate the current truth valuation of the corresponding variable.

Proposition 3. The secondary random walks with reflecting barriers have stationary distributions.

Proof. In the secondary random walks with reflecting barriers, when we say that we are in state The probability transition matrix is:

                                       0 1 0 0 0 0 0 0 2 1 0 2 1 0 0 0 0 0 0 2 1 0 2 1 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 2 1 0 2 1 0 0 0 0 0 0 2 1 0 2 1 0 0 0 0 0 0 1 0                  A If we write ( 𝜋(0), 𝜋 ( 1 𝑀 ) , 𝜋 ( 2 𝑀
) , … … . , 𝜋(1) ) for the stationary distribution, it will be the solution of the system of equations (this is a 1 × (M + 1) row matrix multiplied by a (M + 1) × (M + 1) square matrix):

( π(0) π ( 1 𝑀 ) π ( 2 𝑀 ) … … . π(1) ) • A = ( π(0) π ( 1 𝑀 ) π ( 2 𝑀 ) … … . π(1) ) .
When we solve this system of equations, we will find:

π(0) = π(1) = 1 2M π ( 1 𝑀 ) = π ( 2 𝑀 ) = π ( 3 𝑀 ) = ⋯ … . = π ( 𝑀-1 𝑀 ) = 1 M .
This stationary distribution is an equilibrium distribution. We need some results related to the convergence towards a stationary distribution for periodic chains.

Definitions 4. Two states in a Markov chain are in the same class if we can go from one to another in a finite number of steps with positive probability. A Markov chain is said to be irreducible if all states are in the same class. A recurrent state is one for which the probability that the Markov chain will return to it after a finite time is one. Assume that state j is a recurrent state. Let I = {n ≥ 1; p n (j, j) > 0} , and let d be the greatest common divisor of I. We call d the period of state j . A chain with period 1 is said to be aperiodic. All states in the same recurrent class have the same period.

Proposition 4. Suppose the Markov chain M is irreducible, recurrent and all states have period d. Fix x in S (the set of states), and for each y in S, we let K y = {n ≥ 1 ; p n (x, y) > 0}. Then the following statements are true:

(i) There is an

r y ∊ {0, 1, … … , d -1} so that if n ∊ K y , then n = r y mod d . (ii)
Set S r = {y ; r y = r} for 0 ≤ r < d . If y ∊ S i and z ∊ S j and p n (y, z) > 0 , then we have n = (j -i) mod d. (iii) S 0 , S 1 , … … … . , S d-1 are irreducible classes for M d (the dstep chain constructed from M), and all states have period 1 (this is called a cyclic decomposition of the state space).

Proof. For the proof, see [Durrett, 2010], chapter 6. Proof. For the proof, see [Durrett, 2010], chapter 6.

Examples. We will look at the secondary random walks with reflecting barriers for different values of M.

We note that the case M = 1 corresponds to the original version of Schöning's algorithm. In this case the transition probability matrix is A = ( 0 1 1 0 ) . We see that

A 2 = I (the identity matrix) . We have two states, state 0 (when the truth valuation of the variable is 0), and state 1 (when the truth valuation is 1). We have the transition probabilities p(0, 1) = p(1, 0) = 1 . The stable distribution of this chain is π(0

) = π(1) = 1 2
. The chain is periodic with period d = 2. The cyclic decomposition of the state space is S 0 = {0}, S 1 = { 1 } . In this case, we have p 2m (0, 0) = p 2m+1 (0, 1) = 1 . If we start in state 0, an example of a path taken by this chain is 1, 0, 1, 0, 1, 0, … … … …. We see that at any odd time, the chain is in state 1 , and at every even time the chain is in state 0. If we choose a state at random from a given path, we recover the stationary distribution π(0) = π(1) = 1 2 .

We will now consider the case 𝑀 = 2 in greater detail. In this case the transition

probability matrix is A = ( 0 1 0 1 2 0 1 2 0 1 0 ) . We see that A 2 = ( 1 2 0 1 2 0 1 0 1 2 0 1 2
) , and we also see that A 3 = A . We have three states, state 0 (when the truth valuation of the variable is 0), state ), and state 1 (when the truth valuation is 1). We have the transition probabilities p (0, Proof. The proof is immediate from proposition 4 and theorem 1. Definition 5. If the current truth valuation of a variable is 0, but the satisfying truth assignment for this variable is 1, or if the current truth valuation of a variable is 1, but the satisfying truth assignment for this variable is 0, then we say that this will be a positive reflection. In this case, in the primary Markov chain, the Hamming distance to a solution will decrease with probability 1.

If the current truth valuation of a variable is 0, and the satisfying truth assignment for this variable is also 0, or if the current truth valuation of a variable is 1, and the satisfying truth assignment for this variable is also 1, then we say that this will be a negative reflection. In this case, in the primary Markov chain, the Hamming distance to a solution will increase with probability 1.

The states i M , with 1 ≤ i ≤ M -1 will be called intermediate states.

In the algorithm, choosing a variable to change its truth valuation is equivalent to running one of the secondary random walks (the one associated to the variable chosen) for one step, and that is equivalent to one step performed by the primary chain.

Conjecture. At least for large values of M (comparable to n), the algorithm above will find a solution to a 3SAT problem (if it exists) in polynomial time, with high probability.

Arguments in favor of the conjecture. We have to study the ergodic properties of the primary Markov chain described above. For this purpose, we use proposition 5, relations (1) -( 6). We have to consider the two step Markov chain, on one of the cyclic classes S 0 , or S 1 . As an example, for the case 𝑀 = 2 , we have S 0 = {0, 1} , S 1 = { 1 2 } . For the two step chain, we have the probabilities :

p ( 1 2 → 0 → 1 2 ) = p ( 1 2 → 1 → 1 2 ) = 1 2
. We can couple our chain with a symmetric random walk. For each variable, starting in the state 1 2 , the chain visits the correct truth assignment, or the incorrect one with the same probability 1 2 . We know from proposition 2 that for a symmetric random walk, the expected traveled distance after N 2 steps is of order of magnitude N . In the context of our two step chain, this means that after N 2 steps, there might be a sufficiently large excess of variables that visit the correct truth assignment. Of course, this is just a heuristic argument, but the study of the ergodic properties of the primary Markov chain could lead to the conclusion that its behavior resembles the properties of a symmetric random walk, and in this case we know that a quadratic number of steps is sufficient , in order to find a solution with high probability.

Observation 1. There is an interesting geometrical interpretation. The n random walks with reflecting barriers (one associated to each variable) generate a random walk inside the truth valuation hypercube. The truth valuation hypercube has a side length of 1 (but we keep in mind that M is the minimum number of steps for a variable to change its truth assignment from 0 to 1 or from 1 to 0), and its main diagonal has the length √n . We could assume that the random walk starts at (0, 0, 0, … … . . , 0) , and it reaches the vertex of the hypercube that represents the truth assignment solution . As a result of the construction, this n -dimensional random walk never exits the interior of the hypercube, even if at times it can take place on its boundary. Also, this is not a perfectly symmetric random walk, because at each step, it follows the direction of the variables involved in minimal clauses (clauses with a minimal truth valuation). This will give our random walk a general "drift" direction towards the solution vertex of the truth valuation hypercube, and we also know that the distance that has to be travelled is less than √n. Since the distance travelled scales up as the square root of the number of steps performed by the algorithm, this means that a quadratic number of steps (up to a factor that depends on M ) are far more than sufficient, in order for the algorithm to hit a solution. I emphasize that this is only a heuristic proof, and more work needs to be done in this direction.

Observation 2. We also note that this is only one version of this type of algorithm. Other versions or improvements are possible. The original Schöning algorithm ( M = 1 ), relies only on reflections. In the version of the algorithm presented here, we try to minimize the effect of reflections, and rely instead on intermediate steps to drive the primary Markov chain towards a solution.

Discussion and conclusions

For general implications, related to efficiently solving NPcomplete problems, see [Fortnow, 2013]. An interesting application is related to the problem of automated theorem proving using an efficient algorithm for NPcomplete problems (see [A1]). The impact of this type of algorithm in mathematics is obvious. All unsolved problems at the present time (if they allow proofs that are not too long, within the axiomatic system that we work with, for example, with the information content equivalent to less than 10000 journal pages) will be quickly solved. If NP complete problems can be solved efficiently, better AI system can be designed. In industry, transportation problems, logistics, and manufacturing planning will be significantly improved. In medicine, these algorithms will lead to the design of better drugs and treatments (protein folding and its relation to NP complete problems). Also the crypto community must redesign their encoding and decoding procedures (and public key cryptography must be replaced). Basically, any field of activity that requires intellectual effort can benefit from these types of algoritms. The main purpose of this paper is to open new ways to approach this interesting problem.

Aknowledgements.

I emphasize that Professor Fortnow's book ( [Fortnow, 2013]) was a great source of inspiration and motivation that led me to seriously consider this problem. Also, I received some feedback related to previous versions of my work from Professor Uwe Schöning , Professor Lance Fortnow, and Professor C. Papadimitriou. I also discussed some of the arguments presented above with Eric Demer , graduate student at University of California, Santa Barbara, who also corrected a previous error that I had in my work. The clustered Sparrow algorithm from [ A4] was developed in collaboration with Dr. Anastasia-Maria Leventi-Peetz (BSI, Germany). I am grateful to all. In the same time, I take full responsibility for any omissions present in my work.

Appendices

A1. Godel's letter to John von Neumann. In his letter, Godel writes: "One can obviously easily construct a Turing machine, which for every formula F in first order predicate logic and every natural number n, allows one to decide if there is a proof of F of length n (length = number of symbols). Let 𝜓(𝐹, 𝑛) be the number of steps the machine requires for this and let 𝜑(𝑛) = 𝑚𝑎𝑥 𝐹 𝜓(𝐹, 𝑛). The question is how fast 𝜑(𝑛) grows for any optimal machine" (see [Godel, 1956]. Now we consider this. In [START_REF] Hopcroft | [END_REF], we have theorem 13.1, at page 325 (a version of the Cook -Levin theorem), where it is proved that for each Turing machine (deterministic or nondeterministic) M that is time by a polynomial 𝑝(𝑛), a log-space algorithm exists, that takes as input a string x and produces a Boolean expression 𝐸 𝑥 that is satisfiable if and only if M accepts x.

This means that the process of seeking a proof (of reasonable length) of a mathematical statement can be completely automatized. With the algorithm presented in this paper, Godel's vision can be made reality.

A2.

We are given a 3SAT expression E. A positive literal represents the variable itself, a negative literal represents the negation of a variable. For each occurrence of a variable x (in a positive or negative literal) within the expression we introduce a new variable x i , and form the modified expression E*. We also have to include a conjunction of clauses that state that the variables x i have the same truth assignment. The conjunction (x i ˅ ˥ x j ) ˄ (˥ x i ˅ x j ) has the truth value 1 if and only if the variables x i and x j have the same truth value. In general, the variables x 1 , x 2 , x 3 , … … . . , x m have the same truth value if and only if the conjunction (x 1 ˅ ˥ x 2 ) ˄ ( x 2 ˅ ˥ x 3 ) ˄ (x 3 ˅ ˥ x 4 ) ˄ … … … . ˄ (x m-1 ˅ ˥ x m ) ˄ (x m ˅ ˥ x 1 ) has the truth value 1. In the modified expression E*, each variable appears in at most three clauses, either in two positive literals and one negative, or in two negative literals and one positive.

In other words, each variable x appears only in a three variable clause ( x ˅ α ˅ β ) (or it could be ( ˥x ˅ α ˅ β ) ) , and in a couple of two variable clauses ( x ˅ ˥ γ) and ( ˥ x ˅ θ). Each variable appears only in the conjunction of these clauses ( x ˅ α ˅ β ) ˄ (x ˅ ˥ γ) ˄ (˥ x ˅ θ) . We now consider the valuation of these clauses , in terms of the valuations of each variable that appears in these clauses (we keep in mind that the truth valuation of a variable is a real number in the interval [0, 1], in this appendix). We calculate the valuation of each of the three clauses where the variable x appears.

v( x ˅ α ˅ β) = v (x) + v(α) + v(β) -v(x) • v(α) -v(x) • v(β) -v(α) • v(β) + v(x) • v(α) • v(β) . v(x ˅ ˥ γ) = v(x) + v(˥ γ) -v(x) • v(˥ γ) v(˥ x ˅ θ) = v(˥ x) + v(θ) -v(˥ x) • v(θ) We also keep in mind that v(˥ x) = 1 -v(x) and v(˥ γ) = 1 -v(γ). The function f(x) = v( x ˅ α ˅ β) • v(x ˅ ˥ γ) • v(˥ x ˅ θ
) becomes a cubic polynomial in the truth valuation of the variable x, if we look at the valuations of α, β, γ, and θ as fixed parameters. We can then calculate the valuation of the variable x, such that the expression f(x) takes a maximum value in the interval [0, 1], and change the valuation of x to that value. We remember that we want to maximize the truth valuations of all the clauses in the expression E*, until they all become 1. We can repeat this process for all the variables involved in the expression E*, over and over again, until all clauses (and thus the whole expression E*) has maximum truth valuation 1. The problem is that we can get stuck in a local maximum, even if the truth valuation of every clause is not the maximum 1. In that case, we can reinitialize the truth valuations of the variables at random and start all over again, until we enter the basin of attraction of the global maximum, that we are seeking. At each step, the truth valuation of the whole expression E* can only increase or stay the same.

A3.

If in a solution truth assignment, a variable is given the truth assignment 0, then the truth assignment 1 is a positive reflection point, and the truth assignment 0 is a negative reflection point, for the random walk with reflecting barriers associated to this variable. If in a solution truth assignment, a variable is given the truth assignment 1, then the truth assignment 0 is a positive reflection point, and the truth assignment 1 is a negative reflection point, for the random walk with reflecting barriers associated to this variable.

We consider the random walks with reflecting barriers associated to each variable. We consider the case M = 4. In this case, we have the states 0,

                                                  0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 0 2 1 2 0 2 1 0 2 1 0 2 1 2 0 2 1 0 2 1 2 0 2 1 2 0 2 1 2 0 1 1 1 1 1 1 1 1 1 1 1 1 1 2 k k k k k k k k k k k k k k k k k A                                                  1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 2 0 2 1 0 2 1 2 0 2 1 2 0 2 1 2 0 4 1 0 2 1 0 4 1 0 2 1 2 0 2 1 2 0 2 1 2 0 2 1 0 2 1 2 k k k k k k k k k k k k k k k k k A
These probability transitions govern all the odd and even steps of the random walk with reflecting barriers associated to the variables. We see that if a variable starts in a positive reflection point, then at even steps, it is slightly more likely that the associated random walk with reflecting barriers will hit the positive reflection point, rather than the negative reflection point. It is also more likely that at odd steps, the random walk will hit points closer to the positive reflection point, rather than closer to the negative reflection point. Without restricting generality, if we assume that most of the variables start in positive reflection points (for example, we can initialize all the variables with 0 or we can initialize all the variables with the truth value 1), it is then likely that overall, the positive reflection points will be hit more often than the negative reflection points, but this also depends on the structure of the 3SAT expression, and the complex dynamics of the primary Markov chain. It is worth noticing that if all the variables are initialized with the truth valuation 1 2 , then at even steps, it is as likely that the random walk with reflecting barriers (associated to any variable) will hit a positive reflection point, as it is likely that it will hit a negative reflection point (in both cases the probability is 1 4 ).

A4. The clustered Sparrow algorithm

We start from a 3SAT expression E, and we perform the conversion to the clustered SAT expression E*, where each variable appears in at most 3 clauses. For a clear presentation of the procedure, see proposition 9.3, page 183, in [Papadimitriou, 1994].

We note that the assignments marked with * satisfy the cluster (all clauses in the cluster are satisfied). The flips 0 → 1 and 1 → 0 refer to the primary variable x, when all the other literals do not change (under the current truth assignment). The last two columns represent the make minus break quantity Δ = make -break , where "make" represents the number of clauses that change from unsatisfied to satisfied, as a result of the flip, and "break" represents the number of clauses that change from satisfied to unsatisfied, as a result of the flip. The algorithm only touches unsatisfied clauses (or clusters), so the satisfying assignments do not have a Δ value in the corresponding column (a possible exception is between assignments 15* and 16*, since the cluster is left satisfied and Δ = 0 ).

We will call a positive flip, a flip that has the value of delta strictly positive Δ > 0. We will call a negative flip, a flip that has the value of delta strictly negative Δ < 0 . We will call a null flip, a flip that has the value of delta 0, Δ = 0 .

We note that all flips are either positive or null, with one exception, the second assignment in the table (the delta value marked in red). Also, we note that if at a given moment, a negative flip occurs, we see that the cluster is still unsatisfied, allowing for a positive flip later. Thus, at later stages, the flip will be reversed with high probability, if the change of the secondary variables in the cluster do not make the cluster satisfied before that.

Lemma. If the clustered expression E* contains clusters with any of the primary clauses unsatisfied, then there are at least some null flips available (if not positive flips).

Proof. If a primary clause is unsatisfied, then the literal (positive or negative) associated to the primary variable of the cluster has truth value 0. When we flip the primary variable, and make this unsatisfied primary clause satisfied, the other primary clause cannot become unsatisfied as a result of this flip. Only the secondary clause in this cluster could become unsatisfied as a result of this flip (but not necessarily). As a consequence, the makebreak value of this flip is greater or equal to zero Δ ≥ 0 .

We have to construct a probability function that will determine the type of flip to be chosen, at each step. Let's assume that at a given moment, we have available N 1 negative flips, N 2 null flips, and N 3 positive flips (where N 1 + N 2 + N 3 represents the number of variables that have unsatisfied clusters). We want to assign a higher probability to the positive and null flips, and a lower probability to the negative flips. We choose a small positive number α. If we assign the probability , to choose a particular negative flip, then the probability to choose any negative flip is α. We also assign the probability . If there are no positive flips available, N 3 = 0 , then we simply take the probability to choose any null flip 1 -α (distributed equally among the null flips available) . If there are no null flips available, N 2 = 0 , then we simply take the probability to choose any

.

  If the current truth valuation of the variable is 0, then with probability 1 increase its truth valuation with 1 𝑀 . If the current truth valuation of the variable is 1, then with probability 1 decrease its truth valuation with

M.

  that the current truth valuation of the corresponding variable is i The probability transition matrix A for each secondary random walk is defined by the transition probabilities: │i -j│ > 1 , for any values of i, j ϵ {0, 1, 2, 3, … … . . , M} .

..

  The stable distribution of this chain is π(0The chain is periodic with period d = 2. The cyclic decomposition of the state space is S 0 = {0, 1}, S 1 . If we start in state 0, an example of a path taken by this … … … … We see that at any odd time, the chain is in state 1 2 , and at every even time the chain is in state 0 or 1 with equal probability. If we choose a state at random from a given path, we recover the stationary distribution π(0) = π(1M = 4 is considered in [A3].Proposition 5. In the general case, the period is d = 2. If M is an even number, then the cyclic decomposition of the state space is S an odd number, then the cyclic decomposition of the state space is

A

  It can be easily proved that we have the following relations, for 𝑘 ≥ 1.

We note that if the 3SAT expression E has n variables and c clauses, then the clustered expression E* will contain 3c variables, and 4c clauses, out of which c will be three variable clauses and 3c will be two variable clauses.

A cluster associated to a variable x, can be of two types. Type 1 cluster: (x ˅ y ˅ z)˄(x ˅ ˥u)˄(˥x ˅ w)

Here y and z are two literals (they can be positive or negative), and we write ˥𝑥 for the negative literal that represents the negation of x.

Type 2 cluster:

In the clusters above, we will call x the primary variable associated to the cluster, and the other variables are called secondary (but they are primary variables as seen in their own clusters). In a cluster, the three variable clause, and the two variable clause where the primary variable is under the same literal (both positive or bot negative) are called primary clauses. The two variable clause in the cluster in which the primary variable is under an opposite literal (compared to the three variable clause), is called the secondary clause. So a cluster has two primary clauses and a secondary clause.

The most general form of a cluster can be written in the form:

In this case, b, and c can be positive or negative literals, and a is a disjunction of literals, 𝑎 = y ˅ z , b = ˥u , c = w , and x can be a positive or negative literal We construct the truth table of the cluster.

positive flip 1 -α (distributed equally among the positive flips available).

If there are no negative flips available , N 1 = 0 , then we choose a null or positive flip with equal probability 1 2 (distributed equally among the flips available). It is, in principle, possible that at a given moment we only have flips of a certain type available. In that case, the algorithm will choose that type of flip with probability 1. So let's see what is happening. At each step, the algorithm will choose null or positive flips, with high probability (we assume α close to 0), so the number of satisfied clauses can only increase, with high probability (and any negative flips that may occur will be reversed later with high probability). We have to prove that the positive flips occur sufficiently often, so the algorithm is polynomial. This point will be discussed in a future paper.

The clustered Sparrow algorithm

We start with a 3SAT expression E. We construct the clustered expression E*, where each variable appears in at most 3 clauses, as described above.

Repeat 2𝑚 2 times (m is the number of clauses of E*)

If the current truth assignment is a solution, return the solution and stop Choose at random a negative, null or positive flip, according to the probability function described above.

Perform the flip, and update.

Return no solution was found.

So at every step, the algorithm looks only at all the variables that have unsatisfied clusters, and chooses a negative, null or positive flip, according to the probability function described above.

The makebreak idea is discussed in [START_REF] Schöning | [END_REF]. The idea to work with clustered expressions E*, as well as using a probability function that takes into account all the variables at every step (not just those involved in an unsatisfied clause) is original. This algorithm is the result of my collaboration with Dr. Anastasia-Maria Leventi-Peetz (BSI, Germany), but implementation and testing have not been performed yet.