Mareike Picklum

Georg Modzelewski

Susanne Knoop

Toke Lichtenberg

Philipp Dittmann

Tammo Böhme

Volker Fehn

Christian John

Johannes Kenkel

Philipp Krieter

P Niethen

N Pampuch

M Schnelle

Y Schwarte

S Stark

A Steenbergen

M Stehr

H Wielenberg

M Yildirim

C Yüzüncü

F Pollmann

D Wenig

R Malaka

Player Control in a Real-Time Mobile Augmented Reality Game

Keywords: mobile gaming, augmented reality, AR, user interaction, gestures

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

On smartphones, controlling characters in augmented reality games has a lot in common with touch-based games but there is an additional problem: To receive visual feedback of his actions the player needs to keep the AR world in view, so one is not entirely free to choose his device's position.

Within a students' project we developed a real-time mobile augmented reality game in which two virtual characters fight against each other. Each player controls a character in the AR world, which is created by having both devices track the same marker (Fig. 1) and communicate wirelessly. While each player can see both characters, one only controls his own. Additional information about the current game state as well as buttons to initiate actions are displayed on the screen (Fig. 1). The player can control the avatar's movement and initiate primary and secondary attacks. He is also able to block the enemy's attacks. Primary attacks have a short range, e.g. kicks or punches while secondary attacks can be long ranged e.g. fireballs. The movement speed of the character is limited to prevent the avatar from moving instantly to the point the user clicked on.

In this paper we suggest different input options for the best game experience in our AR game and propose further research to evaluate them.

Hürst and van Wezel [START_REF] Hürst | Multimodal Interaction Concepts for Mobile Augmented Reality Applications[END_REF] developed a system in which the user's own hands or fingers are used to interact with the 3D objects. Avatars can be moved or knocked over by using the finger behind the device to 'push' the models instead of touching the display. Usability tests showed that users interacting with objects while holding a mobile device with one hand and moving the other one in front of the camera results '... in an awkward hand position or even forces people to switch the hand in which they hold the device.' Harviainen et al. [START_REF] Harviainen | Camera-based interactions for augmented reality[END_REF] used camera movement and accelerometers to control virtual characters. In one example an animated model of a dog reacts to the camera movement, while another implementation uses the accelerometer to detect shaking or tilting of the phone. Gu et al. [START_REF] Gu | 7. In: A Platform for Mobile Collaborative Augmented Reality Game: A Case Study of " AR Fighter[END_REF] developed a game similar to ours and used the accelerometer to move a character and touches on the screen to initiate actions. They did not evaluate the effects of different input options on the game experience. Calvillo-Gámez et al. [START_REF] Calvillo-Gámez | Human-Computer Interaction Series[END_REF] developed a questionnaire to measure game experience.

Interaction concepts

When developing mobile interaction concepts several factors need to be considered to provide the best user experience. Often the screen is both input and output device. The more control elements are placed on the screen the higher is the risk of occluding important parts of the game with the user's fingers. This might have a negative effect on the game experience and make it difficult to control it in a real-time environment. As the touch screen provides no inherent haptic feedback, the user has to actively make sure his fingers are in contact with the displayed control elements which lowers the immersion by forcing him to focus not on game content but on input modalities. An additional difficulty in AR games on smartphones is to permanently keep the tracked marker in the field of view of the device's camera.

The control of character movement in a game can be relative, with respect to the position of the player, or absolute, with respect to absolute coordinates of the AR world. Absolute control means that the player sets the goal of the movement and the avatar moves to the destination by itself without further interaction of the player. For continuous control the input is read in each update cycle of the game, forcing the player to give continuous input until the desired position is reached. Discrete input starts a perpetual movement until it is interrupted by further user input or the destination is reached. To improve user experience, feedback can be provided, e.g. to notify the player if his fingers are no longer in contact with the control elements on the touch screen or if the marker can no longer be tracked. While this feedback could use all output channels of the device it is important that the user can distinguish between the provided input feedback and the regular game output at any time. Feedback can be provided using vibration, audio signals and visual hints like a flashing screen or a some kind of in-game feedback of the character (e.g. stumbling).

The following concepts concentrate on controlling the movement of the character. Primary and secondary attacks as well as blocking are initiated by touching buttons displayed on the screen. The concepts focus on the touch screen and other built-in sensors of the devices.

Touch-based virtual joystick Some mobile games use a concept similar to a joystick but without the need for the actual hardware device. A circle is drawn on the corner of the screen and the position of a touch in relation to the center of the circle defines the position of the virtual joystick. It is usually used with a thumb. Virtual joysticks provide movement control relative to the character's position. They require the continuous and correct placement of the player's finger on the control element, occluding only a small part of the screen. Feedback can be provided if the finger is no longer touching the control element.

Touch-gesture control Swipe gestures are well established to interact with smartphones. They are used to initiate the movement of the character in the indicated direction. Tapping on the screen stops the movement.

Physical control buttons Some Android devices like the Motorola Milestone have physical keyboards which can be used to move the player model relatively to its current position with a set of predefined keys, analogous to many desktop games. This easy and intuitively understandable technique is established in many other applications. As most of the common devices currently on the market do not have a physical keyboard integrated, this concept is not suitable in general but provides the best haptic feedback.

Touch-based absolute control The user sets the location in the AR world by tapping on a point on the screen, occluding it only for a short period of time. The destination is set in the AR world, so moving the device does not change the target position. Depending on the distance between the current and the desired position of the avatar it might take some time before the movement is finished.

It could be helpful to place a visual hint such as a flag or cross-hair in the AR world to remind the player about the current destination.

Field-of-view-based continuous control Instead of requiring the user to select a specific point, the destination is continuously updated to the center of the camera's current field of view. Moving the device and thereby the AR viewport allows the player to control the character. This is even true if the player does not intend to move the character. An alternative to the continuous updating could be realized by pressing a button to set the new destination. Again a visual hint can be helpful to indicate the current movement target.

Physical gestures Modern smartphones offer additional sensors like gyroscopes or accelerometers which can be used as input in games. They react to movements like tilting, rotating or shaking of the device. These gestures would also change the viewport on the AR world because the camera is fixed on the device. Further research has to show if the accompanying viewport change has a detrimental effect on the game experience in a real-time game.

Conclusion & Future Work

We presented several possible concepts for player control in mobile AR scenarios. Using visual, auditive or haptic feedback might mitigate the shortcomings of some of these concepts. Prototypical implementations will be used to conduct further game experience studies.

Fig. 1 .

 1 Fig. 1. left: AR mockup; middle: actual prototype; right: screen capture of the prototype. a) player/device 1, b) player/device 2, c) character of player 1, d) character of player 2, e) AR marker, f) GUI buttons, g) AR arena


Arne Bernin
email: arne.bernin@haw-hamburg.de

A Framework Concept for Emotion Enriched Interfaces

The work presented outlines my doctoral research in emotion and action based human computer interfaces, with the approach to create an open source framework. The idea is to find the suitable abstractions and interfaces to integrate different approaches to process input data to interpret user's emotions and actions. Fusing and comparing alternatives for processing will help to find the appropriate solution for a particular need for the next generation of interactive systems. Widening the sensing abilities of computers has the potential to add new degrees of freedom to the design of human computer interaction and ubiquitous entertainment computing.

Introduction

The level of interaction of today's computing systems lack various aspects that can be found in human-human communication. One major difference lies in ability to communicate on an emotional level. Combining emotions and actions shows great potential for new applications by leveraging of humanlike communication skills. This is particular relevant for communication centric applications such as gaming and learning. There are two fundamental designs to realize emotions in interactive Systems: 1. observing systems facilitate an emotional monologue i.e. provide no feedback. 2. Reactive systems have sensing and displaying abilities leading to an emotional dialog. The dialog may be facilitated by a combination of one or more modalities. Humans combine a variety of modalities as input channels for emotion recognition including gesture, posture, and prosody of speech, semantic, context and facial expressions.

Combining different data sources is also a common approach in computer science. Although there were some experiments in the field of combined channels for emotion recognition in computer science, the decision, which aggregation of modalities are more effective, is still an open research question. This decision also depends on the application and needs to be determined on the basis of a particular application scenario.

Currently there are many approaches in emotion interpretation and comparisons are rarely performed. Therefore, integrating established algorithms in a common framework enables to compare application specific differences and find opportunities for further research.

Framework

Current developments in entertainment computing go beyond the classic desktop scenario with one user in front of a display. Computer interaction has become ubiquitous. Therefore, the research scenarios should be developed in a ubiquitous context and laboratories, which we aim for in the livingplace hamburg, a smart home lab at the HAW Hamburg. [START_REF] Luck | Living place hamburga place for concepts of it based modern living[END_REF] The proposed framework enables to integrate different approaches in soft-and hardware and adds the ability to evaluate them on a scientific level. The requirements for the framework are:

1. Capability to log and replay all input data is needed for validation of an approach as well as comparison of different approaches with the same input data. Therefore, the complete data has to be written to data storage. 2. Processing of input data need to be performed at interactive rates. For this and to avoid bias due to fluctuating latencies, the framework has to be realtime orientated. 3. Concurrent processing of different modalities. The Framework needs the capacity to handle multiple input channels at the same time without fatal increase of processing time. 4. Facilities to analyze results for validation and comparison. In addition to logging of the input data, metrics of the system state, latencies, processing times and detection rate need to be saved for further analysis. 5. Easy exchange and integration of different processing components. This includes the requirements for an interface that works on different operating systems. Adapters for different programming languages are needed for flexibility.

