The SIGCHI and Social Computing research communities have been at the forefront of online safety efforts for youth, ranging from understanding the serious risks youth face online to developing evidence-based interventions for risk protection. Yet, to bring these efforts to bear, we must partner with practitioners, such as industry stakeholders who know how to bring such technologies to market, and youth service providers who work directly with youth. Therefore, we interviewed 33 stakeholders in the space of youth online safety, including industry professionals (n=12), youth service providers (n=11), and researchers (n=10) to understand where their visions toward working together to protect youth online converged and surfaced tensions, as well as how we might reconcile conflicting viewpoints to move forward as one community with synergistic expertise on how to change the current sociotechnical landscape for youth online safety. Overall, we found that non-partisan leadership is necessary to chart actionable, equitable goals to facilitate collaboration between stakeholders, combat feelings of isolation, and foster trust between the stakeholder groups. Based on these findings, we recommend the use of open-innovation methods with their inherent transparency, federated governance models, and clear but inclusive leadership structures to promote collaboration between youth online safety stakeholders. We propose the creation of an open-innovation organization that unifies the diverse voices in youth online safety to develop open-standards and evidence-based design patterns that centralize otherwise fragmented efforts that have fallen short of the goal of effective technological solutions that keep youth safe online.

Mobile user profiling refers to the efforts of extracting users’ characteristics from mobile activities. In order to capture the dynamic varying of user characteristics for generating effective user profiling, we propose an imitation-based mobile user profiling framework. Considering the objective of teaching an autonomous agent to imitate user mobility based on the user's profile, the user profile is the most accurate when the agent can perfectly mimic the user behavior patterns. The profiling framework is formulated into a reinforcement learning task, where an agent is a next-visit planner, an action is a POI that a user will visit next, and the state of the environment is a fused representation of a user and spatial entities. An event in which a user visits a POI will construct a new state, which helps the agent predict users’ mobility more accurately. In the framework, we introduce a spatial Knowledge Graph (KG) to characterize the semantics of user visits over connected spatial entities. Additionally, we develop a mutual-updating strategy to quantify the state that evolves over time. Along these lines, we develop a reinforcement imitative graph learning framework for mobile user profiling. Finally, we conduct extensive experiments to demonstrate the superiority of our approach.

In many scenarios, 1) data streams are generated in real time; 2) labeled data are expensive and only limited labels are available in the beginning; 3) real-world data is not always i.i.d. and data drift over time gradually; 4) the storage of historical streams is limited. This learning setting limits the applicability and availability of many Machine Learning (ML) algorithms. We generalize the learning task under such setting as a semi-supervised drifted stream learning with short lookback problem (SDSL). SDSL imposes two under-addressed challenges on existing methods in semi-supervised learning and continuous learning: 1) robust pseudo-labeling under gradual shifts and 2) anti-forgetting adaptation with short lookback. To tackle these challenges, we propose a principled and generic generation-replay framework to solve SDSL. To achieve robust pseudo-labeling, we develop a novel pseudo-label classification model to leverage supervised knowledge of previously labeled data, unsupervised knowledge of new data, and, structure knowledge of invariant label semantics. To achieve adaptive anti-forgetting model replay, we propose to view the anti-forgetting adaptation task as a flat region search problem. We propose a novel minimax game-based replay objective function to solve the flat region search problem and develop an effective optimization solver. Experimental results demonstrate the effectiveness of the proposed method.

