Regina Bernhaupt
email: regina.bernhaupt@irit.fr

Michael Pirker
email: michael.pirker@ruwido.com

Evaluating User Experience for Interactive Television: Towards the Development of a Domain-Specific User Experience Questionnaire

Keywords: interactive TV, iTV, user experience, UX, questionnaire, Internet Protocol Television, IPTV, emotion, stimulation, identification

This paper presents a questionnaire-based approach to evaluate the user experience (UX) while interacting with interactive Television (iTV) systems. Current contributions in the field of UX propose generic methods applicable to various application domains, whereas our contribution is dedicated to the specific domain of interactive TV systems. Based on a classification of UX dimensions from a literature review, the first version of the questionnaire is focusing on the dimension's aesthetics, emotion, stimulation and identification. A validation study with 106 participants was performed to assess the relations between the evaluated UX dimensions, as well as their fit to the underlying theoretical assumptions. Results showed that the UX dimensions aesthetics, emotion and stimulation are important for the domain of iTV, while identification was not confirmed. The study revealed significant correlations between the type of IPTV system used and the emotional and stimulation dimension. Additionally, a significant effect of the TV reception mode and the type of IPTV box owned on the emotion towards the system was observed. Beyond the contribution of the questionnaire that is directly applicable for any iTV system, the findings described in the paper demonstrate the need for user experience evaluation methods targeted at specific domains: the validation of the questionnaire shows that identification is not a central dimension of user experience when interacting with interactive TV.

Introduction

User experience (UX) is described as dynamic, time dependent [START_REF] Karapanos | Measuring the dynamics of remembered experience over time[END_REF] and beyond the instrumental [START_REF] Hassenzahl | User Experience -a research agenda[END_REF]. The overall goal of UX is to understand the role of affect as an antecedent, a consequence and a mediator of technology [START_REF] Hassenzahl | User Experience -a research agenda[END_REF]. The concept of UX focuses rather on positive emotions and emotional outcomes such as joy, fun and pride [START_REF] Hassenzahl | User Experience -a research agenda[END_REF]. The development of a general definition of UX is still focus of scientific discourse [START_REF] Law | Understanding, scoping and defining user experience: a survey approach[END_REF], and despite the lack of a clear definition, the concept of UX has become an important design aspect of interactive systems.

There are a growing number of methods available to evaluate user experience in all stages of the development process. Surveys on these contributions are already available such as in [START_REF] Bargas-Avila | Old wine in new bottles or novel challenges[END_REF] where Bargas-Avila and Hornbaek present an overview on UX and UX evaluation methods or in [START_REF] Vermeeren | User experience evaluation methods[END_REF] where Vermeeren and colleagues have been collecting and classifying user experience methods. Beyond that work on generic methods, contributions have been proposed for specific application domains, e.g. for games and entertainment [START_REF] Bernhaupt | User Experience Evaluation in Games and Entertainment[END_REF] or for the evaluation of mobile devices like mobile phones [START_REF] Roto | User Experience Evaluation in Nokia. Now Let's Do It[END_REF].

What is still not answered is whether generic user experience evaluation methods provide meaningful and sufficiently precise insights when applied to specific application domains. In the field of usability the answer to that question was already negative [START_REF] Forbrig | 5th Workshop on Software and Usability Eng.Cross-Pollination: Patterns, Usability and UX[END_REF]. Due to the idiosyncratic nature of user experience that is situational, time dependent, and influenced by the technological context especially the type of system and functionality, we advocate that there is a need to adapt, customize and validate specific UX evaluation methods for the respective application areas.

The domain of interactive TV (iTV) is described as being specific due to a variety of contextual factors, including the spatial, temporal, social, personal and technological context [START_REF] Obrist | Interactive television for the home: An ethnographic study on users' requirements and experiences[END_REF]. Beyond the difficulties brought by these factors, the evaluation of user experience for iTV is complex, as the system to be evaluated consists of multiple components: the TV screen, (a set of) remote controls, (possibly) a set top box (i.e. the hardware device connecting the TV to the IP network) and potentially other devices in the living room (e.g. surround sound system). One of the characteristics of the iTV domain is also the multiple goals of the users aiming at being entertained and informed.

We have been applying various UX methods in the area of iTV [START_REF] Bernhaupt | Security, Privacy, and Personalization[END_REF][START_REF] Pirker | Measuring User Experience in the Living Room: Results from an Ethnographically Oriented Field Study Indicating Major Evaluation Factors[END_REF][START_REF] Pirker | Investigating usability and user experience as possible entry barriers for touch interaction in the living room[END_REF] which otherwise has received only limited attention. These studies have been carried out in close cooperation with one of the industry leaders in hardware and software systems for iTV. However, even though the evaluation results were iteratively fed into the development process of the systems, customer feedback reported by our client were exhibiting users' frustration and dissatisfaction, demonstrating a user experience far below expectations. Based on these results we have been working on the definition of a user experience evaluation method specifically adapted for iTV systems. This paper presents the development and the validation of the first version of a user experience evaluation questionnaire called iTV-UX. The goal of the questionnaire is to enable the evaluation of all types of iTV systems in terms of user experience. The iTV-UX is based on four UX dimensions: visual and aesthetic experience, emotion and affect, stimulation, and identification.

State of the Art

User Experience (UX) is a research topic within the HCI community that has gained a lot of attention within the past years [START_REF] Bargas-Avila | Old wine in new bottles or novel challenges[END_REF]. The term UX still lacks a clear and agreed-on definition. The reasons therefore are rooted in the nature of UX, which is associated within a lot of different concepts and meanings within the community, or as Law et al.

[34, p. 1] put it "User Experience (UX) is a catchy as well as tricky research topic, given its broad applications in a diversity of interactive systems and its deep root in various conceptual frameworks, for instance, psychological theories of emotion." Despite several attempts to define and better explain the user's experience when interacting with an interactive system in the past, the HCI community still has no unified definition of what really makes up UX, how to measure or evaluate UX, and how to rate it. An ISO Standard defining UX exists, but leaves a lot of room for interpretation, and is said to be too imprecise [START_REF]Ergonomics of Human-System Interaction -Part 210: Humancentred Design for Interactive Systems[END_REF]: "A person's perceptions and responses that result from the use and/or anticipated use of a product, system or service."

Additionally, the term UX is also influenced by several concepts from other areas, like fun, playability, or Csikszentmihalyi's concept of flow [START_REF] Csikszentmihalyi | Flow: The Psych. of Opt. Experience[END_REF][START_REF] Järvinen | Communication and Community in Digital Entertainment Services[END_REF]. Within this multitude of concepts, as pointed out by Law et al. [START_REF] Law | Understanding, scoping and defining user experience: a survey approach[END_REF], the inclusion and exclusion of particular variables seem arbitrary, depending on the author's background and interest. Further reasons stated by Law et al. include the differences in the unit of analysis, ranging from a single aspect of a single user's interaction with a specific application to multi-users' interactions with a company and its services from multiple disciplines; and finally the fragmented landscape of UX research with diverse theoretical models with different foci [START_REF] Law | Understanding, scoping and defining user experience: a survey approach[END_REF]. In more recent work, Law [START_REF] Jordan | Designing Pleasurable Products[END_REF] argues that the current UX researchers and practitioners may also roughly be divided into two camps, a "designbased UX research camp" which focuses more on qualitative approaches and a "model-based UX research camp" with a focus on quantitative approaches.

Similar reasons have already been pointed out by Hassenzahl [START_REF] Hassenzahl | The interplay of beauty, goodness, and usability in interactive products[END_REF]. He stated that the lack of agreement in definition of key elements makes building up empirical knowledge about what constitutes UX difficult, and that future research must aim at unifying approaches to UX, with its major objectives being the selection of key constructs and a better understanding of their interplay. Hassenzahl and Tractinsky [START_REF] Hassenzahl | User Experience -a research agenda[END_REF] categorize current UX approaches and concepts in three groups:

1. Beyond the instrumental: One of the criticisms of usability evaluation was that a focus only on tasks is too narrow. Beauty as a perceptual experience, on the other hand, goes beyond the instrumental, functional concept of usability. It satisfies a human need, and was also described as an important quality of technology usage [START_REF] Alben | Quality of experience: defining the criteria for eff. interaction design[END_REF]. Other needs that are described as being important and should be addressed by technology include needs such as surprise, diversion or intimacy [START_REF] Gaver | Alternatives: exploring information appliances through conceptual design proposals[END_REF]. Further concepts falling into this category can be summarized as hedonic aspects of technology usage, like stimulation and identification [START_REF] Hassenzahl | The interplay of beauty, goodness, and usability in interactive products[END_REF]. All these UX approaches link product attributes with needs and values, the common goal is to enrich current models of product quality with non-instrumental aspects.