Figure 1: process flow

The flow model of processing is shown in Figure 1. The different components are:

Emotion: Sense describes the different input modalities as sensor input for different channels. Sense is gathered by observing the user with different technical systems. The user does not need to consciously act for expressing the sensed information as his current emotional state might be subconscious to him.

Action: Actions are performed by the user such as input to operate a game. Actions are actively and conscious expressions done by the user as part of his planned interaction.

Input: Input is an abstraction of Emotion and Action. Incoming data needs to be normalized for further processing. Input is also the step, where the data is first completely visible to the framework, so here is the place to log it.

Process: Input data needs to be filtered and processed. The aggregated Information is then used to update the emotional model.

Log/Replay: Capability to store all input data in a database for future evaluation.

Model: Emotional Model on Computational level. This model represents the current emotional state of the user as recognized by the system. It can also be used to validate state changes and avoid fluctuations caused by misattributed input data.

Display: Output modality. Appropriate Display is task for future research. The current interface for the livingplace as testing environment at the HAW is the central message broker.

Applications in Gaming

Sensing emotions opens a variety of applications for interactive systems. For my thesis work, i plan to evaluate my proposed framework in gaming scenarios. I envision two possible application domains in entertainment computing.

Serious Games

Serious games are used for learning. By Gamification of the learning context or by developing skills inside the game that also have a benefit in the real world. Emotion recognition has two major applications in the context of serious games: Feedback to the machine and feedback to the user. Feedback to the machine on an emotional level can be used to control the learning curve. Changing speed and level of presented facts in an automated learning system according to the speed of understanding can improve the efficiency of the learning process. [START_REF] Mello | AutoTutor detects and responds to learners affective and cognitive states[END_REF] Provoking emotions can improve the user's motivation and memorization ability. Emotion recognition can be applied to verify the wanted effect. Further, emotional feedback to the user can improve can improve learning for public speaking and presentation skills.

Fun and Entertainment Games

There is an ongoing evolution in game controls from buttons and joysticks evolved to gestural input. In the future facial expressions and emotional state promise further enhancements. Expressed emotions can be transferred to avatar expression in game context. Like in serious games, Emotions can be applied to adapt the level of the game to user abilities and preferences. Current games use AI technologies, adding emotions have the potential to make them more believable. [START_REF] Becker-Asano | WASABI: Affect Simulation for Agents with Believable Interactivity[END_REF] Although, currently unknown, using emotion recognition technologies could increase immersion and embodiment on the user side.

Contribution to Entertainment Computing

The main purpose for the planned framework is to evaluate different approaches of sensing emotions and corresponding models for research. Nevertheless, the framework and exemplary procedure can be applied to integrate emotional sensing and to design into entertainment computing and games. Our complete prototype system can be directly integrated in game engines as additional source of input.

Current and Future Work

The main focus of the current work is to develop the basics of the framework. Therefore, methods and technical components evaluation for realtime messaging systems, facial expressions and prosody of speech is in process, the procedure for framework development has been derived from this evaluations. Examples can be presented at the doctorial consortium. Suitable datasets for evaluation selected as well. Future work includes the integration of a system for multi camera based determination of position and recognition of persons, currently developed at the HAW Hamburg. Integrating the results from the research done on terms of emotional surfaces at the HAW Hamburg are also part of future work. [START_REF] Müller | Emotional interaction with surfacesworks of design and computing[END_REF]


Ian Dunwell
email: i.dunwell@cad.coventry.ac.uk

Conducting ethical research with a game-based intervention for groups at risk of social exclusion

With developers of entertainment games increasingly exploiting the potential the platform affords for capturing rich data on user behaviour, adopting similar paradigms for "serious" purposes such as positive social change or public health intervention is a tempting prospect. However, exploitation of this potential must be tempered by a careful consideration of how ethical principles can be adhered to and applied to foster and sustain trust amongst end-users. This is particularly the case for at-risk groups, who may be particularly vulnerable to misunderstanding or misinterpreting requests to participate in research activities. In this paper, several key areas in which serious games present unique ethical considerations are presented and discussed: the unique nature of play as a source of data for analysis, the motivating role of the game and its use as an incentive for participation, and the impact of the entertainment gaming industry and its conventions user expectations. A case is presented based on preliminary work in developing a serious game for European migrants, and a number of key areas for consideration described. Through discussion of the emergence of methods and techniques for the analysis of data arising through play, the technological urgency for development of mechanisms to support ethical capture and processing of data from game-based learning environments is noted. To conclude the paper, future ethical dilemmas brought by success in achieving technological platforms capable of stimulating and managing behavioural changes are discussed.

Introduction

Entertainment games, and their serious counterparts, have attracted a wide range of attention from various sectors of the research community. With a little over a quarter of 13,000 Europeans surveyed in 2010 agreeing they considered themselves "gamers" [START_REF] Isfe | Video Gamers in Europe[END_REF], the pervasiveness and widespread appeal of this emerging medium is apparent. Attempts to demonstrate the impact and value of these serious outcomes often seek to utilize data captured from interactions between user and game, however, as an emergent medium, how users perceive and trust games requires careful consideration to ensure both an ethical and methodologically-sound approach to research. Since the early 1990s, the potential negative impact of emerging technology on exclusion through a "digital divide" has been well documented [START_REF] Norris | Digital Divide: Civic Engagement, Information Poverty, and the Internet Worldwide[END_REF]. However, as technology has matured and become increasingly pervasive, interventions seeking to harness this same technology to promote inclusion and empower groups at-risk of social exclusion have equally been observed to emerge [START_REF] Adams | Social empowerment and exclusion: A case study on digital libraries[END_REF][START_REF] David | The politics of communication: information technology, local knowledge and social exclusion[END_REF][START_REF] Ureta | Mobilising Poverty?: Mobile Phone Use and Everyday Spatial Mobility Among Low-Income Families in Santiago, Chile[END_REF]. In this article, we refer to "at-risk" groups specifically in terms of their risk of social exclusion; itself a concept lacking a ubiquitous definition, though broadly described as a state in which individuals fail to contribute economically, socially, and politically to the society in which they live [START_REF] Glenister | Discourse, social exclusion and empowerment[END_REF]. In Section 2, this paper presents from a pragmatic perspective a number of ethical considerations specific to serious games intended for these at-risk groups, reflecting on the unique case of game-based interventions, leading to discussion of both the need for trust, and routes towards obtaining it. Section 3 then reflects upon these considerations in light of the European Mobile Assistance for Social Inclusion and Empowerment of Immigrants with Persuasive Learning Technologies and Social Network Services (MASELTOV). The paper concludes by considering the broader ethical questions that must be confronted in the drive to create effective game-based methods for social, societal, and behavioural change.

Fostering trust in at-risk groups through an ethical approach

The challenges posed in ethically assessing the impact of technology with at-risk groups have been explored in general terms in a wide range of frameworks [START_REF] Wright | A framework for the ethical impact assessment of information technology[END_REF]. What, then, makes serious games worthy of special consideration? Interesting is the ease with which games are labeled as either "serious" or "entertainment" when few other media are defined in such absolute terms (consider, for example, the notion of "serious television"). Yet does this distinction extend to the end-user? It is not uncommon for serious games to adopt a stealthy approach to their learning objectives [START_REF] Davis | Liemandt Foundation launches hidden agenda contest: university students vie for a $25,000 prize by building video games that secretly teach middle school subjects[END_REF], and in doing so particular care must be taken in ensuring fundamental ethical processes such as informed consent are adhered to. However, the issue here is selfevident: if the user is informed of the objectives of the game, the pedagogical method is compromised, and a study of users in a naturalistic context becomes impossible. The lack of immediate solutions to this problem is no doubt a contributory factor to the paucity of conclusive, generalizable and objective studies showing the impact of game-based learning in a natural usage context. Whilst a range of studies have demonstrated the situational benefits of such approaches [START_REF] Knight | Serious gaming technology in major incident triage training: a pragmatic controlled trial[END_REF][START_REF] Kato | A Video Game Improves Behavioral Outcomes in Adolescents and Young Adults With Cancer: A Randomized Trial[END_REF][START_REF] Rebolledo-Mendez | Societal impact of a serious game on raising public awareness: the case of FloodSim[END_REF], a need still exists for a fuller understanding of how the indirect nature of learning through play is best selected and applied to meet a given learning requirement.