In this paper, we study the problem of mobile user profiling, which is a critical component for quantifying users' characteristics in the human mobility modeling pipeline. Human mobility is a sequential decision-making process dependent on the users' dynamic interests. With accurate user profiles, the predictive model can perfectly reproduce users' mobility trajectories. In the reverse direction, once the predictive model can imitate users' mobility patterns, the learned user profiles are also optimal. Such intuition motivates us to propose an imitation-based mobile user profiling framework by exploiting reinforcement learning, in which the agent is trained to precisely imitate users' mobility patterns for optimal user profiles. Specifically, the proposed framework includes two modules: (1) representation module, that produces state combining user profiles and spatio-temporal context in real-time; (2) imitation module, where Deep Q-network (DQN) imitates the user behavior (action) based on the state that is produced by the representation module. However, there are two challenges in running the framework effectively. First, epsilon-greedy strategy in DQN makes use of the exploration-exploitation trade-off by randomly pick actions with the epsilon probability. Such randomness feeds back to the representation module, causing the learned user profiles unstable. To solve the problem, we propose an adversarial training strategy to guarantee the robustness of the representation module. Second, the representation module updates users' profiles in an incremental manner, requiring integrating the temporal effects of user profiles. Inspired by Long-short Term Memory (LSTM), we introduce a gated mechanism to incorporate new and old user characteristics into the user profile. In the experiment, we evaluate our proposed framework on real-world datasets. The extensive experimental results validate the superiority of our method comparing to baseline algorithms.

360-degree experiences such as cinematic virtual reality and 360-degree videos are becoming increasingly popular. In most examples, viewers can freely explore the content by changing their orientation. However, in some cases, this increased freedom may lead to viewers missing important events within such experiences. Thus, a recent research thrust has focused on studying mechanisms for guiding viewers' attention while maintaining their sense of presence and fostering a positive user experience. One approach is the utilization of diegetic mechanisms, characterized by an internal consistency with respect to the narrative and the environment, for attention guidance. While such mechanisms are highly attractive, their uses and potential implementations are still not well understood. Additionally, acknowledging the user in 360-degree experiences has been linked to a higher sense of presence and connection. However, less is known when acknowledging behaviors are carried out by attention guiding mechanisms. To close these gaps, we conducted a within-subjects user study with five conditions of no guide and virtual arrows, birds, dogs, and dogs that acknowledge the user and the environment. Through our mixed-methods analysis, we found that the diegetic virtual animals resulted in a more positive user experience, all of which were at least as effective as the non-diegetic arrow in guiding users towards target events. The acknowledging dog received the most positive responses from our participants in terms of preference and user experience and significantly improved their sense of presence compared to the non-diegetic arrow. Lastly, three themes emerged from a qualitative analysis of our participants' feedback, indicating the importance of the guide's blending in, its acknowledging behavior, and participants' positive associations as the main factors for our participants' preferences.

Traditional parental control applications designed to protect children and teens from online risks do so through parental restrictions and privacy-invasive monitoring. We propose a new approach to adolescent online safety that aims to strike a balance between a teen's privacy and their online safety through active communication and fostering trust between parents and children. We designed and developed an Android "app" called Circle of Trust and conducted a mixed methods user study of 17 parent-child pairs to understand their perceptions about the app. Using a within-subjects experimental design, we found that parents and children significantly preferred our new app design over existing parental control apps in terms of perceived usefulness, ease of use, and behavioral intent to use. By applying a lens of Value Sensitive Design to our interview data, we uncovered that parents and children who valued privacy, trust, freedom, and balance of power preferred our app over traditional apps. However, those who valued transparency and control preferred the status quo. Overall, we found that our app was better suited for teens than for younger children.

Facial Expression Recognition (FER) is a challenging task because many factors of variation such as pose, illumination, and identity-specific attributes are entangled with the expression information in an expressive face image. Recent works show that the performance of a FER algorithm can be improved by disentangling the expression information from identity features. In this paper, we present Transfer-based Expression Recognition Generative Adversarial Network (TER-G AN) that combines the effectiveness of a novel feature disentanglement technique with the concept of identity-invariant expression representation learning for FER. More specifically, TER-GAN learns a disentangled expression representation by extracting expression features from one image and transferring the expression information to the identity of another image. To improve the feature disentanglement process and to learn an identity-invariant expression representation, we introduce a novel expression consistency loss and an identity consistency loss that exploit expression and identity information from both real and synthetic images. We evaluated the performance of our proposed facial expression recognition technique by employing four public facial expression databases, CK+, Oulu-CASIA, MMI, BU-3DFE. The experimental results show the effectiveness of the proposed technique.