2. Emotion and affect: There are two basic ways in dealing with emotions in UX concepts. One way can be summarized as research that stresses the importance of emotions as consequences of product use, focusing on emotion as a result of the interaction or usage of a product. The other way concentrates on emotions that are preceding product use and contributing to the formation of evaluative judgments [START_REF] Hassenzahl | User Experience -a research agenda[END_REF]. Current UX research rather, focuses on positive emotions and emotional outcomes such as joy, fun and pride, and also deals with emotion as a design goal [START_REF] Desmet | Designing products with added emotional value[END_REF].

3. The experiental: The third perspective looks at temporal and situational influences, asking for the dynamics of an interaction, how unique, complex, temporary or situated an experience is. In this view, an experience is a unique combination of various elements, such as the product and internal user states (e.g. mood, expectations, active goals), which extend over time with a definitive beginning and end. The experiential assumes all these elements to be interrelatedto interact and modify each other. The outcome of this process is the actual experience [START_REF] Forlizzi | Understanding experience in interactive systems[END_REF].

Generally, UX is described as focusing on the interaction between a person and a product, and is likely to change over time and with an embedding context [START_REF] Hassenzahl | User Experience -a research agenda[END_REF][START_REF] Law | Understanding, scoping and defining user experience: a survey approach[END_REF].

User Experience Evaluation

A broad variety of UX evaluation methods is available today, which are described and discussed in detail by Vermeeren et al. [START_REF] Vermeeren | User experience evaluation methods[END_REF]57] regarding their methodological approach (e.g. field studies, lab studies), the development phase they can be applied (from concepts to products on the market), the studied period of experience, and the evaluator. Law and van Schaik [START_REF] Law | Modelling user experience -An agenda for research and practice[END_REF] summarize that UX measurement should essentially be self-reported, trajectory-based and adaptive, in accordance with the common understanding of UX as subjective, dynamic and context-dependent [START_REF] Hassenzahl | User Experience -a research agenda[END_REF]. Thus, traditional techniques such as questionnaire, interview, and think-aloud remain important for capturing self-reported data [START_REF] Law | Modelling user experience -An agenda for research and practice[END_REF].

Following the classification of UX approaches and concepts by Hassenzahl and Tractinsky [START_REF] Hassenzahl | User Experience -a research agenda[END_REF], approaches focusing on the evaluation of emotion and affect include questionnaires like EmoCards [START_REF] Desmet | Designing products with added emotional value[END_REF] that ask the user to indicate the emotional state based on graphical representations. Other ways to measure the emotional response include physiological measurements (e.g. heart rate, skin conductance) or the evaluation of valence and arousal, which are currently also applied in the games area [START_REF] Nacke | More than a feeling: Measurement of sonic UX and psychophysiology in a first-person shooter game[END_REF]. To measure the user experience beyond the instrumental, task-based approach, Hassenzahl [START_REF] Hassenzahl | The interplay of beauty, goodness, and usability in interactive products[END_REF] introduced the AttrakDiff questionnaire. In order to evaluate situational or temporal experiences, some approaches in mobile UX exist, using conceptualanalytical research and data gathering techniques [START_REF] Roto | User Experience Evaluation in Nokia. Now Let's Do It[END_REF]. For prototypes, usability evaluation methods can be enhanced by including experimental aspects to the evaluations, e.g. in long-term field trials, where diaries, experience sampling, questionnaires, and focus groups can be used to collect additional data [START_REF] Roto | User Experience Evaluation in Nokia. Now Let's Do It[END_REF].

User Experience Evaluation of interactive TV

In the TV and entertainment sector, UX has been evaluated using a broad variety of methods. Dimensions that are addressed include emotions [START_REF] Mandryk | Using psychophysiological techniques to measure UX with entertainment technologies[END_REF][START_REF] Oliveira | Towards emotional interaction: using movies to automatically learn users' emotional states[END_REF], social factors [START_REF] Geerts | Supporting the social uses of television: sociability heuristics for social tv[END_REF], values and requirements [START_REF] Bernhaupt | Security, Privacy, and Personalization[END_REF][START_REF] Obrist | Interactive television for the home: An ethnographic study on users' requirements and experiences[END_REF][START_REF] Pirker | Measuring User Experience in the Living Room: Results from an Ethnographically Oriented Field Study Indicating Major Evaluation Factors[END_REF], the perception of the quality of the interaction or representation [START_REF] Turunen | User expectations and user experience with different modalities in a mobile phone controlled home entertainment system[END_REF][START_REF] Rajae-Joordens | Measuring experiences in gaming and TV applications[END_REF], or service quality and content [START_REF] Hartmann | Framing the user experience: information biases on website quality judgement[END_REF][START_REF] Lavie | Assessing dimensions of perceived visual aesthetics of web sites[END_REF]. These user experience evaluations have been applying standard UX methods, like the AttrakDiff questionnaire [START_REF] Pirker | Investigating usability and user experience as possible entry barriers for touch interaction in the living room[END_REF]. Other measurements include the SUXES evaluation method, as used by Turunen et al. [START_REF] Turunen | User expectations and user experience with different modalities in a mobile phone controlled home entertainment system[END_REF] to evaluate UX with different modalities in a mobile phone controlled home entertainment system. Experiences in gaming and TV applications were evaluated using psycho-physiological measurements [START_REF] Mandryk | Using psychophysiological techniques to measure UX with entertainment technologies[END_REF]. These measurements were also used to evaluate the users' experiences with multi-view 3D displays [START_REF] Rajae-Joordens | Measuring experiences in gaming and TV applications[END_REF] or to classify emotional reactions to video content [START_REF] Oliveira | Towards emotional interaction: using movies to automatically learn users' emotional states[END_REF]. Obrist et al. [START_REF] Obrist | Interactive television for the home: An ethnographic study on users' requirements and experiences[END_REF] investigated users' requirement and experiences within an ethnographic study and identified patterns how iTV services can support people. Tsekleves et al. [START_REF] Tsekleves | Bringing the television experience to other media in the home: an ethnographic study[END_REF] investigated the TV experience and media use habits using ethnographic observations. Roibas et al. [START_REF] Roibás | Unfolding the user experience in new scenarios of pervasive interactive TV[END_REF] used ethno-methodologies like cultural probing and collaborative design to uncover the UX in future scenarios of mobile and pervasive iTV.