The depth of interaction, and possibility games afford for increased connection and emotional investment from users [START_REF] Dormann | Understanding game design for affective learning[END_REF] can be argued as one of the primary mechanisms through which they sustain engagement and foster intrinsic motivation to play [START_REF] Tychsen | Motivations for play in computer role-playing games[END_REF]. In the case where the rationale behind the selection of a game-based approach stems from its perceived ability to reach at-risk groups outside of formal or structured contact, adhering to ethical principles can be particularly challenging when seeking to compete for screen-time in a leisure context. Commercial games such as Farmville achieve success by adapting to the user [START_REF] Cikic | What FarmVille can teach us about cooperative workflows and architectures[END_REF], based on data capture methods that have been argued as unethical [START_REF] Zimmer | But the data is already public": on the ethics of research in Facebook[END_REF]. We may seek to implement our ethical approach, yet can we reasonably expect to attract users when we actively obstruct their access to ensure they are informed? Similarly, without the ability to customize and adapt our games without the express consent of the user, we should expect to provide an inferior service to those users who opt-out. If we allow users to opt-out of research activity, what incentive do we offer for them to participate, and if none, can we reasonably expect sufficient participants to ascertain whether our serious game achieves serious impact? Shifting context to a classroom, trial, or other environment where extrinsic motivation can be relied upon is an obvious solution, though if this is unrepresentative of the actual usage context, findings may be of limited value.

Fostering trust is therefore essential in guiding the decisions of participants to allow researchers access to their data, as well as allowing serious games to exploit the adaptive and iterative approaches shown to improve their efficacy [START_REF] Kam | Designing e-learning games for rural children in India: a format for balancing learning with fun[END_REF]. In entertainment gaming, and more generally software development, an End User Licensing Agreement (EULA) commonly accompanies the process for installation and first access. Increasingly, these agreements include consent to have data analyzed and kept for marketing purposes. A study of 80,000 users found that 50% of users took less than 8 seconds to read the agreement. Such was the extent of overfamiliarity with the EULA process, users were observed to be more inclined to blindly accept terms if the presented screen resembled an EULA [START_REF] Böhme | Trained to accept?: a field experiment on consent dialogs[END_REF]. In short, the majority of users have become accustomed to accepting these agreements without review; an unsurprising finding when considering that, in terms of perceivable impact on the user, the EULA is hard to recognize as more consequential than any other confirmation dialogue during an installation or startup process. Yet does this lack of attention from the user stem from a lack of understanding of what they are consenting to, or is it that these users understand the implications of a standard EULA and are happy to consent? Even presented with research addressing this question, it would be unlikely to apply to broader or generalized usage contexts.

An EULA is typically deployed with provision of service as an incentive: users unwilling to consent cannot typically access the software or game, therefore should we also consider the ethical implications of using a serious game as a vehicle to incentivize consent? For any intervention with intrinsic appeal, particular attention needs to be paid to the impact incentivisation may have on decisions to opt-out. A participant eager to play the game may not be a willing test subject; yet they may be willing to disregard this concern to gain continued access to the game. The extent to which this effect needs to be considered and planned for does, as with any other intervention, depend highly on the ability to ensure the participant makes the decision to participate in an informed manner, with the capacity to play the game whilst opting-out of the associated research activity. Thus, care should be taken when conducting research alongside users who are intrinsically motivated to play the game, but not necessarily to participate within the research programme. The title of this section acknowledges that an ethical approach is central in developing the trust required amongst end-users to perform effective evaluations. Important is not only the need to adopt an ethical approach, but how to communicate it effectively to the endusers without compromising the pedagogic or behavioural model at the core of the intervention's design. In the next section, we discuss how these principles might be applied in the specific case of a game-based intervention seeking to lower the risk of social exclusion amongst migrants entering the EU.

Game-based intervention for European migrants

We consider specifically in this section the case of a serious game currently being developed to support migrants entering the European Union (EU) from non-EU states as part of the MASELTOV project. The audience, therefore, is typified by the need to develop an understanding of the language and culture of the host country, as well as form social ties which lead to inclusion. In such a case, it is suggested games can form an effective basis for cultural learning through playful scenarios, and the gamification of existing resources. In this case the ethical approach builds upon the established principles of informed consent, though also notes the difficulties that can be posed in achieving this with an audience whose linguistic and cultural skill-set is defined by their country of origin rather than destination. Key, then, is to limit the requirements for these skills within the game, and to make the consent process highly transparent and accessible, as well as giving reference to the cultural context of the user. Technology is increasingly allowing data from users to be monitored and assessed. As the game developed for MASELTOV will be employed through a mobile device, technological methods for gaining consent for tools such as location awareness can be capitalized upon. However, again consideration must be afforded to the evidence given in the previous section, which suggests consent achieved through user agreements may not be fully informed. To address this, secondary mechanisms for ethical validation and information must be fully explored.

In addressing the general problem of social exclusion, the game must also be considered in its wider context as a single tool amongst a broader set of applications. The motivation games can stimulate, as outlined in the previous section, must be carefully considered with respect to its implications for how users might interact with the broader MASELTOV platform. A technological need to ensure users retain ownership of the data the system generates on their behaviour therefore emerges; a complex challenge when considering the interactions between multiple applications as well as the social context of the platform. Work within the MASELTOV project will therefore explore the role the game can play as both a conveyor of content and stimulus of intrinsic motivation, and central to this work will be an understanding of how trust can be sustained through a transparent, accessible, and integrated approach to data capture.

Conclusions

This paper has focused primarily on the pragmatic aspects of implementing a game-based solution or intervention to a problem. Indeed, serious games are commonly put forth as a medium with high potential as a means of behavioural change in a public audience. Many games already exist seeking to shift behaviour to certain ends; for example stimulating healthier eating [START_REF] Baranowski | Squire's Quest! Dietary outcome evaluation of a multimedia game[END_REF], treatment adherence [START_REF] Kato | A Video Game Improves Behavioral Outcomes in Adolescents and Young Adults With Cancer: A Randomized Trial[END_REF], and behavioural science frequently underpins their design [START_REF] Thompson | Serious Video Games for Health How Behavioral Science Guided the Development of a Serious Video Game[END_REF]. Taking the general goal of these approaches to be games capable of changing behaviour to any stated set of parameters, and ethical questions immediately emerge, particularly when one of the largest scale serious games to-date has functioned as a military recruiting tool [START_REF] Zyda | The MOVES institute's America's army operations game[END_REF].

More to the point, can, or should, we expect users to "trust" interventions which seek to covertly, or even insidiously, change their behaviour? Whilst games are by no means the sole technology for which these concerns must be raised, they are, based upon the above cited examples, one of the most powerful.

A future where these approaches are effective enough to require these questions to be answered fully is perhaps not as far away as we might like to think. Approaches to understanding "big data" [START_REF] Cuzzocrea | Analytics over large-scale multidimensional data: the big data revolution![END_REF] are increasingly allowing us to interpret meaning and models from complex systems and behaviours. Significant future investiture will undoubtedly enable research that explores how these techniques to be applied to iterate and adjust these complex systems to our own ends. Yet in the context of platforms for social, societal, or behavioural change, the ethical dilemmas these systems may raise cannot be understated. In fact, there can be little doubt that an information-driven approach capable of adjusting societies and behaviours on a largescale is no less of an ethical conundrum, or, indeed, as potentially devastating, as Oppenheimer's bomb. We might, as well-meaning researchers, seek to shift behaviour for short term public health gain, such as promotion of healthier lifestyles, but we cannot truly understand the "butterfly effect" our actions might stimulate. Though digital technologies and other emerging media only constitute individual parts of the complex structures underlying changes in behaviour, it is important to be mindful of this wider picture. In doing so, we must ask ourselves not only how we achieve our goals of change, but how we can expect to understand fully their consequences.

Acknowledgements

This work has been supported by the European Commission under the Collaborative Project MASELTOV ("Mobile Assistance for Social Inclusion and Empowerment of Immigrants with Persuasive Learning Technologies and Social Network Services") funded by the European Commission under the eInclusion theme, project FP7-ICT-7 Grant agreement n. 288587.


Michael Nitsche
email: michael.nitsche@gatech.edu

Sanjeev Nayak
email: snayak8@gatech.edu

Cell Phone Puppets: Turning Mobile Phones into Performing Objects

Keywords: Puppet, tangible user interface, virtual character

We introduce Puppettime, a digital puppetry project that uses mobile phones as interfaces to control virtual puppetry via motion gestures. The goal of the project is to explore cell phones as performative objects in novel interaction designs. Combining the evolution of mobile devices into tangible interfaces with traditional puppetry, the paper discusses the connections between these domains. It describes the design rationale behind the Puppettime project as well as its implementation and first feedback, focusing on the core thesis that puppetry provides a valuable and underused metaphor for interface design that supports digital entertainment between co-present players.

Introduction

The potential of gestures as intuitive input feature was recognized early on [START_REF] Wexelblat | Research Challenges in Gesture: Open Issues and Unsolved Problems[END_REF] but only the recent inclusion of advanced sensors in smart phones has made motion gesture recognition available to the larger audience of phone users. The inclusion of numerous sensors to smart phones allowed them to evolve into tangible controllers (as defined by [START_REF] Ullmer | Emerging frameworks for tangible user interfaces[END_REF]). But even though today's devices are stacked with accelerometers, compass, gyro, touch screens, and camera(s), all of them valuable features to support tangible interaction, the dominant interaction design for cell phones remains focused on the use of screens, buttons, microphones, and speakers.