Interactive training environments typically include feedback mechanisms designed to help trainees improve their performance through either guided or self-reflection. In this context, trainees are candidate teachers who need to hone their social skills as well as other pedagogical skills for their future classroom. We chose an avatar-mediated interactive virtual training system–TeachLivE–as the basic research environment to investigate the motions and embodiment of the trainees. Using tracking sensors, and customized improvements for existing gesture recognition utilities, we created a gesture database and employed it for the implementation of our real-time gesture recognition and feedback application. We also investigated multiple methods of feedback provision, including visual and haptics. The results from the conducted user studies and user evaluation surveys indicate the positive impact of the proposed feedback applications and informed body language. In this paper, we describe the context in which the utilities have been developed, the importance of recognizing nonverbal communication in the teaching context, the means of providing automated feedback associated with nonverbal messaging, and the preliminary studies developed to inform the research.

We present a study of the relative effects of gradual versus instantaneous transition between one's own body and a virtual surrogate body, and between one's real-world environment and a virtual environment. The approach uses a stereo camera attached to an HMD to provide the illusions of virtual body ownership and spatial presence in VR. We conducted the study in a static environment which is similar to the traditional rubber hand experiment platform. Since our transition method is a blending scheme between real and virtual contexts, our study investigates the direct use of real-world information during the transition to increase the dominant visual illusion in a virtual space. We also investigate the use of a conceptual stage, called Limbo, which is a transition phase that evokes anticipation of the virtual world, providing a psychological link between the real and virtual before we enter a totally virtual space. Our study of the transition effect shows that the Limbo state has a significant influence in one's illusions of virtual body ownership (VBOI) and presence.

A person's face discloses important information about their affective state. Although there has been extensive research on recognition of facial expressions, the performance of existing approaches is challenged by facial occlusions. Facial occlusions are often treated as noise and discarded in recognition of affective states. However, hand over face occlusions can provide additional information for recognition of some affective states such as curiosity, frustration and boredom. One of the reasons that this problem has not gained attention is the lack of naturalistic occluded faces that contain hand over face occlusions as well as other types of occlusions. Traditional approaches for obtaining affective data are time demanding and expensive, which limits researchers in affective computing to work on small datasets. This limitation affects the generalizability of models and deprives researchers from taking advantage of recent advances in deep learning that have shown great success in many fields but require large volumes of data. In this paper, we first introduce a novel framework for synthesizing naturalistic facial occlusions from an initial dataset of non-occluded faces and separate images of hands, reducing the costly process of data collection and annotation. We then propose a model for facial occlusion type recognition to differentiate between hand over face occlusions and other types of occlusions such as scarves, hair, glasses and objects. Finally, we present a model to localize hand over face occlusions and identify the occluded regions of the face.

Automatic emotion recognition plays a central role in the technologies underlying social robots, affect-sensitive human computer interaction design and affect-aware tutors. Although there has been a considerable amount of research on automatic emotion recognition in adults, emotion recognition in children has been understudied. This problem is more challenging as children tend to fidget and move around more than adults, leading to more self-occlusions and non-frontal head poses. Also, the lack of publicly available datasets for children with annotated emotion labels leads most researchers to focus on adults. In this paper, we introduce a newly collected multimodal emotion dataset of children between the ages of four and fourteen years old. The dataset contains 1102 audio-visual clips annotated for 17 different emotional states: six basic emotions, neutral, valence and nine complex emotions including curiosity, uncertainty and frustration. Our experiments compare unimodal and multimodal emotion recognition baseline models to enable future research on this topic. Finally, we present a detailed analysis of the most indicative behavioral cues for emotion recognition in children.

This poster describes the TeachLivE paradigm, its application to de-escalation training, especially for law enforcement personnel, and the realization of this in a four-walled augmented virtuality space. Emphasis is placed on how the resulting physical presence increases co-presence and social presence, leading to an immersive and effective learning environment.