None of the methods applied for evaluating the overall user experience of interactive TV systems has been adapted to fit the interactive TV context. Interactive TV is special as the interaction with the system typically takes place at home, involving a certain type of setting (physical context) or influenced by people who might join the TV experience (social context) (see [START_REF] Obrist | Interactive television for the home: An ethnographic study on users' requirements and experiences[END_REF] for a discussion of the different contextual factors). While for the area of social factors and social TV Geerts and De Groof [START_REF] Geerts | Supporting the social uses of television: sociability heuristics for social tv[END_REF] have been proposing sociability heuristics, there is no adapted and validated UX evaluation method focusing on a set of UX dimensions specific for interactive TV in general.

Research Goals and Approach

Goal of our research is to develop a user experience evaluation method that allows us to evaluate the iTV specific user experience. Our research goal is motivated by the demand from the industry to have only one questionnaire combining the most important UX dimensions in this specific domain. The problem for the construction of such a method lies in the specificities of the iTV domain: it is necessary to take into account iTV characteristics and the context of usage. The user experience is shaped by interacting (using an interaction technology, i.e. a remote control, or other means of interaction) from a distance to control an interactive TV system and navigate in its menu structure, services and features. The spatial and temporal context of usage also influences the perception of the system (likely at home, at leisure time), as well as possible social factors (shared usage, co-experience). The UX of the iTV system itself is of interest, not the UX related to entertainment content. The goal is to cover an extensive and holistic collection of user experience dimensions for the domain of iTV. The questionnaire development proceeds in three major steps, and the following methodological approach was chosen to identify the user experience dimensions used in the questionnaire and its subsequent development and iteration: 1. Identification of UX dimensions from the literature and development of a set of attributes based on existing questionnaires (presented in this paper), 2. Development and validation of the questionnaire including a set of the most important UX dimensions to verify their applicability in the domain with currently available iTV systems (presented in this paper), and finally 3. Extension of the set of dimensions to address the context specifics by adding additional dimension, and revalidation (future work).

3.1

Overview on UX Dimensions

Based on a literature review, we identified publications related to UX and its dimensions, the evaluation of product experiences and UX evaluation methods from entertainment and games. Table 1 gives an overview of the diversity of UX dimensions that are referred to when describing user experience. [START_REF] Desmet | Framework of product experience[END_REF] x x x VM Alben 1996 [START_REF] Alben | Quality of experience: defining the criteria for eff. interaction design[END_REF] x x [START_REF] Hassenzahl | The interplay of beauty, goodness, and usability in interactive products[END_REF]Hassenzahl , 2008 [17, 19] [17, 19] x x x SRC Karapanos et al 2010 [START_REF] Karapanos | Measuring the dynamics of remembered experience over time[END_REF] x Jordan 2000 [START_REF] Jordan | Designing Pleasurable Products[END_REF] x x x VM, SRC Wright et al 2003 [START_REF] Wright | Making Sense of Experience[END_REF] x x Hassenzahl et al 2010 [START_REF] Hassenzahl | Needs, affect, and interactive products -Facets of user experience[END_REF] x x x VM, SRC, DST Jääskö and Mattelmäki 2003 [START_REF] Jääskö | Observing and probing[END_REF] x x x VM De Angeli et al 2006 [START_REF] Angeli | Interaction, usability and aesthetics: what influences users' preferences?[END_REF] x x DST Steen et al. 2003 [START_REF] Steen | The 'wow' experience -Conceptual model and tools[END_REF] x Gaver and Martin 2001 [START_REF] Gaver | Alternatives: exploring information appliances through conceptual design proposals[END_REF] x [START_REF] Desmet | Designing products with added emotional value[END_REF][START_REF] Mandryk | Using psychophysiological techniques to measure UX with entertainment technologies[END_REF][START_REF] Mahlke | Studying affect and emotions as important parts of the UX[END_REF][START_REF] Minge | Methoden zur Erhebung emotionaler Aspekte bei der Interaktion mit technischen Systemen[END_REF][START_REF] Norman | Emotional design: why we love (or hate) everyday things[END_REF] x Sheldon et al 2001 [START_REF] Sheldon | What Is Satisfying About Satisfying Events? Testing 10 Candidate Psychological Needs[END_REF] x x x VM McCarthy/Wright 2004 [START_REF] Mccarthy | Technology as experience[END_REF] x VM Hartmann et al 2008, [START_REF] Hartmann | Framing the user experience: information biases on website quality judgement[END_REF] x x x SQ Turunen et al 2009 [START_REF] Turunen | User expectations and user experience with different modalities in a mobile phone controlled home entertainment system[END_REF] x VM Sproll et al 2010 [START_REF] Sproll | From product concept to user experience: exploring UX potentials at early product stages[END_REF] x x SRC, DST Battarbee 2003, 2004 [START_REF] Battarbee | Co-Experience the social UX[END_REF] SRC Pirker et al. [START_REF] Pirker | Measuring User Experience in the Living Room: Results from an Ethnographically Oriented Field Study Indicating Major Evaluation Factors[END_REF] x x x VM, SRC Lavie & Tractinsky 2004 [START_REF] Lavie | Assessing dimensions of perceived visual aesthetics of web sites[END_REF] x x x SQ Ijsselsteijn et al 08 [START_REF] Ijsselsteijn | Measuring Player Experiences in Digital Games[END_REF] x x Flow, C

The classification identified aesthetics and beauty, emotion and affect, stimulation, identification, meaning and value, social factors, flow, immersion, involvement and engagement; challenge; service quality and content; and dependability, trust and security. The aesthetics dimension describes how aesthetically pleasing or beautiful something is perceived. The visual/aesthetic experience deals with the pleasure gained from sensory perceptions [START_REF] Hekkert | Design aesthetics: Principles of pleasure in product design[END_REF]. It incorporates beauty [START_REF] Hassenzahl | The interplay of beauty, goodness, and usability in interactive products[END_REF], as well as classic aesthetics (e.g. clear, symmetric) described by Lavie and Tractinsky [START_REF] Lavie | Assessing dimensions of perceived visual aesthetics of web sites[END_REF]. It follows Alben's [START_REF] Alben | Quality of experience: defining the criteria for eff. interaction design[END_REF] statement that objects have to be aesthetically pleasing and sensually satisfying.

Emotion has been identified as a key factor of UX [START_REF] Hassenzahl | User Experience -a research agenda[END_REF]. For Desmet and Hekkert [START_REF] Desmet | Framework of product experience[END_REF], the emotional experience is one of the three main factors contributing to product experience, including feelings and emotions elicited. Also Alben [START_REF] Alben | Quality of experience: defining the criteria for eff. interaction design[END_REF] addressed the factor emotion in the form of the emotional response as an outcome of the interaction. Izard [START_REF] Izard | Die Emotionen des Menschen[END_REF] described ten basic emotions, of which the three clearly positive emotions were chosen to be included in the questionnaire (interest, joy and surprise), as UX is described as focusing on positive experiences [START_REF] Hassenzahl | User Experience -a research agenda[END_REF]. Additionally, the feeling of competence as a need fulfillment is covered within this dimension [START_REF] Sheldon | What Is Satisfying About Satisfying Events? Testing 10 Candidate Psychological Needs[END_REF][START_REF] Hassenzahl | Needs, affect, and interactive products -Facets of user experience[END_REF][START_REF] Nacke | More than a feeling: Measurement of sonic UX and psychophysiology in a first-person shooter game[END_REF].

The stimulation dimension describes to what extent a product can support the human need for innovative and interesting functions, interactions and contents. Hassenzahl [START_REF] Hassenzahl | Aesthetics in interactive products: Correlates and consequences of beauty[END_REF] describes stimulation as a hedonic attribute of a product, which can lead to new impressions, opportunities and insights. Hedonic experiences were subsumed by Karapanos et al [START_REF] Karapanos | Measuring the dynamics of remembered experience over time[END_REF] under the term innovativeness to describe hedonic experiences and the ability of a product to excite the user through its novelty. In the area of games, Jääskö and Mattelmäki [START_REF] Jääskö | Observing and probing[END_REF] defined product novelty as one of the qualities of user experience.

The identification dimension indicates to what extent a certain product allows the user to identify with it. For Hassenzahl [START_REF] Hassenzahl | The interplay of beauty, goodness, and usability in interactive products[END_REF], the identification dimension addresses the human need to express one's self through objects. Thus, using or owning a specific product is a way to reach a desired self-presentation. Identification can be seen as self-expression through an object to communicate identity.

Developing the Questionnaire

For the questionnaire we chose the most prominent UX dimensions to verify their applicability in the domain with currently available iTV systems: aesthetics, emotion, stimulation and identification. The decision to not include dimensions like social connectedness, interaction and value in this first version of the questionnaire is based on the current market situation for TV and I(P)TV products. At the moment, most IPTV systems do not support social communication or services; additionally, the interaction takes place using a standard infra-red remote control. The dimension of Value might not be addressed properly in a broad evaluation of different TV systems as it is heavily influenced by the assembly of IPTV and entertainment-oriented devices and might provide better results when used in a specific setting in the future.

The questionnaire is based on a set of word-pairs for each of the dimensions identified. Each word pair represents an item of the questionnaire and is based on a sevenpoint semantic differential rating scale. The bi-polar adjectives used in the semantic differential scale where placed at the extremes of the scale; inversion of items was used to avoid fill-in schemes. This kind of scale was chosen as semantic differentials are described as a good choice to evaluate positive affective responses [START_REF] Heise | The Semantic Differential and Attitude Research. Attitude Measurement[END_REF], which is the case for the evaluated UX dimensions.

The dimension visual/aesthetic experience is evaluated using seven bi-polar adjectives addressing beauty, the composition (classic aesthetics) and the design of the IPTV system.

It includes items like beautiful vs. ugly, or appealing vs. unappealing. Items were based on the work of Hassenzahl [START_REF] Hassenzahl | The interplay of beauty, goodness, and usability in interactive products[END_REF], Lavie [START_REF] Lavie | Assessing dimensions of perceived visual aesthetics of web sites[END_REF] and Desmet et al [START_REF] Desmet | Framework of product experience[END_REF].

The emotional response as an outcome of the interaction and the emotions elicited are evaluated using 14 adjectives addressing the positive emotions joy, interest, surprise, and the need for diversion and competency. Seven of the items were focusing on the personal emotions (E-P) and the feeling of competence of the respondent (e.g. happy, proud, competent), and seven of the items were focusing on the emotional reaction towards the system (E-S) (e.g. pleasant, fascinating, fun). Items were based on work found in the literature [e.g. [10, 22, 25 39] and fit to the theoretical concepts.

To evaluate the stimulation dimension, the questionnaire uses six word-pairs including inventive vs. typical, or creative vs. standard amongst others. The identification dimension was evaluated using six word-pairs including premium vs. cheap, presentable vs. unpresentable, amateurish vs. professional amongst others. Item selection was mostly based on Hassenzahl's AttrakDiff [START_REF] Hassenzahl | The interplay of beauty, goodness, and usability in interactive products[END_REF] questionnaire and its dimensions hedonic quality -stimulation and hedonic quality -identification. To motivate respondents to respond on the basis of their concrete experiences, questions were asked in relation to their last TV usage that lasted at least 20 minutes, and also the repetition that the question is focusing on their TV system before each new UX scale in the questionnaire. The questionnaire consists of 33 items in total. It was developed in an English master version, which was then translated into [Language] for the administration of the questionnaire. The translation was checked using back-translation by native speakers against the master version, which is described as a common way of ensuring validity in cross-cultural research [START_REF] Brislin | Back-Translation for Cross-Cultural Research[END_REF].

The questionnaire was piloted in two steps, first using a think-aloud test, followed by pre-tests where three native speakers completed the questionnaire. Modifications resulting from the pre-tests have been incorporated in the questionnaire before its administration. Additionally, to be able to investigate differences between certain types of TV reception and the different types of IPTV set-top boxes available at the market in France, questions of how the respondents receive their TV signal and which kind of IPTV set-top box they own were added in the demographic part of the questionnaire. To get a higher response rate, and due to the fact that because of the current change to Digital Terrestrial Broadcasting, which also needs a set-top box to be received, the questionnaire was not limited to IPTV households only.

Usability of the evaluated system was evaluated using the already existing and validated SUS questionnaire. The SUS was included for further analysis of possible influences on the UX dimensions.

Validation Study

Method

Following our methodological approach, the aim of the study was to validate the first version of the developed questionnaire and to verify the applicability of the identified UX factors in the TV and IPTV domain. The questionnaire was presented as an online survey, allowing a uniform administration to a large number of respondents.

The dimensionality of the questionnaire items was analyzed using maximum likelihood factor analysis to investigate their fit to the underlying theoretical assumptions that UX in this setting can be evaluated using the UX dimensions aesthetics, emotion, stimulation and identification. This approach should subsequently inform the further development of the questionnaire, which aims to investigate domain-specific user experience dimensions in the TV and IPTV context.

Procedure and Participants

To validate the initial version of the iTV-UX questionnaire, the questionnaire was distributed online using the online survey tool surveymonkey.com. Participants were invited using e-mail, social networks, word of mouth and by personal invitation. The iTV-UX questionnaire had a brief introductory section, including obligatory statements on data anonymity, followed by a series of demographic questions (age, gender) and questions regarding the TV system used (reception, type of set-top box, media usage frequency). The sections of the questionnaireintroduction, demographics and media usage, UX scales, and debriefing -were represented on individual (web) pages. The questionnaire parts addressing the UX scales additionally had a brief introductory text to highlight that participants should evaluate the most recent 20 or more minutes usage of their TV system. At the end of the questionnaire, a standard usability scale was added. Questionnaire items were randomly inverted to avoid fill-in patterns like "1111". No monetary incentives were given to questionnaire participants. Overall, the fulfillment of the whole questionnaire lasted 10 minutes on average.

Over a three week period, 106 complete datasets were retrieved. 65 participants were between 20 and 29 years, 21 participants were between 30 and 39 years, and 20 participants were older than 40 years. 59.6 % were male, 40.4 % female (2 participants did not name their gender). The number of persons living in the household of the person filling in the questionnaire ranged from one to six persons. 15.2 % were living in single households, 46.7% of the participants lived in 2-person-households, 24.8% in 3-persons-households, and 13.4% of participants lived in households with 4 or more persons (n=105).

The vast majority (91.5%) of the participants watch TV at least once a week, with 64.2% watching every day, 22.6% several times a week and 4.7% of participants watching TV at least once a week. More than half of the participants (58.7%) receive their TV signal via ADSL (i.e. IPTV), 28.8% via digital terrestrial broadcast (TNT), 9.6% via satellite -Pay-TV, and 2.9% via satellite without Pay-TV (n=104).

The duration of the ownership of their current I(P)TV decoder was for a cumulated 83.5% more than six months, with 40.8% owning the decoder for more than 3 years; 33.0% for 1 year or more and 9.7% between 6 and 11 months. 7.8% of participants owned their decoder between 2 and 5 months, 5.8% between one and two months, 1.9% between 2 and 4 weeks and 1% for just a week (n=103). The rather large amount of new boxes can be explained by the fact that within the last half year, two major IPTV providers introduced the newest version of their set-top-box with new features and introductory offers.

The last TV usage situation was in 64.4% a social situation where the persons watched TV together with other persons, whereas 35.6% of participants watched TV alone (n=104). The last TV usage relative to the questionnaire submission date was in 92.6% of the cases within the last week, and for 73.4% of the answers even on the same day or the day before submission (n=94).

Data Analysis

Before further analysis of the results, the inter-item reliability of questions was computed for each original scale of UX dimensions using Cronbach's Alpha [START_REF] Cronbach | Coefficient alpha and the internal structure of tests[END_REF], which indicates the extent to which questions correlate to each other. A scale is typically considered reliable if its value for alpha is above the threshold of .7. The five scales used in the questionnaire had alphas ranging from .773 to .869 (Visual aesthetics: ,861, number of items =7; Emotion System ,852, n=8; Emo Personal ,773, n=6, Stimulation ,869, n=6; Identification: ,783 n=6). This analysis confirms that the scales are reliable indicators of the dimensions of UX we chose to investigate.

Factor Analysis

The UX questionnaire was using 33 items that were evaluated on a 7 point semantic differential scale using bi-polar adjectives. The items were addressing the UX dimensions aesthetics, emotion, stimulation and identification that were identified in the literature. The dimensionality of the 33 items from the UX questionnaire was subsequently analyzed using a maximum likelihood factor analysis. According to Kline [START_REF] Kline | The handbook of psychological testing[END_REF], performing factor analysis requires several participants per item, where the rule of thumb lies between 4 and 10 respondents per item, with a necessary minimum of 100 participants. For our first evaluation study, 106 participants for 33 questionnaire items is slightly below the 4 person per item rule, which seems to be reasonably acceptable for a first validation study to inform the further development of the questionnaire. Three criteria were used to determine the number of factors to rotate:

(1) the a priori hypothesis that the measures were not uni-dimensional, (2) the initial statistics of the principal component analysis including the Scree plot, and (3) the interpretability of the factor solutions in accordance to the theoretical UX factors framework.

The principal component analysis indicated that the initial hypothesis that the measures are not uni-dimensional was correct. The analysis yielded seven components with eigenvalues above 1, explaining 70 % of the variance. Based on inspection of the Scree plot (as the results for eigenvalues bigger than 1 was no supportive indicator), we decided to carry out a subsequent factor analysis with maximum likelihood extraction assuming 4 factors (according to the Scree plot, where the eigenvalues were flattening out after 4 factors and the fitting with the underlying theoretical assumptions), which were rotated using a varimax rotation procedure for the UX factors that were evaluated with the 7pt semantic differential.

The rotated solutions yielded four interpretable factors (see Table 2) for Visual Aesthetics (VA), Emotional reaction towards the System (E-S), Emotion Personal (E-P) and Stimulation (ST). The UX factors accounted for: 16% for Visual Aesthetics, 15% for Emotional -System, 13% for Stimulation, and 9% for Emotional Person of item variance. The factor labels from the theoretical background suited the extracted factors and were retained. A total of four items were eliminated because they did not contribute to a simple factor structure and failed to meet a minimum criteria of having a primary factor loading of .4 or above, and no cross-loading of .3 or above.

Overall, the Factorial analysis of the results of the first validation study showed that most of the evaluated UX factors were loading on the predefined factors and were fitting the assumed underlying theoretical concept. Nevertheless, the validation revealed some important insights for the further development of the questionnaire. The emotion dimension is as expected split into Emotion vs. the System and the Personal Emotion / Feeling of Competence of the respondent. The topic of identification as an UX dimension showed no clear own factor, and items that were assumed to fit into the identification dimension showed factor loadings on other dimensions in the factor analysis and were thus moved to these scales for further analysis and development of the questionnaire. The final set of items kept for the questionnaire are for Visual Aestethics (VA): beautiful-ugly; like/do not like design; appealing/unappealing, visually well-arranged/confusing; stylish/unstylish; premium/cheap; for emotional reaction towards system: fun/boring; entertaining/unamusing; pleasant/unpleasant; impressive/unimposing; exciting/lame, fascinating/uninteresting; for Emotion Personal: confident/unsure; competent/incompetent; happy/sad; proud/embarassed; for Stimulation: innovative/conservative; novel/commonplace; inventive/typical; creative/standard. All labels are translated from French.

Correlations between the UX Factor Scales

To investigate the interrelations between the different UX indicators, correlation coefficients (Spearman's roh) were computed among the four indicator scales. The results of the correlation analyses show that 8 out of the 12 correlations were highly significant (p < 0.01) and all were greater or equal to 0.403; In general, the results suggest that the user experience factors are highly interrelated, which goes in line with the opinion of most UX researchers in the HCI community that the elements of user experience are heavily interrelated and influencing each other mutually.

Moreover, these results could be interpreted as an indicator that these UX factors or dimensions cannot be viewed independently.

4.6

Correlations between Usability and UX Scales

For further investigation of the interrelations between different indicators, correlation coefficients (Spearman's roh) were computed. As a reference for usability, the questionnaire included the items from the SUS questionnaire.

The SUS rating of the system showed a significant correlation with all UX factor scales (Visual Aestethic ,447 p<0.001, ES ,642 p<0.001; EP ,528 p <0.01; ST ,271 p<005). The results indicate that the usability of interactive systems remains an important issue in evaluating iTV systems and usability is influencing the overall user experience of the evaluated IPTV systems. It is important to investigate in more detail how usability influences the perception of user experience, or if the two concepts are independent.

During further investigation and correlation analysis of the SUS rating indicator, no significant correlations could be found regarding the independent variables "Type of TV Reception", "Type of IPTV Bow owned", "Period of ownership of decoder", "Age", "Sex", "Number of Persons in Household", or "TV usage frequency" and "Number of Persons in Household".

Other Insights

Regarding the independent variables "Age", "Sex" and "Number of Persons in Household", no significant correlation could be found for the UX indicators. We observed no significant correlations between the UX scales and the type of TV signal reception (Terrestrial, ADSL, Satellite). Nevertheless, we discovered a significant correlation between the type of IPTV box owned and the Emotion-System scale (rho= 0.346, p<0.01), as well as for the Stimulation scale (rho= 0.267, p<0.05).

Overall, the UX ratings for the observed dimensions in our sample were rather low, but with a positive trend for the Visual Aesthetics and both Emotion vs. System and Emotion Personal dimensions. The negative trend in the results regarding the Stimulation dimension suggest that in general, TV systems are not perceived as stimulating devices. This shows that the user experience can be different for systems, even if the perceived usability is the same.

Using One-Way ANOVA on the means of the four UX scales extracted from the factor analysis, there is a significant effect of TV reception type on the Emotion-System scale at the p<.05 level for the four conditions [F(3,99) = 2.88, p = .04].

Post hoc comparisons using the Tukey HSD test indicated that the mean score for the satellite Pay-TV condition (M = 1.11, SD = 0.80) was significantly different than the ADSL-IPTV condition (M = .17, SD = 1.02) and the TNT condition (M = .14, SD = .92). However, the Satellite (without Pay-TV) condition (M = .34, SD = .76) did not significantly differ from the other conditions. Taken together, these results suggest that the Pay-TV offer via satellite does have a positive effect on the emotion versus the system.

Another One-Way ANOVA was conducted to compare the effect of the type of ADSL box on the on the means of the four User Experience scales extracted from the factor analysis.

There was a significant effect of the type of ADSL box, again on the Emotion-System Scale, at the p<.05 level for the six conditions [F(5,52) = 2.79, p = .026].

Post hoc comparisons using the Tukey HSD test indicated that the mean score for one of the recently introduced IPTV boxes (M = 1.08, SD = .88) was significantly different than the other IPTV boxes.

As the sample size was low (58, 3 entries for 2 types of IPTV boxes were excluded), and Type II Errors are frequently in small sample sizes, additional post hoc comparisons using LSD were carried out, which resulted in a significant difference of the same IPTV box compared to all the other boxes. Taken together, these results suggest that this newly introduced IPTV set-top box which is including e.g. a BluRay Player, HDTV, a remote control that includes some simple gesture interaction and has a very elaborate design approach does have a positive effect on the emotional reaction versus the system.

Discussion of Results

The work reported here is clearly the first validation of the questionnaire. At current stage we have to deal with the following limitations: (1) the composition of the current sample influences the results; (2) the systems used influence the results; (3) participants answered the questionnaire not directly after the interaction with their iTV system. The clear limitation of the rather small sample size will be addressed in the next iteration of the questionnaire, which will be evaluated using a larger sample to assure the validity of the factor analysis.

The strong correlations between the UX factors up to now only show that variables are related, but not the determining influence in a particular direction. Moreover, Spearman's Roh correlations also do not state which influences are dominating determinants on particular factors. Therefore, a regression analysis will be conducted in future to come up with a model for iTV-UX, which can also be used and applied by fellow researchers in the field. This statistical model approach will enable fellow researchers to use the complete questionnaire or to focus only on specific influences, which means only a part of the UX dimensions are used. This step will be taken within the analysis of the next iteration of the questionnaire to assure validity through a higher sample size and coverage of a higher number of UX dimensions.

The extensibility of the questionnaire is critical for the development of a successful iTV user experience evaluation method, as next generation iTV system will include for instance social functionalities, new ways of representation of content and information (e.g. 3D), and also more sophisticated interaction modalities like touch, gesture or motion interaction.

Summary and Future Work

In this paper, we presented the results of a study aiming at the evaluation of a set of literature-based user experience dimensions for TV and IPTV systems using a questionnaire-based approach. The assessed UX dimensions were aesthetics, emotion, stimulation and identification. Results from a performed factor analysis showed that except for the identification dimensions all evaluated UX dimensions were loading on the predefined assumed factors and were fitting the assumed underlying concept. Also the factor labels from the theoretical framework suited the extracted factors and were retained; the extracted factors were labeled Visual Aesthetics, Emotion vs. the System, Emotion Personal, and Stimulation. Correlation analysis showed that the UX dimensions are highly interrelated, which goes in line with the opinion of most UX researchers in the HCI community that the elements of User Experience are heavily interrelated and influencing each other mutually. Additional analysis revealed also strong correlations of the UX scales to the Usability rating gained from the SUS scale. The assumed UX dimension identification did not show a clear own factor, the items assumed to fit into this dimensions showed mostly loadings on other factors. This suggests that identification may not be a major UX dimension for the domain of IPTV. A detailed list of the results of the factor analysis and the items used in the evaluation can be found in Table 2. Overall UX ratings for the observed UX dimensions were rather low, although all dimensions except stimulation showed a positive trend, which suggests that in general, TV and IPTV systems are not perceived as stimulating devices.

During further analysis we observed significant correlations between the type of IPTV box owned and the emotional reaction towards the system and the stimulation dimension. We also observed a significant effect of the TV reception mode on the emotion towards the system, which was significantly better for Pay-TV Systems via satellite compared to ADSL/IPTV offers and TNT. Also the type of ADSL/IPTV box showed a significant effect on the emotion towards the system, where a newly introduced IPTV set-top box which is including e.g. a BluRay Player, HDTV and has a very elaborate design approach is evaluated significantly better than other boxes.

While the usability of the systems was perceived the same for all IPTV offers, the UX evaluation indicates differences in the perception, indicating that the two concepts are different.

For our research goal to develop a questionnaire that covers an extensive and holistic collection of UX dimensions for the iTV domain, the present evaluation study was the first step. We followed our methodological approach to start with a smaller set of literature-based UX dimensions (aesthetics, emotion, stimulation and identification) and validate their applicability for the IPTV domain. Results are promising and supported our underlying theoretical assumptions that these dimension are important in this setting and measurable.

A second phase of validation with a revised questionnaire will address the identified limitations by extending the sample, ensuring that the interaction with the iTV system occurs closely related to filling in the questionnaire and by enclosing additional UX factors. These will include the value of the system for the user, social factors (shared usage, co-experience), the interaction and interaction technology, and also the perception of the quality of service. This next version aims to cover the major dimensions that are influencing the user experience in this field. When looking at recent attempts on social interactive TV systems, social factors seem to become an important factor for the evaluation of future systems. The construct of relatedness will be addressed together with other social factors like shared usage and co-experience. Evaluating these social factors can provide more valuable insights if future TV or connected home systems support social applications like communication. Also the ongoing development of interaction technologies that go beyond a standard button remote, e.g. by integrating gyroscopes or using touch-screens, will be considered in future versions of the questionnaire, and the interaction will be addressed as a factor influencing the UX of an IPTV system. The next iteration of the questionnaire will also incorporate entertainment-oriented UX factors like flow, as on state of the art IPTV set top boxes, games and other services are introduced and iTV systems and gaming consoles are moving closer towards each other.

Table 1 .

 1 Results of literature review identifying four major user experience dimensions (VM:Value/Meaning, SRC: Social/Relatedness/Co-Experience; C:Challenge; DST: Dependability/Security/Trust; SQ: Service Quality)

		Aesthetic	Emotion/ Affect	Stimulation Identification Others
	Hekkert 2006 [21]	x	x	VM
	Desmet and Hekkert 2007

Table 2 .

 2 Four Factors and their items, rev -reversed, * item indicates removed in final version

	Ass. Dim.	Item
		Visual Aesthetics (VA)	VA	E-S	E-P	ST
	VA	Beautiful -ugly	,843	,205	,027	,162
	VA	like the design / don't like design	,803	,127	,018	,196
	VA (rev)	appealing -unappealing	,790	,011	,047	,214
	VA	visually well-arranged -confusing	,650	,281	,143	,193
	I	stylish -unstylish	,607	,233	,135	,264
	I	premium -cheap	,604	,313	,073	,374
	VA (rev) *	clear lines -irregular	,566	,069	,038	,030
	I (rev) *	Presentable-unpresentable	,563	,285	-,054	,218
	VA (rev) *	Flawless -imperfect	,514	,071	,106	,197
	VA *	symmetric -asymmetric	,358	-,004	-,061	-,026
		Emotional Reaction towards System (E-S)
	E-S	fun -boring	,113


Jean Berstel

Luc Boasson

Olivier Carton

Isabelle Fagnot

A First Investigation of Sturmian Trees

We consider Sturmian trees as a natural generalization of Sturmian words. A Sturmian tree is a tree having n+1 distinct subtrees of height n for each n. As for the case of words, Sturmian trees are irrational trees of minimal complexity. We give various examples of Sturmian trees, and we characterize one family of Sturmian trees by means of a structural property of their automata.

Introduction

Sturmian words have been extensively studied for many years (see e.g. [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF][START_REF] Pytheas-Fogg | Substitutions in Dynamics, Arithmetics and Combinatorics[END_REF] for recent surveys). We propose here an extension to trees.

A Sturmian tree is a complete labeled binary tree having exactly n+1 distinct subtrees of height n for each n. Thus Sturmian trees are defined by extending to trees one of the numerous equivalent definitions of Sturmian words. Sturmian trees share the same property of minimal complexity than Sturmian words: indeed, if a tree has at most n distinct subtrees of height n for some n, then the tree is rational, i.e. it has only finitely many distinct infinite subtrees.

This paper presents many examples and some results on Sturmian trees. The simplest method to construct a Sturmian tree is to choose a Sturmian word and to repeat it on all branches of the tree. We call this a uniform tree, see Fig. 1. However, many other categories of Sturmian trees exist.

Contrary to the case of Sturmian words, and similarly to the case of episturmian words, there seems not to exist equivalent definitions for the family of Sturmian trees. This is due to the fact that, in our case, each node in a tree has two children, which provides more degrees of freedom. In particular, only one of the children of a node needs to be the root of a Sturmian tree to make the whole tree Sturmian.

Each tree labeled with two symbols can be described by the set of words labeling paths from the root to nodes sharing a distinguished symbol. The (infinite) minimal automaton of the language has quite interesting properties when the tree is Sturmian. The most useful is that the Moore equivalence algorithm produces just one additional equivalence class at each step. We call these automata slow. We have observed that two parameters make sense in studying Sturmian trees: the degree of a Sturmian tree is the number of disjoint infinite paths composed of nodes which are all roots of Sturmian trees. The rank of a tree is the number of distinct rational subtrees it contains. Both parameters may be finite or infinite.

The main result of this paper is that the class of Sturmian trees of degree one and with finite rank can be described by infinite automata of a rather special form. The automata are obtained by repeating infinitely many often a distinguished path in some finite slow automaton, and intertwining consecutive copies of this path by letters taken from some Sturmian infinite word. Another property is that a Sturmian tree with finite degree at least 2 always has infinite rank.

The class of Sturmian trees seems to be quite rich. We found several rather different techniques to construct Sturmian trees. To the best of our knowledge, there is only one paper on Sturmian trees prior to the present one, by Carpi, De Luca and Varricchio [START_REF] Carpi | Special factors and uniqueness conditions in rational trees[END_REF].

Sturmian Trees

We are interested in complete labeled infinite binary trees, and we consider finite trees insofar as they appear inside infinite trees.

In the sequel, D denotes the alphabet {0, 1}. A tree domain is a prefix-closed subset P of D * . Any element of a tree domain is called a node. Let A be an alphabet. A tree over A is a map t from a tree domain P into A. The domain of the tree t is denoted dom(t). For each node w of t, the letter t(w) is called the label of the node w. A complete tree is a tree whose domain is D * . The empty tree is the tree whose domain is the empty set. A (finite or infinite) branch of a tree t is a (finite or infinite) word x over D such that each prefix of x is a node of t. Example 1. (Dyck tree) Let A be the alphabet {a, b}. Let L be the set of Dyck words over D = {0, 1}, that is the set of words generated by the context-free grammar with productions S → 0S1S + ε. The Dyck tree is the complete tree defined by

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • t[0, 3] t[010, 2]
t(w) = a if w ∈ L, b otherwise. ( 1
)
The top of this tree is depicted in Fig. 2. The first four words ε, 01, 0101 and 0011 of L correspond to the four occurrences of the letter a as label on the top of the tree.

More generally, the characteristic tree of any language L over D is defined to be the tree t given by (1). Conversely, for any tree t over some alphabet A, and for any letter a in A, there is a language L = t -1 (a) of words labeled with the letter a. The language L = t -1 (a) is called the a-language of t. In the sequel, we usually deal with the two-letter alphabet A = {a, b}, and we fix the letter a.

We then say the language of t instead of the a-language.

We shall see that the a-languages of a tree t are regular if and only if the tree t is rational. For any word w and any language L, the expression w -1 L denotes the set w -1 L = {x | wx ∈ L}. Let t be a tree over A and w be a word over D. We denote by t[w] the tree with domain w -1 dom(t) defined by t[w](u) = t(wu) for each u in w -1 dom(t). The tree t[w] is sometimes written as w -1 t, for instance in [START_REF] Carpi | Special factors and uniqueness conditions in rational trees[END_REF]. If w is not a node of t, the tree t[w] is empty. A tree of the form t[w] is the suffix of t rooted at w. Suffixes are also called quotients or subtrees in the literature.

Let t be a tree over A and let w be a word over D. For a positive integer h, we denote by D <h the set (ε + D) h-1 of words over D of length at most h -1. We set D <0 = ∅.

Let h be a nonnegative integer. The truncation of a tree t at height h is the restriction of t to the domain D <h . Any tree obtained by truncation is called a prefix of t. A factor of t is a prefix of a suffix of t. More precisely, for any word w and any nonnegative integer h, we denote by t[w, h] the factor of height h rooted at w, that is the tree of domain w -1 dom(t) ∩ D <h and defined by t[w, h](u) = t(wu). A factor of height 0 is always the empty tree. A factor t[w, 1] of height 1 can be identified with the letter t(w) of A that labels its root. A prefix is a tree of the form t[ε, h].

Factors of height h are sometimes considered to have height h -1 in the literature (e.g. [START_REF] Carpi | Special factors and uniqueness conditions in rational trees[END_REF]). In this paper, the height of a finite tree is the number of nodes along a maximal branch and not the number of steps in-between. Our convention will be justified by Proposition 1 which extends a similar result for words in similar terms.

A tree is rational if it has finitely many distinct suffixes. Recall (see e.g. [START_REF] Courcelle | Fundamental properties of infinite trees[END_REF]) that a tree over an alphabet A is rational if and only if t -1 (a) = {w ∈ D * | t(w) = a} is a regular subset of D * for each letter a of A. For instance the Dyck tree t of Example 1 is not rational since t -1 (a) is the Dyck language which is not regular [6]. The following proposition gives a characterization of complete rational trees using factors. It extends to trees the characterization of ultimately periodic words by means of their subword complexity [START_REF] Coven | Sequences with minimal block growth[END_REF]. This statement appears in [START_REF] Carpi | Special factors and uniqueness conditions in rational trees[END_REF]. Proposition 1. A complete tree t is rational if and only there is an integer h such that t has at most h distinct factors of height h.

A complete tree is Sturmian if for any integer h, it has h + 1 factors of height h. Since the factors of height 1 are the letters t(w) a Sturmian tree is defined over a two letter alphabet. In what follows, we always assume that this alphabet is {a, b}.

We will prove later that the Dyck tree given in Example 1 is indeed Sturmian. We start with some simpler examples of Sturmian trees.

In the first of these examples, the same infinite word is repeated along each branch of the tree.

Example 2. (Uniform trees) Let x = x 0 x 1 x 2 • • • be an infinite word over an alphabet A, where x 0 , x 1 , x 2 , . . . are letters. The uniform tree of x is the complete tree t defined by t(w) = x |w| . This means of course that all nodes of the same level n in the tree are labeled with the same symbol x n . If x is a Sturmian word, then its uniform tree t is a Sturmian tree. Figure 1 shows the top of the uniform tree of the Fibonacci word x = abaaba • • • .

Example 3. (Left branch tree) Let x = x 0 x 1 x 2 • • • be an infinite word over A, where x 0 , x 1 , x 2 , . . . are letters. We define a complete tree t by t(w) = x |w|0 . (Recall that |w| d is the number of occurrences of d in w.)

The label of each node w is the letter x n of x, where n is the number of symbols 0 occurring on the path from the root to w. The label of the root node is x 0 . If the label of w is x n , the labels of w0 and w1 are respectively x n+1 and x n .

In particular, the letters of the word x label the nodes of the leftmost branch of the tree, and all nodes on a rightmost branch share the same label. Figure 3 shows the top of the left branch tree of the Fibonacci word x = abaaba • • • . We write x[n, h] for the factor x n x n+1 Example 4. (Indicator tree) Let x be an infinite word over D. The indicator tree of x is the complete tree t defined by

t(w) = a if w is a prefix of x, b otherwise.
In other terms, there is exactly one infinite path in t with all its nodes labeled by the letter a. The letters of this path are the letters of the word x. Equivalently, the indicator tree of the infinite word x is the characteristic tree of the language composed of its (finite) prefixes. Figure 4 shows the indicator tree of the Fibonacci word. It can be easily proved that x is a Sturmian word if and only if its indicator tree t is a Sturmian tree.

The following example is a variation on Example 4. For a finite word w and an infinite word x, we denote by d(w, x) the integer |w| -|u| where u is the longest common prefix of w and x.

Example 5. (Band indicator tree) Let x be an infinite word over D and let k be a non-negative integer. The band indicator tree of width k is the complete tree t defined by

t(w) = a if d(w, x) ≤ k, b otherwise.
Again, x is a Sturmian word if and only if t is a Sturmian tree. The band indicator tree of width 0 is the indicator tree defined in Example 4, since d(w, x) ≤ 0 if and only if w is a prefix of x.

Rank and Degree

Recall that a branch of a tree is a (finite or infinite) word x over D such that each prefix of x is a node of the tree.

A node w of a tree t is called rational if the suffix t[w] is a rational tree. It is called irrational otherwise. The rank of a tree t is the number of distinct rational suffixes of t. This number is either a nonnegative integer or infinite.

If w is an irrational node, then its prefixes also are irrational. Furthermore, at least one of the two words w0 and w1 also is irrational. The set of irrational nodes of a tree is a tree domain in which any finite branch is the prefix of an infinite branch.

The degree of a tree t is the number of infinite branches composed of irrational nodes. This number is either a nonnegative integer or infinite.

As a first example, consider the Dyck tree defined in Example 1. It has rank 1 and has infinite degree. A node w of this tree is rational if it is not a prefix of some Dyck word. The set of rational nodes is thus the set L1D * where L is the set of Dyck words. On the contrary, each branch in 00 * 10 ω only contains irrational nodes. The degree of the Dyck tree is thus infinite.

Next, let t be the indicator tree of a Sturmian word x, as defined in Example 4. A node w of t is irrational if and only if it is a prefix of x. Thus, the word x itself is the only infinite branch composed of irrational nodes, and therefore the degree of this tree is 1. All rational subtrees are the same, so this tree has rank 1.

These examples show that there are Sturmian trees of degree 1 or of infinite degree. It turns out that there exist also Sturmian trees of finite degree greater than 1. In the final section, we construct a Sturmian tree of degree 2 but this construction is rather involved.

Here is a table summarizing the relations between degree and rank for Sturmian trees. A tree with rank 0 always has infinite degree since there is no rational node. rank degree finite infinite 1 characterized in Theorem 1 Example 8 Indicator tree (rank 1) Band width tree (rank d + 1) ≥ 2, finite empty by Proposition 4 example not given here infinite Uniform tree (rank 0)

example not given here Left branch tree (rank 0) Dyck tree (rank 1)

The main result of the paper is the characterization of Sturmian trees of degree 1 and with finite rank by a structural property of the minimal automaton of its language.

Slow Automata

Let t be a complete tree over {a, b}. The language of t is the set t -1 (a). We study properties of trees by considering automata recognizing their language. In particular, minimization of automata will play a central role.

We recall elementary properties of automata, just observing that they hold also when the set of states is infinite. We only use deterministic and complete automata. An automaton A over a finite alphabet D is composed of a state set Q, a set F ⊆ Q of final states, and of a next-state function Q × D → Q that maps (q, d) to a state denoted by q • d. Given a distinguished state i, a word w over D is accepted by the automaton if the state i•w is final. When we emphasize the existence of state i, we call it the initial state as usual.

An automaton B is a subautomaton of an automaton A if its set of states is a subset of the set of states of A which is closed under the next-state function of A. The next state function is given by n

• 0 = n + 1 for n ≥ 0, n • 1 = n -1 for n ≥ 1, 0 • 1 = ∞ and ∞ • 0 = ∞ • 1 = ∞.
This automaton is depicted in Fig. 6. We call it the Dyck automaton. The singleton {∞} is the unique proper subautomaton of the Dyck automaton. Given an arbitrary automaton A, we define inductively a sequence (∼ h ) h≥1 of equivalence relations on Q as follows.

q ∼ 1 q ⇐⇒ (q ∈ F ⇐⇒ q ∈ F ) q ∼ h+1 q ⇐⇒ (q ∼ h q and ∀d ∈ D q

• d ∼ h q • d)
These are well-known in the case of finite automata, and many properties extend to general automata. We call ∼ h the Moore equivalence of order h. The index of ∼ h is the number of equivalence classes of ∼ h . The Moore minimization algorithm consists in computing inductively the Moore equivalences.

The equivalence ∼ h+1 is a refinement of the equivalence ∼ h . Thus the index of ∼ h+1 is at least the index of ∼ h . An automaton is called slow if it is minimal and if the index of ∼ h is at most h+1 for all h ≥ 1. If ∼ h and ∼ h+1 are different, that there is one class c of ∼ h which gives raise to two classes in ∼ h+1 . We say that ∼ h+1 splits class c, or that class c is split by ∼ h+1 .

It is sometimes useful to distinguish, in a minimal automaton, two kinds of states. A state p is rational if it generates a finite subautomaton. States which are not rational are called irrational. In the minimal automaton associated to the language of a tree, a state is rational if and only if it corresponds to the root of a rational tree.

The following proposition shows that the classes of ∼ h are in a one to one correspondence with the factors of t of height h. Proposition 2. Let t be a complete tree over {a, b} and let A be an automaton over D accepting the language of t, with initial state i. For any words w, w ∈ D * and any positive integer h, one has

i • w ∼ h i • w ⇐⇒ t[w, h] = t[w , h] .
Corollary 1. Let t be a complete tree over {a, b} and let A be an automaton over D accepting the language of t. The tree t is Sturmian iff the minimal automaton of its language is infinite and slow.

A Tree of Degree One

In this section, we give an example of a family of Sturmian trees with finite rank and of degree 1 by describing the family of automata accepting their languages. These (infinite) automata are based on a finite slow automaton. In this automaton, a path is distinguished (called a lazy path). The infinite automaton is obtained by repeating the lazy path and intertwining the copies with symbols taken from an infinite Sturmian word.

In the next section, we show that any Sturmian tree of degree 1 and with finite rank can be obtained in this way. Let A = (Q, {i}, F ) be a finite deterministic automaton over the alphabet D with N states. We assume that A has the two following properties. First, A is slow. Recall that by definition, this means that the automaton is minimal and that the Moore minimization algorithm splits just one equivalence class into two new classes at each step.

0 1 2 3 4 5 6 7 8 • • • p r s 0 0 0 x0 0 0 0 x1 0 1 1 1 1 1 1 1 x0 x1 0 1 0 1 0, 1
Next, we suppose that there is a lazy path in A. This is a path

π : q 0 a0 -→ q 1 a1 -→ q 2 • • • q h-1 a h-1 ---→ q h
of length h, where q 0 and q h are the two states which are separated in the last step in the Moore algorithm together with the condition that q h-1 • āh-1 = q 0 or q h where ā = 1a for a ∈ D. If N ≥ 2, the first of these conditions means that q 0 ∼ N -2 q h and q 0 ∼ N -1 q h . As a consequence, the second property means that q h-1 • āh-1 cannot be separated from q h-1 • a h-1 before the very last step of the Moore algorithm.

Example 7. The automaton  given in Fig. 7 has a subautomaton A composed of the states {p, s, r}. This subautomaton is slow: the first partition is into {p, r} and {s}, and the second partition is equality. The finite subautomaton A in Fig. 7 admits for example the lazy path π : p 0 -→ s 0 -→ p 0 -→ s 1 -→ r, and indeed s 0 -→ p. Here h = 4.

Given the finite slow automaton A, the lazy path π and an infinite word x = x 0 x 1 x 2 • • • over D, we now define an infinite minimal automaton  which accepts the set of nodes labeled a of a tree t. We will show that if x is a Sturmian word, then t is a Sturmian tree of degree 1. This automaton is the extension of A by π and x, and is denoted by  = A(π, x).

The set of states of  is Q ∪ N. For convenience, we use a mapping q : N → Q defined by q(n) = q n mod h for any n ∈ N. Here and below q 0 , . . . , q h are the states of the lazy path of A and a 0 , . . . , a h-1 are the letters labeling the path. The initial state of  is 0 and its set of final states is F ∪ q -1 (F ). The next-state function of A is extended to  by setting, for n ∈ N,

(α) if n ≡ h -1 mod h, then n • a n mod h = n + 1, n • ān mod h = q(n) • ān mod h (β) if n = ih + h -1 for some i ≥ 0, then n • x i = n + 1, n • xi = q 0
The infinite path through the integer states of the automaton  is composed of an infinite sequence of copies of the lazy path of A. For each state q(n) inside each of the copies of the lazy path, the next-state for the "other" letter, that is the letter ān mod h , maps q(n) back into A. Two consecutive copies of the lazy path, say the ith and i + 1th, are linked together by the letter x i of the infinite word x driving the automaton (see Fig. 7). Proposition 3. Let  = A(π, x) be the extension of the finite slow automaton A by a lazy path π and an infinite word x. If the word x is Sturmian, then  defines a tree t which is Sturmian, of degree 1, and having finite rank.

The tree defined by this automaton has degree 1 since the only irrational states are the integer states n and they all lie on a single branch. Its rank is the number of states of A. We claim that this tree is also Sturmian.

Characterization

In this section, we give a characterization of Sturmian trees of degree 1 which have finite rank by describing the family of automata accepting their languages. These (infinite) automata are extensions of a finite automaton by a lazy path and a Sturmian word.

Theorem 1. Let t be a Sturmian tree of degree one having finite rank, and let  be the minimal automaton of the language of t. Then  is the extension of a slow finite automaton A by a lazy path π and a Sturmian word x, i.e.  = A(π, x).

Given a tree t and some Moore equivalence ∼ h on its minimal automaton, it is convenient to call an equivalence class of ∼ h an irrational class if it is entirely composed of irrational states. It is a rational class otherwise. A rational class contains at least one rational state, and may contain even infinitely many irrational states.

Q ∪ N p,
Up to now, all our examples of Sturmian trees are of finite rank. It can be observed that for all of them the degree is either 1 or infinite. This is unavoidable. Proposition 4. The degree of a Sturmian tree with finite rank is either one or infinite.

A Tree With Infinite Rank

There exist Sturmian trees with infinite rank. The following example gives a Sturmian tree with infinite rank and of degree 1.

Concluding Remarks

In this paper, we have introduced the notion of Sturmian trees. We have considered two parameters, the degree and the rank, and we have described Sturmian trees of finite rank and finite degree.

We have given several examples of Sturmian trees of finite rank and infinite degree. All these are in some sense easy. There exist more involved examples of trees in this family. Such examples may be constructed using more than one Sturmian word.

In this short note, we have presented only one Sturmian tree of infinite rank which is of degree one. Using some kind of fractal structure, we are able to build Sturmian trees of infinite rank and of degree two or more. Similarly, we know some Sturmian trees for which both degree and rank are infinite. None of these examples is given here due to the lack of space. They will be presented in a forthcoming full version.

Fig. 1 .

 1 Fig. 1. The top of a uniform tree for the word abaaba • • • . Node label a is represented by •, and label b is represented by •. This tree will be seen to have infinite degree and rank 0.

Fig. 2 .

 2 Fig. 2. The top of the Dyck tree of Example 1 and two of its factors, of height 3 and 2, respectively. Again, a is represented by • and b by •.

Fig. 3 .

 3 Fig. 3. The top of a left branch tree for the word abaaba • • • .

Fig. 4 .Fig. 5 .

 45 Fig. 4. The top of the indicator tree for the Fibonacci word 01001010 • • • . The only nodes labeled a are on the Fibonacci path.

Example 6 .

 6 (Dyck automaton) The following automaton accepts the Dyck language. The set of states is Q = N ∪ {∞}. The initial and unique final state is 0.

Fig. 6 .

 6 Fig.6. Automaton of the Dyck language. State 0 is both the initial and the unique final state.

Fig. 7 .

 7 Fig. 7. A slow automaton  for the Fibonacci word x0x1 • • • = 01001010 • • • . The final states are p, r, 0, 2, 4, • • • .

Fig. 8 .

 8 Fig. 8. The tree showing the evolution of the Moore equivalence relations on the automaton given in Fig. 7. Each level describes a partition. Each level has one class splitting into two classes at the next level.

Example 8 .

 8 We define a tree by giving a (minimal) automaton accepting its language. The set of states of the automaton isQ = {n ∈ N | n ≥ 3} × {0, 1}. The set of final states is the set {(n, b) ∈ Q | n ≡ 0 mod 2}.The set E of transitions is defined as follows. Let n = 2 k m where m ≥ 1 and m ≡ 0 mod 2. The integer 2 k is then the greatest power of 2 which divides n.(n, b) • 0 = (2 k-1 + 1, 0) if m = 1 and b = 0 (n + 1, b) otherwise (n, b) if k = 2, m = 1 and b = 0 (2 k-2 + 1, 0) if k > 2, m = 1 and b = 0 (2 k-1 + 1, 0) otherwiseIn Fig.9, we give a picture of this automaton; states of the form (n, 0) are drawn as circles n and states of the form (n, 1) as squares n .

Fig. 9 .

 9 Fig. 9. Final states are dark. Observe the fractal-like structure, with a doubling of the size of each block.

  • • • x n+h-1 of the word x. In Example 2, two factors t[w, h] and t[w , h] of height h are equal if and only if x[|w|, h] = x[|w |, h]. In Example 3, t[w, h] and t[w , h] are equal if and only if x[|w| 0 , h] = x[|w | 0 , h]. It follows that in these examples, the tree t is Sturmian if and only if the word x is Sturmian.