The potential of mobile devices clearly encourages increased motion-based interaction but it remains woefully underused. The problem is not one of technology but one of design metaphors. We argue that in order to embrace the new opportunities a fundamental change of our understanding of mobile phones as media devices is needed. Through motion-based design, cell phones turn from audio-visual media devices into performing objects. They evolve from input/ output devices to objects, whose physical condition becomes prevalent not only to the player but every bystander. Designing for this form of mobile play cannot exclusively rely on audiovisual representation rendered by the phone, but it has to include the object itself in the design. This mirrors main arguments of earlier research on embodiment and situatedness of ubiquitous interaction [START_REF] Dourish | What we talk about when we talk about context[END_REF]. Within the larger field, the goal of this paper is to address particularly the recognition of the device itself as performing object and explore the opening design space through an example project.

Parallel to our past work with digital puppetry [START_REF] Mazalek | I'm in the Game: Embodied Puppet Interface Improves Avatar Control[END_REF] we have developed Puppettime, a prototype for a cell phone based digital puppetry system. It addresses a number of prevalent questions in the development of mobile interaction design for co-located digital entertainment, including design for multiple devices and for multi-user conditions, as well as testing of the underlying technology for fine grain control mechanisms. In this paper we will present the background, design, implementation, and some initial responses to the system.

Background

Mobile Phones and Tangible Interaction Design

A number of innovative projects have started to use phones as tangible objects in themselves. Phones have been used as controllers for Wii-like interaction with large screens [START_REF] Vajk | Using a Mobile Phone as a "Wii-like" Controller for Playing Games on a Large Public Display[END_REF], as well as controllers for 3D mobile games [START_REF] Chehimi | Motion controlled mobile 3D multiplayer gaming[END_REF], co-located social games based on motion gestures [START_REF] Fan | Surprise Grabber: a colocated tangible social game using phone hand gesture[END_REF], and multi-modal approaches that combine touch and motion [START_REF] Hinckley | Sensor synaesthesia: touch in motion, and motion in touch[END_REF]. First frameworks for the design of tangible interaction with phones are emerging [START_REF] Edge | Bimanual tangible interaction with mobile phones[END_REF] but the question remains how the interaction design and user experience will change as interactions with phones evolve further into a shared, movement-based, and co-located user experience. Does the design follow generic tasks, such as text input supported by accelerometers [START_REF] Jones | GesText: Accelerometer-Based Gestural Text-Entry Systems[END_REF] or develop particularly phone-related gestures, like the DoubleFlip [START_REF] Ruiz | DoubleFlip: A Motion Gesture Delimiter for Mobile Interaction[END_REF]?