Research in learning analytics and educational data mining has recently become prominent in the fields of computer science and education. Most scholars in the field emphasize student learning and student data analytics; however, it is also important to focus on teaching analytics and teacher preparation because of their key roles in student learning, especially in K-12 learning environments. Nonverbal communication strategies play an important role in successful interpersonal communication of teachers with their students. In order to assist novice or practicing teachers with exhibiting open and affirmative nonverbal cues in their classrooms, we have designed a multimodal teaching platform with provisions for online feedback. We used an interactive teaching rehearsal software, TeachLivE, as our basic research environment. TeachLivE employs a digital puppetry paradigm as its core technology. Individuals walk into this virtual environment and interact with virtual students displayed on a large screen. They can practice classroom management, pedagogy and content delivery skills with a teaching plan in the TeachLivE environment. We have designed an experiment to evaluate the impact of an online nonverbal feedback application. In this experiment, different types of multimodal data have been collected during two experimental settings. These data include talk-time and nonverbal behaviors of the virtual students, captured in log files; talk time and full body tracking data of the participant; and video recording of the virtual classroom with the participant. 34 student teachers participated in this 30-minute experiment. In each of the settings, the participants were provided with teaching plans from which they taught. All the participants took part in both of the experimental settings. In order to have a balanced experiment design, half of the participants received nonverbal online feedback in their first session and the other half received this feedback in the second session. A visual indication was used for feedback each time the participant exhibited a closed, defensive posture. Based on recorded full-body tracking data, we observed that only those who received feedback in their first session demonstrated a significant number of open postures in the session containing no feedback. However, the post-questionnaire information indicated that all participants were more mindful of their body postures while teaching after they had participated in the study.

As part of normal interpersonal communication, people send and receive messages with their body, especially with their hands. Gestures play an important role in teacher-student classroom interactions. In the domain of education, many research projects have focused on the study of such gestures either in real classrooms or in tutorial settings with experienced teachers. Novice teachers especially need to understand the messages they are sending through nonverbal communication as this can have a major effect on their ability to manage behaviors and deliver content. Such learning should optimally occur before experiencing the real classroom. To assist in this process, we have developed a virtual classroom environment- TeachLivE- and used it for teacher practice, reflection and assessment. This paper investigates the way teachers use gestures in the virtual classroom settings of TeachLivE. Biology and algebra teachers were evaluated in our study. Analysis of video recordings from real and virtual environment seems to indicate that algebra teachers gesture significantly more often than biology teachers. These results have implications for providing useful feedback to participant teachers.

We demonstrate a new technique to minimize photometric differences between the color space of a display, sensor, and the real world, for mixed-reality (MR) systems where the real world is visible near or around a display. In this approach, we use an uncalibrated sensor to capture images of the display showing a series of calibration patterns. Using these images, we precompute a polynomial mapping function describing the continuous color-space transform between the real-world, sensor, and display. This mapping function can be evaluated in real-time to produce images that, when rendered on the embedded display, greatly reduce the color differences between displayed images of a mixed-reality world and the surrounding real-world environment. The color distribution of the resulting displayed images is significantly closer to that of the ground truth real-world scene as perceived through the human eye or other sensors. We demonstrate the impact of this technique when applied to a simple dynamic-geometry mixed-reality application.

This paper presents an architecture to control avatars and virtual characters in remote interaction environments. A human-in-the-loop (interactor) metaphor provides remote control of multiple virtual characters, with support for multiple interactors and multiple observers. Custom animation blending routines and a gesture-based interface provide interactors with an intuitive digital puppetry paradigm. This paradigm reduces the cognitive and physical loads on the interactor while supporting natural bi-directional conversation between a user and the virtual characters or avatar counterparts. A multi-server-client architecture, based on a low-demand network protocol, connects the user environment, interactor station(s) and observer station(s). The associated system affords the delivery of personalized experiences that adapt to the actions and interactions of individual users, while staying true to each virtual character's personality and backstory. This approach has been used to create experiences designed for training, education, rehabilitation, remote presence and other-related applications.

The storage requirements for rendering with arbitrary tabular BRDFs can be quite large. This limits the number of BRDFs that can be in used in a scene to only a few. Furthermore, material parameters can be too complex to store and render per-pixel.

A major goal for researchers in neuroevolution is to evolve artificial neural networks (ANNs) that can learn during their lifetime. Such networks can adapt to changes in their environment that evolution on its own cannot anticipate. However, a profound problem with evolving adaptive systems is that if the impact of learning on the fitness of the agent is only marginal, then evolution is likely to produce individuals that do not exhibit the desired adaptive behavior. Instead, because it is easier at first to improve fitness without evolving the ability to learn, they are likely to exploit domain-dependent static (i.e. non-adaptive) heuristics. This paper proposes a way to escape the deceptive trap of static policies based on the novelty search algorithm, which opens up a new avenue in the evolution of adaptive systems because it can exploit the behavioral difference between learning and non-learning individuals. The main idea in novelty search is to abandon objective-based fitness and instead simply search only for novel behavior, which avoids deception entirely and has shown prior promising results in other domains. This paper shows that novelty search significantly outperforms fitness-based search in a tunably deceptive T-Maze navigation domain because it fosters the emergence of adaptive behavior.

Abstract In Mixed Reality (MR) applications, immersion of virtual objects in captured video contributes to the perceived unification of two worlds, one real, one synthetic. Since virtual actors and surround may appear both closer and farther than real objects, compositing must consider spatial relationships in the resulting world. Chroma keying, often called blue screening or green screening, is one common solution to this problem. This method is under‐constrained and most commonly addressed through a combination of environment preparation and commercial products. In interactive MR domains that impose restrictions on the video camera hardware, such as in experiences using video see‐through (VST) head‐mounted displays (HMD), chroma keying becomes even more difficult due to the relatively low camera quality, the use of m ltiple camera sources (one per eye), and the required processing speed. Dealing with these constraints requires a fast and affordable solution. In our approach, we precondition the chroma key by using principal component analysis (PCA) to obtain usable alpha mattes from video streams in real‐time on commodity graphics processing units (GPUs). In addition, we demonstrate how our method compares to off‐line commercial keying tools and how it performs with respect to signal noise within the video stream. Copyright © 2009 John Wiley & Sons, Ltd.

This paper examines the efficacy of genetic algorithms (GAs) in combining input from multiple users to control a single interactive system, such as an educational exhibit at a museum. Specifically, the idea of collaborative interactive evolution (that is, interactive evolution with input from multiple users) is introduced for this purpose. Two fitness functions are proposed to guide the collaborative interactive evolution, as well as two non-GA methods for combining user input. The usefulness and success of each of these methods is examined, and the GA is shown to be a viable means for combining user input for the control of a single interactive system.

Modern society requires the public to have an increased knowledge of science beyond the basics, with average people needing to understand concepts in science, technology, engineering and mathematics that rapidly evolve throughout their lifetimes. Our future depends upon closing the gaps between citizen and scientist to create a "citizen scientist". Mixed reality innovations provide the magic to spark a lifetime of learning for community learning centers by continuously providing new content and reinventing the free-choice learning experience that helps citizens make informed choices in an increasingly complex world. This work explores a mixed reality experiential learning landscape that expands our ability to provide dynamic content structures for venues to engage the user's physical environment and interactive imagination by incorporating the conventions of story, play and game employed in competing leisure time activities. This is intended to reverse the standard decline of attendance by teenagers and young adults.

This exhibition presents a Mixed Reality experience that applies basic research to the media industries of entertainment, training and informal education. Contributing areas of research include tracking, registration, rendering, real-time and distributed algorithms, and adaptations of existing as well as the creation of new forms of artistic convention.

Abstract Virtual drama is based on the use of a shareable virtual world as a stage setting, with avatars controlled by actors and audience members. The Caracol Time Travel Project was an experiment in the use of virtual drama for learning about archaeology. Eighteen undergraduate students at the University of Central Florida used a locally developed Java‐based system for sharing VRML worlds. They designed and constructed a virtual drama to teach basic concepts of Mesoamerican archaeology and the cultural history of the ancient Maya for middle schools. This paper presents their story design and details of the system we developed to support interaction in this shared virtual world. We then discuss performance issues, lessons learned and newer features that we did not have available at the time. Copyright © 2001 John Wiley & Sons, Ltd.