This mirrors the challenge seen earlier in the transition of other interfaces to increasingly motion-based interaction design, particularly the focus on motion gestures in game consoles (Microsoft's Kinect, Sony's Move, Nintendo's Wii). Video games have discovered the social space in front of the console and designed particular interaction conditions for this space. But a key difference between gaming and general mobile phone usage is the different social context for gesture based interaction [START_REF] Rico | Usable Gestures for Mobile Interfaces: Evaluating Social Acceptability[END_REF].

Motion gestures are performative. Unlike a screen-based gesture system, a motion input is clearly visible to others and constitutes an expressive action in itself. The Kinect transforms the living room into a performance stage for gaming and Sall/ Grinter have found that "physical gaming often brought an awareness of other householders" [START_REF] Sall | Let's Get Physical! In, Out and Around the Gaming Circle of Physical Gaming at Home[END_REF]. Likewise, motion gestures for mobile devices add a performative element to the interaction. Instead of a hidden input, as seen with keyboards or touch screens, bystanders are able to read and interpret the gestures. But because the surroundings and bystanders are often less familiar in the public use of smart phones, the resulting awareness of others is not always wanted. Technically, we might be able to use our smart phones like Wii controllers, but conceptually we have to revisit the motion gestures when we apply them to public use. How, then, can we develop performative gestures for innovative cell phone interaction design?

Value of Puppetry

To address this question we turned to puppetry. Puppetry presents a highly developed form of expressive interaction and over the course of its 4000-year old history it has developed rich and culturally complex performative practices [START_REF] Blumenthal | Puppetry: A World History[END_REF]. It depends on motion gestures -what we would call "input" -to control a wide range of expressions. Thanks to its long tradition of outstanding artistry, the granularity and efficiency of this "input" is remarkably higher in traditional puppetry than it is in most current digital technology. The most delicate movement can have the power to evoke highly effective expressions in traditional puppetry formats. Thus, it provides a valid testing goal post for new interface technology and builds on a critical overlap between entertainment technology as a form of creative expression.

Puppetry has been identified as a metaphor for interaction with digital worlds before. For example, it has been claimed that puppetry supports storytelling, improvisation, and public engagement in digital media [START_REF] Bottoni | CoPuppet: Collaborative Interaction in Virtual Puppetry In[END_REF]. The relationship between puppeteer and puppet is used to describe the relationship between user and avatar, starting in early HCI concepts [START_REF] Walser | Elements of a Cyberspace Playhouse[END_REF], to more current educational projects [START_REF] Marshall | PUPPET: Playing and Learning in a Virtual World[END_REF], and tangible interfaces [START_REF] Mayora | iTheater Puppets Tangible Interactions for Storytelling[END_REF]. At the same time, traditional puppetry has started to explore and theorize its relation to the digital, gradually building frameworks to include it better [START_REF] Tillis | The Art of Puppetry in the Age of Media Production[END_REF].

In commercial entertainment, digital puppetry is at work in a range of projects such as Disney's Turtle Talk with Crush exhibit at their Epcot theme park or the Henson studio's puppeteering set up for the TV show Sid, the Science Kid [START_REF] Eide | Digital Puppetry[END_REF]. The problem is that these installations and other related work, like ShadowStory [START_REF] Lu | ShadowStory: Creative and Collaborative Digital Storytelling Inspired by Cultural Heritage[END_REF] use custom-built hardware controllers or expensive high-end commercial controllers [START_REF] Kim | Haptic Puppetry for Interactive Games[END_REF]. This limits their accessibility to consumers and instead focuses on expert users. These high end installations do not allow visiting players to easily turn into puppeteers or set up their own puppet shows but instead keep most visitors in the role of traditional audiences that can only contribute at a certain location and with the help of certain technology. Puppettime aims to explore and open up the performative range of digital puppetry to these large groups, test how well modern phones can deliver on the fine granularity of puppet controls, and provide the basis for a discussion of new design concepts for phones as performing objects in mobile entertainment. To do so, it set out to provide a simple, and highly accessible mobile-phone-based puppet interaction system.

Puppettime

Designing a Puppet Interface for Mobile Phones

Puppettime is a digital puppetry project that uses multiple mobile phones as objects to control puppet performances on a projected 3D virtual stage. It is multiplayer, allowing different players to join at any time and participate locally in a shared performance. Once the players have logged on to the central virtual stage, each one can customize their puppets on the mobile devices before they launch them into the performance. During such a performance, each player can either control their puppet with a single device -much like a simple rod puppet -or with two devices that allow for more detailed animation control of body and a puppet limbs. The core principle is to use mobile devices as performative objects much like puppeteers use rods or strings. Puppets are controlled by spatial movement of the devices and players can directly engage with the virtual performance on stage "through" the device and not "on" the device. The goal was to direct attention away from the phone as a traditional focal point of the interaction and toward the performance of the puppets and their puppeteers themselves. Because the interaction is spatial and shared, players realize that they are collaborating with other players during the puppet play. Their collaboration happens not only on the virtual stage but also in the shared physical location. Other players are not hidden behind some interface but their physical behavior -how they move their hands to control the puppet -is obvious and the co-located collaboration spreads between virtual stage and physical control space.

Implementation

Puppettime functions across two platforms. Android smart phones are utilized as tangible motion controllers, and a laptop running Unity3d serves as a display device that receives the phone input and renders the virtual puppet show. The Android phones communicate with the Unity application over a local Wi-Fi network.

The Unity application serves as a digital counterpart to the physical stage. A 3D stage environment is rendered in real-time, giving a backdrop for the virtual puppet performance. A set stage, complete with props, lighting, and curtains gives the digital puppets a place to act our their stories. Unity's built in physics engine adds a sense of realism to the environment as puppets collide with stage geometry, as they would in the real world. Using a cloth simulator, the curtain geometry was made to flow realistically and could be manipulated by the puppet bodies as they moved through the cloth. The puppets themselves were built as rag dolls with their bodies anchored to an invisible rod. The puppets' arms, legs, and heads, were free to move, bounce, and flail along with the simulated gravity depending on how the puppeteer directed the puppet's body. The basic physics simulation helped to help make a tangible connection between the real world mobile device and the digital puppet.

The Android application (Android 2.1 and higher) allows players to log on to the Unity application via the IP address of the host computer, enter a user name to identify their phone, and select between two control schemes: single and dual control (fig. 2 left). Once logged on, players can customize their virtual puppets from a given selection (fig. 2 right). We provided puppets for the classic fairytale setting of Little Red Riding Hood: a wolf, a hunter, a grandmother, and a puppet for Little Red Riding Hood. To support the aforementioned playful engagement and customization, Puppettime allows participants to create their own puppet versions from these basic figures. Players can select a certain body part, and then swipe over the screen to flip between different elements (head, chest, arms, legs) from varying puppets to form their own character. This interaction is not unlike using a children's playbook with split pages that can be turned independently to create new combinations of shapes. Once the player finishes the puppet assembly and activates the puppet, the phone turns into a tangible motion controller that allows the user to control their digital puppet in real-time. Motion data is gathered via the phone's accelerometer and magnetic sensors. The sensor data is turned into orientation values and is then sent via UDP packets over a local wireless network to the Unity application. The UDP protocol was chosen for its speed advantage over TCP. Fast reaction times are necessary to generate the impression of real-time control.

In the single phone scheme, the puppet's orientation will match the phone's orientation, and rotating the phone away from the vertical position will move the puppet in that direction (fig. 3). A quick vertical jerk makes the puppet jump. This is the most basic form of interaction with the system, and gives a similar style of control to that of a single rod puppet.

The dual phone control adds a second phone that controls either the arms or the head in addition to the main body. The secondary phone provides an interface to allow the user to select which additional limb to control: head, any single arm, or both arms (fig. 2 left). Rotations of this second phone will rotate whichever limb is selected. The access in this case is more complex, since the limbs are restricted to only rotate around a fixed joint, and the arms and head cannot match the orientation of the phone directly because they remain attached to the virtual avatar's main body. A challenge of digital technology is the lack of any direct connection to the controlled avatar. Puppeteers interact not only with the main control device but might operate individual strings on a marionette or even more directly, the expressions of a hand puppet with their own hand movements. The mapping applied in Puppettime's single rod control scheme is a direct translation of the phone's orientation onto the body of the virtual puppet. Players do not control a rod above or underneath the puppet but instead holds the puppet in their hands. This allows for a direct mapping of the phone as object to the virtual avatar as the virtual puppet.

All 3D objects were modeled in Maya and imported into Unity3d. Unity3d is a widespread platform for development of 3D applications and we used it here to code the stage for the puppet show. One laudable feature of Unity is its accessible multiplayer option. It allowed us to implement multiplayer performances relatively easily. The sessions are designed to be free form and users can log on and out as they please. They can also rebuild their puppets as they wish.

The virtual stage application also provides icons that control aspects of the performance that are not related to the puppets themselves, such as lights, sound, and the opening and closing of the curtains. These element control specific stage effects and can be activated on the laptop, which turns into a form of a digital stage manager.

Discussion

The project has been demonstrated at a number of occasions and different participants from minors to professional puppeteers have played with it. Users immediately understand the single phone mapping. They recognize their customized puppet on the stage and instantaneously map the phone as control device on the puppet's movements. The phone was readily accepted as a performing object and the responsiveness of the system was sufficient.

However, we also recognized emerging complex conditions that were initially not anticipated. Technically, the bi-manual control that allows players to control body and any selected limb with two phones at a time, works as smooth as the single phone control. However, it took players longer to adjust to the dual device control and to figure out how the rotations of the secondary phone affected the movements of the body parts. To improve performance, we limited the rotation range to avoid unnatural clipping. Still, operating the second phone in synch with the primary controller can be challenging for first time users. This corresponds with earlier work on bi-manual interaction, particularly when the actions of both hands are not mirrored but instead asymmetric and often more complex in their relation to each other. Guiard's model of the "kinematic chain" [START_REF] Guiard | Asymmetric Division of Labor in Human Skilled Bimanual Action: The Kinematic Chain as a Model[END_REF] indicates a higher level of gestural manipulation and expression through a hierarchical relationship between the hands' performances. This model has been discussed in interface design for entertainment technology but his concept of the non-dominant hand (usually left) to guide the general reference frame and the dominant hand to affect smaller scale effects within this frame changes in animation. Animation easily shifts the frame -e.g. from a full body movement to a detailed hand gesture -depending on the motion to be enacted. This challenge has already been noted by 2D puppetry approaches [START_REF] Kipp | Multitouch puppetry: creating coordinated 3D motion for an articulated arm[END_REF]. In our case, the asymmetric condition of one phone controlling the body and the other controlling a single limb allowed for a hierarchical and differently scaled interaction, as mentioned by Guiard, but players had to adjust to that condition, which itself was fixed once the devices were launched.

What this seems to call for is a bridging between different states of mapping. For example, one player commented that the initial positioning of the phones in relation to the virtual puppet is not intuitive. Because the virtual puppet remains frozen upright in the middle of the virtual stage until the phone controls are activated, recognizing the initial mapping before this launch is impossible. Consequently, the performing object of the phone did not match the representation on the virtual stage at the moment of activation. Control started with a kind of shock effect.

Another comment pointed to the device and its physical affordances. An expert puppeteer had no problems with the orientation of the devices but mentioned a lack of weight for the digital puppet. For example, the center of gravity is an important element in physical puppet controls and it is not developed in the current version of Puppettime. This mismatch distanced the virtual puppet from the expert puppeteer. He expected certain affordances that the hardware could not provide. One goal of the project was to test available cell phone hardware for the particular puppetry metaphor. Except for this expert statement, we encountered little to no problems with the role of the cell phone hardware itself. However, we added a "freeze in location" feature that allowed players to freeze the virtual puppet's position in space by pressing the touch screen of the phone. This allowed for a gradual exploration of the puppet's animation and the controls. While it is not possible to adjust the weight of the device to that of the virtual puppet, this kind of multimodal interaction design might offer a possible solution for more nuanced control.

Our system can track movement along two axes, which meant that we had to include limitations in the animation control on the 3D stage. All puppets perform on a 3D stage but their movements upward or downward are limited to jumping. It is worth noting, that only the expert puppeteer commented on this limitation and suggested changes to the puppet designs and not necessarily to the control schemes. No other player noticed this seemingly obvious restriction and commented on it negatively. This indicates a possibly useful restriction for future designs for mobile phones as performative objects and indicates that the consistency and simplicity of the mapping is more important than the sheer range of animation effects called by it.

Conclusion and Future Work

We propose that puppetry provides a useful metaphor to explore mobile phones as performing objects using motion gestures. But the here introduced example project, Puppettime, also highlights limitations of the technology and challenges for future design. The system currently uses accelerometers and magnetic sensors to generate motion data. Most recent phones also include gyroscopes, capable of providing better orientation data. As they become more commonly available in smart phones, Puppettime and other gesture-based input concepts might very well implement the here explored interaction methods in their design. This does not necessarily mean more gestural input but instead better-designed transitions between possible states during this input.

The current interaction design for Puppettime showed a number of friction points for such a design. These include the initial orientation of phones in relation to a virtual character and the bi-manual control scheme. The transformation of the mobile device from a traditional cell phone to a performative object seems to cross a threshold moment that needs to be clearly understood by the puppeteer/ player. Future design iterations should improve this transition to support the mental projection by the player and lead into a less rapid feeling of sudden control (or loss of control). Although mobile devices are turning increasingly into tangible objects with new interaction design, they are likely to keep some of their more traditional interface structures. Thus, these thresholds between different interaction paradigms will remain in the case of the mobile phone and lead to a kind of double identity.

Fig. 1 .

 1 Fig. 1. Stage application at work; lower menu presents stage director options; both puppets are controlled by players.

Fig. 2 .

 2 Fig. 2. Android app: selecting a control scheme (left) and puppet customization (right).

Fig. 3 .

 3 Fig. 3. Single phone control scheme; movements are directly projected onto the puppet body.

Acknowledgements. Puppettime was initially implemented by Sanjeev Nayak, Austin Denoble, and Vincent Zunga. We are thankful for in kind support by AT&T and assistance by Mark Guzdial.


Galina Jirásková
email: jiraskov@saske.sk

Benedek Nagy
email: nbenedek@inf.unideb.hu

On Union-Free and Deterministic Union-Free Languages

The paper continues the study of union-free and deterministic union-free languages. In contrast with the fact that every regular language can be described as a finite union of union-free languages, we show that the finite unions of deterministic union-free languages define a proper subfamily of regular languages. Then we examine the properties of this subfamily.

Introduction

The regular languages are the most common, well-known, and well-applicable languages. They are the simplest languages in the Chomsky-hierarchy, and can be represented by regular expressions or finite automata. Nowadays, some subfamilies of the regular languages have become important in various fields [START_REF] Dassow | Contextual Grammars with Subregular Choice[END_REF][START_REF] Dassow | Networks of Evolutionary Processors with Subregular Filters[END_REF][START_REF] Henning Bordihn | Determination of finite automata accepting subregular languages[END_REF]. One of them is the family of union-free languages: those languages described by regular expressions without the union operation.

Since the Parikh images of regular languages coincide with semi-linear sets, it is an interesting question if the Parikh images of languages in a subregular class still contain every semi-linear set. We address this question in Section 3, and show that only certain special semi-linear sets -the so-called conditional-linear sets -can be obtained by Parikh images of union-free languages.

The union-free languages are accepted by special nondeterministic finite automata, the so called one-cycle-free-path automata, in which there is exactly one cycle-free path from each state to the final state [START_REF] Nagy | Union-free regular languages and 1-cycle-free-path-automata[END_REF]. The deterministic versions of one-cycle-free-path automata are not as powerful, and define the class of deterministic union-free languages [START_REF] Jirásková | Complexity in union-free regular languages[END_REF].

One of the most important results on union-free languages states that every regular language can be expressed as a union of a finite number of union-free languages [START_REF] Nagy | A normal form for regular expressions[END_REF]. Moreover, the minimal number of required union-free languages is algorithmically computable [START_REF] Afonin | Minimal Union-Free Decompositions of Regular Languages[END_REF].

Motivated by these results, we address an analogous question for deterministic union-free languages, and provide a negative answer by describing a regular language which cannot be expressed as a union of a finite number of deterministic union-free languages. Our proof uses the representation of deterministic union-free languages by so-called balloon automata.

We also define the classes dU n as the classes of regular languages that can be described as a union of n deterministic union-free languages, and show that they define a proper hierarchy.

Finally, we consider the class dU * as the union of classes dU n , and conclude the paper with some closure properties.

Preliminaries

We assume that the reader is familiar with the basic concepts of formal languages and automata theory. For all unexplained notions, we refer the reader to [START_REF] Hopcroft | Introduction to Automata Theory, Languages and Computation[END_REF][START_REF] Yu | Chapter 2: Regular languages[END_REF].

For a finite non-empty set of symbols Σ, called an alphabet, Σ * denotes the set of all strings over Σ including the empty string ε. A language over Σ is any subset of Σ * . We denote the size of a finite set A by |A| and its powerset by 2 A .

A regular expression over an alphabet Σ is defined inductively as follows: ∅, ε, and a, for a in Σ, are regular expressions. If r and t are regular expressions, then also (r + t), (r • t), and (r) * are regular expressions. A regular expression is union-free if no symbol + occurs in it. A regular language is union-free if there exists a union-free regular expression describing the language.

A nondeterministic finite automaton (nfa) is a quintuple M = (Q, Σ, δ, s, F ), where Q is a finite set of states, Σ is an input alphabet, s is the initial state, F is the set of accepting states, and δ is the transition function that maps Q×(Σ∪{ε}) into 2 Q . The transition function is naturally extended to the domain Q × Σ * . The language accepted by nfa

M is L(M ) = {w ∈ Σ * | δ(s, w) ∩ F = ∅}.
Automaton M is deterministic (dfa) if it has no ε-transitions, and |δ(q, a)| ≤ 1 for all states q in Q and symbols a in Σ. Hence, we consider incomplete dfa's, in which some transitions may be undefined.

A path from state p to state q in an nfa/dfa M is a sequence p 0 a 1 p 1 a 2 • • • a n p n , where p 0 = p, p n = q, and p i ∈ δ(p i-1 , a i ) for i = 1, 2, . . . , n. The length of this path is n; note that p 0 is a path of length 0. The path is a cycle if n > 0 and p 0 = p n . The path is called a cycle-free accepting path if p n is an accepting state, and either the path is of length 0, or p i = p j whenever i = j. An nfa/dfa is a one-cycle-free-path (1cfp) nfa/dfa if there is a unique accepting cycle-free path from each of its states. It is known that the family of union-free languages coincides with the set of languages accepted by 1cfp nfa's [START_REF] Nagy | Union-free regular languages and 1-cycle-free-path-automata[END_REF]. The 1cfp dfa's define the family of deterministic union-free languages [START_REF] Jirásková | Complexity in union-free regular languages[END_REF].

The accepting path from the initial state of a 1cfp automaton defines the backbone of the automaton, and the string accepted by this path is called the backbone string. The backbone string is contained in each string of the accepted language in a scattered way, and therefore the shortest string is unique in every union-free language [START_REF] Nagy | Union-free regular languages and 1-cycle-free-path-automata[END_REF].

On Parikh Images of Union-Free Languages

The Parikh image of a string w over an ordered alphabet {a 1 , . . . , a k } is the vector Ψ (w) = (m 1 , . . . , m k ) of non-negative integers such that m i is the number of occurrences of a i in w. The Parikh image of a language L is the set of vectors

Ψ (L) = {Ψ (w) | w ∈ L}.
A set of the form

{α 0 + n 1 α 1 + • • • + n m α m | n j ≥ 0 for j = 1, 2, .
. . , m}, where α 0 , α 1 , . . . , α m are vectors of non-negative integers, is said to be a linear set. A semilinear set is a finite union of linear sets. It is well-known that the Parikh images of regular languages coincide with semilinear sets.

The aim of this section is to analyse the Parikh images of union-free languages. We show that the Parikh images of union-free languages are somewhere between linear and semilinear sets. Then we define the so-called conditionallinear sets, and prove that such sets coincide with the Parikh image of union-free languages.

Lemma 1. Every linear set is the Parikh image of a union-free language.

Proof. Let a linear set be given by the vectors α j for j = 0, 1, . . . , m. For each vector α j , consider a string w j with Parikh image α j . First, construct an nfa accepting the singleton set {w 0 }. Now, in the final state, add m disjoint cycles labelled by strings w j for j = 1, . . . , m. This results in a one-cycle-free-path nfa accepting a union-free language with desired Parikh image.

⊓ ⊔

We have seen that the set of Parikh images of union-free languages is a superset of linear sets, now we give 'upper and lower bounds': Lemma 2. There exists a union-free language whose Parikh image is not linear.

Proof. Consider the language given by the regular expression a(bb(aab) * ba) * a.

Its Parikh image is {(2, 0)+n(1, 3) | n ∈ N}∪{(3, 3)+m(1, 3)+k(2, 1) | m, k ∈ N}.
This set cannot be described by only one linear set. Moreover, this language is even deterministic union-free.

⊓ ⊔ Lemma 3. There exists a semilinear set W such that there is no union-free language L with Ψ (L) = W .

Proof. Consider the semilinear set W = {(3, 1), (4, 0)}. Every language with Parikh image W is finite and contains at least two shortest strings. ⊓ ⊔ Lemma 4. Let a language be accepted by a one-cycle-free-path nfa that consists of a backbone and several, up to starting state, disjoint cycles starting and ending in a state of the backbone; each cycle contains just one state of the backbone.

Then the Parikh image of the language is a linear set.

Proof. The Parikh image of the language is a linear set given by the Parikh vector of the backbone, and the Parikh vectors of the labels of all the cycles. ⊓ ⊔

The previous result can be stated as follows: The Parikh image of a unionfree language with star-height 1 is linear. Now we define conditional-linear sets and show that they coincide exactly with Parikh images of union-free languages. Definition 1. A set of vectors W is conditional-linear if every vector α is in W if and only if it can be written in the form

α = α 0 + δ 1 n 1 α 1 + δ 2 n 2 α i + • • • + δ m n m α m ,
where n j are non-negative integers and α j are fixed vectors of non-negative integers, and δ i are conditional coefficients defined in the following way: δ 1 = 1, and if i > 1, then δ i is either without any condition and equals 1, or depends on the coefficient of some α j with j < i, and in such a case it is equal to 1 if δ j n j > 0 and to 0 if δ j n j = 0:

δ i = 1,
if there is no condition for α i ,

δ i = 1, if δ j n j > 0, 0, if δ j n j = 0, if α i depends on the coefficient of α j .
Having δ i = 1 for all i without any conditions, the linear sets can be obtained. Thus conditional-linear sets are a kind of extension of linear sets. Moreover, all conditional linear sets are semilinear; however not every semilinear set is conditional linear. In a conditional-linear set some vectors α i have conditions, i.e., they can be present only if another vector with a smaller index is present.

Theorem 1. Conditional-linear sets coincide with the Parikh images of unionfree languages.

Proof. Let a union-free language be given by a regular expression

x 1 (r 1 ) * x 2 • • • x n (r n ) * x n+1 ,
where the parts x i are star-free; it is allowed that x i = ε for some i. Let α 0 be the Parikh vector of x 1 x 2 • • • x n+1 , that is, of the backbone string; these symbols are not under any Kleene-star in the tree for the expression. Next, let α i be the Parikh image of the string obtained from the child-subexpression r i by substituting ε for the parts under Kleene-star inside. These symbols are below exactly one Kleene-star in the tree. The obtained vectors α i are without conditions, because their mother expression is the original expression, so let

δ 1 = • • • = δ n = 1.
Now, for any subexpression r * which has not been considered yet, using the order of subexpressions as they are in the tree form of the regular expression starting from the top, let the next vector α i be the Parikh image of the symbols under this Kleene-star using ε for its child-subexpressions of the form p * . Let the conditional coefficient δ i depend on the coefficient of the vector α j where j is the index of the mother subexpression. Since the union-free expression contains finitely many stars this procedure terminates after finitely many steps.

Next, let a conditional-linear set W be given by its vectors and δ's. Construct a one-cycle-free-path nfa with Parikh image W as follows. Let A be the automaton accepting only a backbone string with Parikh vector α 0 . Consider every vector α i which is without condition, that is, δ i = 1 independently on any other values. Add a cycle labelled by a string with Parikh vector α i starting and ending at the same state of the backbone of A.

Then consider each other vector α i in order of increasing i. Let the condition for this vector depend on the coefficient of a vector α j . The cycle for vector α j is already included in the automaton, since j < i. Add new states to form a subcycle labelled by a string with Parikh vector α i in a state of the cycle for α j ; it always can be done by adding new states and ε-transitions to the cycle for α j . Finally, after adding subcycles for all the vectors, we get a one-cycle-free-path nfa that accepts a language with Parikh image W .

⊓ ⊔

Representation of Deterministic Union-Free Languages

Let us turn our attention to deterministic union-free languages defined as languages accepted by deterministic one-cycle-free-path dfa's [START_REF] Jirásková | Complexity in union-free regular languages[END_REF].

First we fix further terms used in the paper. A state p of a 1cfp automaton is a branching state if at least two transitions are defined from state p, thus if δ(p, a) = q 1 and δ(p, b) = q 2 , where q 1 , q 2 are states of the automaton and a, b are symbols in the input alphabet such that a = b. Since the automaton is a 1cfp automaton, we must have q 1 = q 2 . The accepting state is a branching state if there is at least one transition defined from it. If p is not the accepting state, then exactly one transition from p lies on the cycle-free accepting path from state p. All the other transition defined in state p start different cycles. All the transitions in the accepting state start new cycles.

Let a path paq contain a transition (p, a, q) starting a cycle. In the case p = q, the cycle has length 1. Otherwise, let us consider the cycle-free accepting path from state q. This path must contain state p, thus the path is of the form qz 1 pz 2 , where z 1 ∈ Σ(QΣ) * and z 2 ∈ (ΣQ) * . The cycle paqz 1 p is a starting cycle at state p. As an example, consider the cycles 4a6b4 and 4c2a3a4 that are starting cycles at state 4 in Fig. 2 (left).

Cycles may only start at branching states. The state where a cycle contains a previously (surely) visited state is the returning state of the cycle. A cycle may return to a previously (surely) visited state in various ways: A cycle may return at the same state as it starts like the cycle 4a6b4 in Fig. 2 (left), or a cycle may return to another state like the cycle 2b0a1a2 in Fig. 2; here state 0 is the returning state.

Since a one-cycle-free-path dfa over a unary alphabet cannot have a branching state, except the accepting state, the automaton may only have one cycle starting at the accepting state. Consequently, a deterministic union-free language over a unary alphabet either contains at most one string or is of the form a m (a n ) * for some positive integers m, n. The other direction also holds: All these languages are accepted by 1cfp dfa's. Therefore, the unary case seems to be not so interesting. In what follows, we always assume that an alphabet has at least two symbols.

There can be several one-cycle-free-path dfa's for the same language. One of them plays an important role for us. We call it a balloon automaton. This name comes from the toys made by clowns for children from long balloons; for example, toydog (see Fig. 1). Now we give the definition of a balloon automaton. We use balloon automata later to get regular expressions for deterministic union-free languages.

Definition 2 (Balloon DFA). A backbone 1cfp dfa, that is, a dfa consisting of states of the backbone connected through the symbols of the backbone string is a balloon dfa. If A is a balloon automaton, then any extension of A obtained in the following way is a balloon automaton:

pick a state p of A and a string a 1 • • • a k of length k with k ≥ 1 such that there is no transition on a 1 from p in A; -add k -1 new states p 1 , . . . , p k-1 to A connected through transitions

p a1 -→ p 1 a2 -→ p 2 a3 -→ • • • a k-1 -→ p k-1 a k -→ p.
Thus a deterministic one-cycle-free-path automaton is called a balloon dfa, if every starting cycle returns at the same (branching) state as it starts. Fig. 2 shows a one-cycle-free-path dfa and the corresponding balloon automaton.

The following result helps us to characterize deterministic union-free languages by regular expressions. Theorem 2. Every deterministic union-free language is accepted by a balloon dfa.

Proof. Let a deterministic union-free language L be given by a 1cfp dfa A. We are going to construct a regular expression and a balloon automaton for L in parallel from 1cfp dfa A. We use mixed-form expressions that contain symbols and names of the states of the automaton alternatively. We start with the expression r 0 = sx 1 q 1 x 2 • • • q m-1 x m f that contains the symbols of the backbone string x 1 x 2 • • • x m and the names of the states s, q 1 , . . . , q m-1 , f that occur on the backbone. All the states in expression r 0 are pairwise distinct.

As an example, consider the 1cfp dfa shown in Fig. 2. In this example, we have r 0 = 0a1a2a3a4b5.

The construction of the balloon automaton starts with the deterministic automaton A 0 that accepts only the backbone string: accordingly, it has states s ′ , q ′ 1 , . . . , q ′ m-1 , f ′ . We continue recursively while the automaton has branching states, that is, states that go to at least two distinct states by some symbols.

If the initial automaton A has no branching state, then it only accepts the backbone string, and it is a balloon automaton. Assume that our current expression is r i , and our current automaton is A i . Construct expression r i+1 by modifying expression r i as follows. Choose the last branching state p that has not been considered yet, that is, the branching state that has the last occurrence in the mixed form r i among the not yet considered mixed states. Put a pair of brackets into expression r i to the points immediately after each occurrence of p. Put a star after the brackets, that is, use the following form:

u 1 p() * u 2 • • • u m p() * u m+1 ,
where p has m occurrences in r i , and u j 's do not contain any p. Then put into these brackets as many sequences () * as many starting cycles exist at state p. After this, write into these brackets the mixed form expressions for the starting cycles using all the starting branches at state p without symbol p. The resulting expression is r i+1 . If only one cycle starts from a branching state, then the form ((z) * ) * can be simplified to (z) * , where z denotes the mixed form representing the cycle. In our example, we have

r 1 = 0a1a2a3a4((a6b) * (c2a3a) * ) * b5, r 2 = 0a1a2a3(c2a) * a4((a6b) * (c2a3(c2a) * a) * ) * b5, r 3 = 0a1a2(b0a1a) * a3(c2(b0a1a) * a) * a4((a6b) * (c2(b0a1a) * a3(c2(b0a1a) * a) * a) * ) * b5.
Notice that after each step, the number of occurrences of p remains m; and all the states which occur in, say, k cycles starting from p have km new occurrences. Moreover, since the automaton is a 1cfp dfa, there are no states appearing in the new brackets which have already been considered. Now construct automaton A i+1 corresponding to expression r i+1 by modifying automaton A i . Extend automaton A i by cycles corresponding to the new subexpressions (z) * ; the ones that are not in r i , but which are in r i+1 . For each of these new subexpressions, add a new cycle to every copy of state p ′ starting and ending in this state (in a similar way as we draw the backbone). In this step, we use various copies of the original states. Fig. 3 shows automata A i in our example.

Repeat the above procedure until no more branching states exist. Since there are only finitely many branching states in the given automaton, this procedure terminates after finitely many steps. Let r n be the resulting expression. After deleting the names of the states in r n , we get a union-free expression which describes language L. The resulting automaton A n accepts language L. Moreover, after each step, automaton A i is a balloon automaton.

⊓ ⊔

The proof of the previous theorem gives also a regular expression for every one-cycle-free-path dfa. By this construction, we can characterize the deterministic union-free languages by regular expressions as follows. Every deterministic union-free language can be expressed by a regular expression of the following form:

(i) there is at most 1 symbol that continues the expression "in the same level"; (ii) the other symbols may enter for brackets: if there is one such symbol, then

((b 1 • • • ) * (b 2 • • • ) * • • • (b ℓ • • • ) * ) * ).
On the other hand, every regular expression that satisfies (i) and (ii) describes a deterministic union-free language since a 1cfp dfa for such a language can be constructed by our proof. We conjecture that the balloon dfa has maximal number of states among all the incomplete dfa's that accept the language and for each of its state there is exactly one accepting cycle free path.

A rough idea for the proof of the conjecture could be the following: By the construction of the balloon automata for a 1cfp dfa, the number of its states is not smaller than the number of the states of the original automaton. Moreover, the balloon automaton cannot be extended further by states. Since it is deterministic, by adding a new state, some new transitions are needed. This modifies the backbone or a cycle, or creates a new cycle; thus modifies the accepted language.

One of the most important complexity measures of regular languages is the star height that is connected to the number of nested stars in the regular expressions [START_REF] Yu | Chapter 2: Regular languages[END_REF]. To measure the complexity of balloon automata, we define the following concept.

Definition 3 (Cycle Depth of Balloon Automata). The cycle depth of a balloon automaton is the maximal number of its nested cycles.

The cycle depth of a balloon automaton is 0 for cycle-free automata. For example, the depth of the automaton A 0 in Figure 3 is 0. Such automata only accept singleton languages. The cycle depth of A 1 , A 2 , A 3 is 1, 2 and 3, respectively.

The cycle depth of the balloon automata and the (nested) star-height of the obtained regular expressions have a strong relation: Actually, if expressions of the form ((r 1 ) * (r 2 ) * ) * are rewritten of the form (r 1 + r 2 ) * , then this new expression has the same star height as the cycle depth of the original balloon automaton.

A cycle pzp of a 1cfp dfa, where z ∈ Σ(QΣ) * , is called an inner cycle if there is no branching state in z. For example, the cycle 2b0a1a2 in Figure 2 is an inner cycle. In balloon automata, these cycles are at the deepest level. For example, the cycles of length 2 of A 2 in Figure 3 are inner cycles.