Virtual drama is based on the use of a shareable virtual world as a stage setting, with avatars controlled by actors and audience members. In this experiment, students built a virtual world to teach concepts of Mesoamerican archaeology and the cultural history of the ancient Maya.

The Virtual Academy is an educational model based on multiage teams of students and adults working through the Internet to build and use virtual worlds for educational purposes. These collaborations are mediated by a range of tools ranging from electronic mail to hypermedia and video links, and result in the creation of simulation‐based role‐playing adventure games within the ExploreNet software environment ExploreNet is an Internet‐based multimedia, multiuser domain constructed specifically for educational experimentation. This article describes the Virtual Academy Model, the ExploreNet software system, and an experiment conducted in the spring of 1995. The article describes the evolution of features of ExploreNet's user interface and their relevance to collaborative work by children.

The Virtual Environment Realtime Network (VERN) is an object oriented testbed for the interconnection of environments over a network of graphical workstations. VERN is based on extensions to the networking technology of the DARPA sponsored SIMNET combined combat training system and the Distributed Interactive Simulation protocol being developed as a DOD standard. It allows for multiple participants to interact in an environment. sharing ideas and solving problems, regardless of their physical locations. Furthermore, dramatic reconstructions of historical events for education or entertainment will be possible. Indeed, much of the impact of VERN is likely to result from the ability of participants to learn from each other even if they and their machines are separated by long distances.

An analytical model is given for predicting the performance of a new support strategy for database views. This strategy, called the virtual method, is compared with traditional methods for supporting views. The analytical model's predictions of improved performance by the virtual method are then validated by comparing these results with those achieved in an experimental implementation.>

A language specification mechanism is reported which is oriented around the automatic generation of editors as well as the conventional goals of parsing and semantic analysis. The primary result is a means by which a specification in the notation can be used to produce a visual editor automatically. In particular, it is demonstrated how well suited the modern techniques of object-oriented software are to this task.>

A methodology is presented for evaluating the performance of database update schemes in a distributive environment. The methodology makes use of the history of how data are used in the database. Parameters such as update-to-retrieval ratio and average file size can be set based on the actual characterization of a system. The analysis is specifically directed toward the support of derived data within the relational model. Because concurrency is a major problem in a distributive system, the support of derived data is analyzed with respect to three distributive concurrency control techniques: master/slave, distributed, and synchronized.>

A year's work on the NSF/University of Tennessee High School Computer Science Project (HSCS) has indicated that it may indeed be possible to dissociate computer skills from the scary, elitist traditions of science and math curricula in high schools. Teachers and students remote from the traditional science/math constituency are learning to play/work with the computer. The development of HSCS is chronicled and some likely scenarios for its arrival on the high school scene are presented. The essential context is that of a race between declining computer hardware costs and declining support for public education. HSCS is succeeding because it exploits computing's unique ability to bridge between the worlds of play, study and employment.

This paper describes a current project to design an Introductory Computer Science Course for High School students. Problems concerning the choice of hardware, the selection of software, programming language(s) and the overall design of the curriculum are discussed. In addition, some previous related research is summarized and a plan for future activities is outlined.

One of the most important developments in the 70's has been the introduction of microcomputers.The impact of these systems presents a major challenge for computer educators today and in the foreseeable future.We must ask ourselves, "How can we best utilize such systems?",as well as, "How can we most effectively integrate microsystems into our Computer Science curriculum?" (1) Today it is possible to purchase an "off-theshelf" computer system for $595 (2) and this price will continue to decrease.The incorporation of minicomputer courses and laboratories in Computer Science Departments is still young (3,4), yet we're already facing a new era of computing with microsystems.Having worked with large systems for many years, we must now respond to different challenges and opportunities offered by small systems, e.g., the inherent restrictions of a smaller system versus its accessibility and availability for student "hands-on" experience.Though educators have tried to adapt to this rapid change in technology, only recently have articles appeared describing experiences in integrating micro-systems in Computer Science curricula (5,6).Though each paper covers different topics in varying degrees of depth, almost all the authors agree that having a micro-lab facility provides students with exposure to concepts and problems such as:actual hardware -computer operation -