We have some important observations about graphs of 1cfp deterministic automata, in particular, we formulate them for balloon automata. Lemma 5. Let A = (Q, Σ, δ, s, f ) be a 1cfp dfa accepting a non-empty language. Then 1. The branching factor at each state of A is at most |Σ|. 2. If the cycle depth of a balloon automaton is zero, then there is a state, in which at most one symbol in Σ defines a transition; the transition on the other symbols are undefined. 3. If the cycle depth of a balloon automaton is at least one, and the length of the/an inner cycle is at least two, then there is a state where only one of the symbols defines a transition.

Proof. 1. In every state of a dfa, at most |Σ| transitions may be defined. 2. Balloon automata with cycle depth zero accept exactly one string, and all the transitions in the final state f are undefined.

3. If the cycle depth of a balloon automaton is one, then there is a cycle starting from a state on the backbone with, by our assumption, length at least two. This means that after the first transition of this cycle, there is a state that is outside of the backbone. In this inner state, exactly one transition is defined. Now assume that the cycle depth of a balloon automaton is at least two. The argument is quite similar to the previous case. In a balloon automaton, one transition could go to the direction of the final state; the first symbol of the unique cycle-free accepting path gives this transition. All the other symbols may start a new cycle going more deeply in the cycle depth of the automaton. Consider the/an inner cycle; its length is at least two by the assumption of the lemma. In this cycle, there is no new starting cycle. Therefore, in the/an inner state, there exists only one transition, which starts the cycle-free accepting path from that state.

⊓ ⊔

We conclude this section with the following result showing that the class of deterministic union-free languages is not closed under basic regular operations.

Theorem 3 (Closure properties). The class of deterministic union-free languages is not closed under boolean operations, concatenation, square, star, reversal, cyclic shift, homomorphism, and inverse morphism.

Proof. For each operation, we present deterministic union-free languages such that the language resulting from the operation is not deterministic union-free. Recall that if a language has at least two shortest strings, or if its minimal dfa has at least two final states, then the language is not deterministic union-free.

Complement:

{ε} c = Σ + , Union: {a} ∪ {b} = {a, b}, Intersection: b * ab * ∩ a * ba * ⊆ {ab, ba} ∪ {a, b} ≥3 Symmetric difference: {a} ⊕ {b} = {a, b}, Cyclic shift: Shift({ab}) = {ab, ba}, Shuffle: {a} {b} = {ab, ba}, Inverse morphism: h -1 ({aa}) = {aa, ab, ba, bb} h(a) = h(b) = a
For square and concatenation, consider the deterministic union-free language L 1 accepted by the 1cfp dfa shown in Fig. 4 (left). For reversal, consider the deterministic union-free language L 2 accepted by the 1cfp dfa shown in Fig. 4 (middle), and for star, the deterministic union-free language L 3 accepted by the 1cfp dfa shown in Fig. 4 (right). The minimal dfa's for L 2 1 , L R 2 , and L * 3 have two final states, and therefore the resulting languages are not deterministic unionfree. For homomorphisms, consider the deterministic union-free language ab * ac * and homomorphism h(a) = a, h(b) = ab, h(c) = c. Then h(ab * ac * ) = a(ab) * ac * , the minimal dfa for which has two final states.

⊓ ⊔

Finite Union of Deterministic Union-Free Languages

Every regular language can be expressed as the union of a finite number of union-free languages [START_REF] Nagy | A normal form for regular expressions[END_REF]. This is one of the most important results on union-free languages. We can ask whether or not a similar result also holds for deterministic union-free languages. The next theorem provides a negative answer, and states one of the main results of this paper.

Theorem 4. The language L described by the regular expression ((a+b)(a+b)) * cannot be expressed as a union of a finite number of deterministic union-free languages.

Proof. The language L contains exactly the strings over {a, b} of an even length. Therefore, each string over {a, b} is a prefix of infinitely many strings in L.

Assume for the contradiction that L is given as a finite union of some deterministic union-free languages. Let us consider the balloon automata for these languages. None of these automata has a cycle of length one because otherwise this loop would allow to pump some strings of the accepted language symbol by symbol which would lead to the acceptance of strings of an odd length. Now let us order all the balloon automata in a list A 1 , A 2 , . . . , A ℓ . By Lemma 5, each of these automata contains at least one state, in which at most one symbol defines a transition. Moreover, such a state is reachable from every state of a balloon automaton: If there is no cycle at the final state, then the final state is such a state. If there is a cycle starting at the final state, then there is an inner cycle here with at least one such state. And since this state is reachable from the final state, it can be reached from each state of the automaton. Let q i refer to such a state in automaton A i .

Let us construct a string w in the following way: Let the prefix of w be the string w 1 that leads to the state q 1 in automaton A 1 . Then let the next symbol of w be the one for which there is no transition from q 1 . Now let i = 2, and hence the next automaton in the list is considered. Let us continue the construction of w by appending w i to it, where w i is defined as follows. If the already constructed initial part of w cannot be processed by the automaton A i , then w i is the empty string. Elsewhere let q ′ i be the state reached by automaton A i after reading w. Then w i is the string that leads automaton A i from state q ′ i to state q i . The next symbol of w is the/a symbol, for which there is no transition from q i in A i . Then, we increase i and consider the next automaton in the list until all of them are considered.

Finally, we add one or two symbols to the end of w, depending on length of w; for example, we add a if the length of w is odd, and aa in the other case. The constructed string has an even length, and therefore it is in L. However, our construction proves that no automaton in our list accepts the constructed string, which is a contradiction to our assumption that L is expressed as the union of languages L(A i ). The theorem is proved.

⊓ ⊔

The proof also works for any language L that has the the following properties:

the minimal complete dfa for the language has no dead state, that is, each string w in Σ * is a prefix of a string in L; -L contains only strings of an even/odd length.

To conclude the paper, let us consider the finite unions of deterministic unionfree languages. Definition 4. For every positive integer n, we define dU n as the family of languages that can be expressed as a union of n deterministic union-free languages. Furthermore, let

dU * = ∞ i=1 dU i .
The following result shows that the classes dU n define a proper hierarchy.

Theorem 5. For every n, there exists a language L n such that L n ∈ dU n \ dU n-1 .

Proof. Let L n = {a i b n-i | i = 1, 2, . . . , n} be a language consisting of n strings over {a, b} of length n. Then L n is accepted by the union of n backbone automata. On the other hand, this language cannot be accepted by the union of any n -1 deterministic one-cycle-free-path automata because otherwise one of them would accept a language containing at least two shortest strings.

⊓ ⊔

Now we give some non-closure properties of the language classes dU n .

Theorem 6. The classes dU n are not closed under union, concatenation, square, cyclic shift. If n ≥ 4, then the class dU n is not closed under star.

Proof. For n = 1, that is, for the class of deterministic union-free languages, we have already proved these non-closure properties. Otherwise, consider the languages K = {b i | 1 ≤ i ≤ n} and L = {a i b | 1 ≤ i ≤ n} in dU n . The union of these languages, as well as their concatenation, is a finite language, however, it contains more than n strings. The square of the language L, as well as its cyclic shift, is a finite language containing more than n strings. The star of the language aa + ab + ba + bb is not in dU * by Theorem 4, and therefore the last statement of the theorem holds.

⊓ ⊔

The next theorem gives some closure properties of the class dU * .

Theorem 7. The class dU * is closed under union, and it is not closed under star, intersection, and complement.

Proof. For star, consider the language {ε, aa, ab, ba, bb} which is in dU 5 . After applying the star operation, we get the language ((a+ b)(a+ b)) * . By Theorem 4, this language is not in dU * . For intersection, consider the languages K = ((b * a) 2 ) * b * and L = ((a * b) 2 ) * a * , the first of which contains the strings with an even number of a's, while the second one consists of strings with an even number of b's. The proof of Theorem 4 works for the language K ∩ L as well since every string in {a, b} is a prefix of a string in K ∩ L, and K ∩ L contains only strings of an even length.

Hence the class dU * is not closed under complement because otherwise, since it is closed under union, it would be closed also under intersection.

⊓ ⊔

We leave as an open problem whether or not the class dU * is closed under other regular operations.

Conclusions

We examined in detail the classes of union-free and deterministic union-free languages. First we studied the Parikh images of union-free languages, and we proved that they coincide with so-called conditional-linear sets.

Then we defined balloon automata for deterministic union-free languages, and we used them to get regular expressions for deterministic union-free languages, as well as to prove one of the main results of our paper. This result shows that the finite unions of deterministic union-free languages describe a proper subfamily of regular languages. We also investigated the properties of classes represented as a finite union of deterministic union-free languages.

Some closure properties remain open. The characterization of the subregular language class containing the regular languages that cannot be expressed as a finite union of deterministic union-free languages is an interesting further task. Providing minimal 1cfp dfa for deterministic union-free languages, and proving/disproving our conjecture about the maximality of the balloon automata seem to be interesting challenges as well.

Fig. 1 .

 1 Fig. 1. A toydog from long balloon.

Fig. 2 .

 2 Fig. 2. A 1cfp dfa (up) and the corresponding balloon automaton (down).

Fig. 3 .

 3 Fig. 3. The construction of a balloon automaton.

  we use b: (b • • • ) * ; if there are two or more symbols, then we use b 1 , b 2 , . . . , b ℓ :

Fig. 4 .

 4 Fig. 4. The 1cfp dfa languages L1, L2, L3 such that L 2 1 , L R 2 , and L * 3 are not deterministic union-free.

⋆ Research supported by the Slovak Research and Development Agency under contract APVV-0035-10 "Algorithms, Automata, and Discrete Data Structures". ⋆⋆ Research supported by the T ÁMOP 4.2.1/B-09/1/KONV-2010-0007 project. The project is implemented through the New Hungary Development Plan, co-financed by the European Social Fund and the European Regional Development Fund.