This paper describes ASSIST-V, a software tool designed for use in the teaching of operating systems, fie management, and machine architecture courses. ASSIST-V is a program that provides an environment for the implementation, testing, and evaluation of systems software for the IBM 360 series machines. This capability is achieved by simulating all relevant aspects of the machine's architecture. In particular, ASSIST-V simulates interrupts, I/O channels, and I/O devices, as well as all IBM 360 machine instructions. In addition, ASSIST-V provides extensive debugging and statistics-gathering aids.

This paper describes a compiler called ORACLE which allows a student to examine the actions performed by a simple compiler. Two features are provided to assist the student. The first called replacement mode, provides the necessary conditions to simulate the replacement of three compiler components: symbol table management, lexical analysis, and syntax analysis. Each replacement module is monitored by ORACLE in order to detect errors and to verify correct operation. The second, a trace option, permits source statements to initiate or terminate a selective monitoring of the actions of the compiler.

Abstract A constructive proof is given which shows that every nonrecursive r.e. many-one degree is represented by the family of decision problems for partial implicational propositional calculi whose well-formed formulas contain at most two distinct variable symbols.

Abstract A new reduction class is presented for the satisfiability problem for well-formed formulas of the first-order predicate calculus. The members of this class are closed prenex formulas of the form ∀x∀yC. The matrix C is in conjunctive normal form and has no disjuncts with more than three literals, in fact all but one conjunct is unary. Furthermore C contains but one predicate symbol, that being unary, and one function symbol which symbol is binary.

Abstract In this paper we investigate some families of decision problems associated with a restricted class of Post canonical forms, specifically, those defined over one-letter alphabets whose productions have single premises and contain only one variable. For brevity sake, we call any such form an RPCF (Restricted Post Canonical Form). Constructive proofs are given which show, for any prescribed nonrecursive r.e. many-one degree of unsolvability D, the existence of an RPCF whose word problem is of degree D and an RPCF with axiom whose-decision problem is also of degree D. Finally, we show that both of these results are best possible in that they do not hold for one-one degrees.

In this paper we describe POPSS, an event driven simulator which is intended to simulate the activity of a computer system- hardware together with an operating system - as it processes a work-load. Input to the simulator is in the form of keyword parameters which are used for describing all three components - hardware, operating system, and workload.

Tag systems were defined by Post [9], [10] and have been studied by a number of researchers including Minsky [7], Maslov [6] and Aanderaa and Belsnes [1]. In their recent paper Aanderaa and Belsnes demonstrated that every r.e. many-one degree (exclusive of the degree of the empty set) is represented by the general halting problem for tag systems, that is, by the family of halting problems ranging over all tag systems. Their result depends upon an informal proof of this property for Turing machines but may be seen to be correct in light of a formal proof due to Overbeek [8]. Our aim is to extend their results to the general word problem for these systems. Specifically, we shall present an effective method which, when applied to an arbitrary r.e. set S, where S is neither empty nor the set of all natural numbers, produces a tag system R′ whose word and halting problems are both of the same many-one degree as the decision problem for S. The proof is realized by first constructing, from the description of an arbitrary Turing machine M, which machine has at least one mortal and one immortal configuration, a 5-register machine R, whose word and halting problems are both of the same many-one degree as the halting problem for M. From R we then construct the desired tag system R′. This construction combined with Overbeek's [8] shows that every r.e. many-one degree (exclusive of the degrees of the empty set and the set of all natural numbers) is represented by the general word and halting problems for tag systems. Moreover our results are seen to be best possible with regard to degrees of unsolvability in that it is not the case that every nonrecursive r.e. one-one degree is represented by either of the general decision problems for tag systems which are considered here. These results were first shown in the author's thesis [3] and were announced in [4], They form part of an extensive study into the many-one equivalence of general decision problems. An overview of the initial findings of this research project may be found in [5].