Algebraic theory of minimal nondeterministic finite automata with applications

Since the 1950s, the theory of deterministic and nondeterministic finite automata (DFAs and NFAs, respectively) has been a cornerstone of theoretical computer science. In this dissertation, our main object of study is minimal NFAs. In contrast with minimal DFAs, minimal NFAs are computationally challenging: first, there can be more than one minimal NFA recognizing a given language; second, the problem of converting an NFA to a minimal equivalent NFA is NP-hard, even for NFAs over a unary alphabet. Our study is based on the development of two main theories, inductive bases and partials, which in combination form the foundation for an incremental algorithm, ibas, to find minimal NFAs. An inductive basis is a collection of languages with the property that it can generate (through union) each of the left quotients of its elements. We prove a fundamental characterization theorem which says that a language can be recognized by an n-state NFA if and only if it can be generated by an n-element inductive basis. A partial is an incompletely-specified language. We say that an NFA recognizes a partial if its language extends the partial, meaning that the NFA’s behavior is unconstrained on unspecified strings; it follows that a minimal NFA for a partial is also minimal for its language. We therefore direct our attention to minimal NFAs recognizing a given partial. Combining inductive bases and partials, we generalize our characterization theorem, showing that a partial can be recognized by an n-state NFA if and only if it can be generated by an n-element partial inductive basis. We apply our theory to develop and implement ibas, an incremental algorithm that finds minimal partial inductive bases generating a given partial. In the case of unary languages, ibas can often find minimal NFAs of up to 10 states in about an hour of computing time; with brute-force search this would require many trillions of years.

Time, Cost, and Environmental Impact Analysis for Sustainable Design at Multiple Building Levels

Construction projects are complex endeavors that require the involvement of different professional disciplines in order to meet various project objectives that are often conflicting. The level of complexity and the multi-objective nature of construction projects lend themselves to collaborative design and construction such as integrated project delivery (IPD), in which relevant disciplines work together during project conception, design and construction. Traditionally, the main objectives of construction projects have been to build in the least amount of time with the lowest cost possible, thus the inherent and well-established relationship between cost and time has been the focus of many studies. The importance of being able to effectively model relationships among multiple objectives in building construction has been emphasized in a wide range of research. In general, the trade-off relationship between time and cost is well understood and there is ample research on the subject. However, despite sustainable building designs, relationships between time and environmental impact, as well as cost and environmental impact, have not been fully investigated. The objectives of this research were mainly to analyze and identify relationships of time, cost, and environmental impact, in terms of CO2 emissions, at different levels of a building: material level, component level, and building level, at the pre-use phase, including manufacturing and construction, and the relationships of life cycle cost and life cycle CO2 emissions at the usage phase. Additionally, this research aimed to develop a robust simulation-based multi-objective decision-support tool, called SimulEICon, which took construction data uncertainty into account, and was capable of incorporating life cycle assessment information to the decision-making process. The findings of this research supported the trade-off relationship between time and cost at different building levels. Moreover, the time and CO2 emissions relationship presented trade-off behavior at the pre-use phase. The results of the relationship between cost and CO2 emissions were interestingly proportional at the pre-use phase. The same pattern continually presented after the construction to the usage phase. Understanding the relationships between those objectives is a key in successfully planning and designing environmentally sustainable construction projects.

Algebraic Theory of Minimal Nondeterministic Finite Automata with Applications

Since the 1950s, the theory of deterministic and nondeterministic finite automata (DFAs and NFAs, respectively) has been a cornerstone of theoretical computer science. In this dissertation, our main object of study is minimal NFAs. In contrast with minimal DFAs, minimal NFAs are computationally challenging: first, there can be more than one minimal NFA recognizing a given language; second, the problem of converting an NFA to a minimal equivalent NFA is NP-hard, even for NFAs over a unary alphabet. Our study is based on the development of two main theories, inductive bases and partials, which in combination form the foundation for an incremental algorithm, ibas, to find minimal NFAs. An inductive basis is a collection of languages with the property that it can generate (through union) each of the left quotients of its elements. We prove a fundamental characterization theorem which says that a language can be recognized by an n-state NFA if and only if it can be generated by an n-element inductive basis. A partial is an incompletely-specified language. We say that an NFA recognizes a partial if its language extends the partial, meaning that the NFA's behavior is unconstrained on unspecified strings; it follows that a minimal NFA for a partial is also minimal for its language. We therefore direct our attention to minimal NFAs recognizing a given partial. Combining inductive bases and partials, we generalize our characterization theorem, showing that a partial can be recognized by an n-state NFA if and only if it can be generated by an n-element partial inductive basis. We apply our theory to develop and implement ibas, an incremental algorithm that finds minimal partial inductive bases generating a given partial. In the case of unary languages, ibas can often find minimal NFAs of up to 10 states in about an hour of computing time; with brute-force search this would require many trillions of years.

3D navigation with six degrees-of-freedom using a multi-touch display

With the introduction of new input devices, such as multi-touch surface displays, the Nintendo WiiMote, the Microsoft Kinect, and the Leap Motion sensor, among others, the field of Human-Computer Interaction (HCI) finds itself at an important crossroads that requires solving new challenges. Given the amount of three-dimensional (3D) data available today, 3D navigation plays an important role in 3D User Interfaces (3DUI). This dissertation deals with multi-touch, 3D navigation, and how users can explore 3D virtual worlds using a multi-touch, non-stereo, desktop display. ^ The contributions of this dissertation include a feature-extraction algorithm for multi-touch displays (FETOUCH), a multi-touch and gyroscope interaction technique (GyroTouch), a theoretical model for multi-touch interaction using high-level Petri Nets (PeNTa), an algorithm to resolve ambiguities in the multi-touch gesture classification process (Yield), a proposed technique for navigational experiments (FaNS), a proposed gesture (Hold-and-Roll), and an experiment prototype for 3D navigation (3DNav). The verification experiment for 3DNav was conducted with 30 human-subjects of both genders. The experiment used the 3DNav prototype to present a pseudo-universe, where each user was required to find five objects using the multi-touch display and five objects using a game controller (GamePad). For the multi-touch display, 3DNav used a commercial library called GestureWorks in conjunction with Yield to resolve the ambiguity posed by the multiplicity of gestures reported by the initial classification. The experiment compared both devices. The task completion time with multi-touch was slightly shorter, but the difference was not statistically significant. The design of experiment also included an equation that determined the level of video game console expertise of the subjects, which was used to break down users into two groups: casual users and experienced users. The study found that experienced gamers performed significantly faster with the GamePad than casual users. When looking at the groups separately, casual gamers performed significantly better using the multi-touch display, compared to the GamePad. Additional results are found in this dissertation.^

3D Navigation with Six Degrees-of-Freedom using a Multi-Touch Display

With the introduction of new input devices, such as multi-touch surface displays, the Nintendo WiiMote, the Microsoft Kinect, and the Leap Motion sensor, among others, the field of Human-Computer Interaction (HCI) finds itself at an important crossroads that requires solving new challenges. Given the amount of three-dimensional (3D) data available today, 3D navigation plays an important role in 3D User Interfaces (3DUI). This dissertation deals with multi-touch, 3D navigation, and how users can explore 3D virtual worlds using a multi-touch, non-stereo, desktop display. The contributions of this dissertation include a feature-extraction algorithm for multi-touch displays (FETOUCH), a multi-touch and gyroscope interaction technique (GyroTouch), a theoretical model for multi-touch interaction using high-level Petri Nets (PeNTa), an algorithm to resolve ambiguities in the multi-touch gesture classification process (Yield), a proposed technique for navigational experiments (FaNS), a proposed gesture (Hold-and-Roll), and an experiment prototype for 3D navigation (3DNav). The verification experiment for 3DNav was conducted with 30 human-subjects of both genders. The experiment used the 3DNav prototype to present a pseudo-universe, where each user was required to find five objects using the multi-touch display and five objects using a game controller (GamePad). For the multi-touch display, 3DNav used a commercial library called GestureWorks in conjunction with Yield to resolve the ambiguity posed by the multiplicity of gestures reported by the initial classification. The experiment compared both devices. The task completion time with multi-touch was slightly shorter, but the difference was not statistically significant. The design of experiment also included an equation that determined the level of video game console expertise of the subjects, which was used to break down users into two groups: casual users and experienced users. The study found that experienced gamers performed significantly faster with the GamePad than casual users. When looking at the groups separately, casual gamers performed significantly better using the multi-touch display, compared to the GamePad. Additional results are found in this dissertation.

Digital and Social Inequalities : A Qualitative Assessment of the Impact of the Connecting Equality Program on Argentinean Youth

This paper focuses on the ties between social and digital inequalities among Argentinean youth. It uses a qualitative approach to explore different aspects of the everyday lives of adolescents, such as sociability, leisure time and family use of Information and Communication Technologies (ICTs), in order to assess the impact of the Connecting Equality Program (Programa Conectar Igualdad, PCI) on reducing digital inequalities and fostering social inclusion. What were the existing conditions of access for students and their families when the PCI was first implemented? What influence does the implementation of the PCI have on the individual, family and scholastic appropriation of ICTs? How does the use of computers and the Internet vary among youth? Has this large-scale incorporation of netbooks in schools, and especially homes and free time changed it in any way? Does the appropriation of ICTs through student participation in the PCI contribute to material and symbolic social inclusion? In order to answer these questions, we compare the processes of ICT appropriation among lower and middle class adolescents, focusing on the distinctive uses and meanings assigned to computers and the Internet by boys and girls in their daily lives. For this purpose we analyze data collected through semi-structured interviews in two schools in Greater La Plata, Argentina during 2012. The main findings show that in terms of access, skills and types of use, the implementation of the PCI has had a positive impact among lower class youth, guaranteeing access to their first computers and promoting the sharing of knowledge and digital skills with family members. Moreover, evidence of more diverse and intense use of ICTs among lower class students reveals the development of digital skills related to educational activities. Finally, in terms of sociability, having a personal netbook enables access to information and cultural goods which are very significant in generating ties and strengthening identities and social integration

Digital and Social Inequalities : A Qualitative Assessment of the Impact of the Connecting Equality Program on Argentinean Youth

This paper focuses on the ties between social and digital inequalities among Argentinean youth. It uses a qualitative approach to explore different aspects of the everyday lives of adolescents, such as sociability, leisure time and family use of Information and Communication Technologies (ICTs), in order to assess the impact of the Connecting Equality Program (Programa Conectar Igualdad, PCI) on reducing digital inequalities and fostering social inclusion. What were the existing conditions of access for students and their families when the PCI was first implemented? What influence does the implementation of the PCI have on the individual, family and scholastic appropriation of ICTs? How does the use of computers and the Internet vary among youth? Has this large-scale incorporation of netbooks in schools, and especially homes and free time changed it in any way? Does the appropriation of ICTs through student participation in the PCI contribute to material and symbolic social inclusion? In order to answer these questions, we compare the processes of ICT appropriation among lower and middle class adolescents, focusing on the distinctive uses and meanings assigned to computers and the Internet by boys and girls in their daily lives. For this purpose we analyze data collected through semi-structured interviews in two schools in Greater La Plata, Argentina during 2012. The main findings show that in terms of access, skills and types of use, the implementation of the PCI has had a positive impact among lower class youth, guaranteeing access to their first computers and promoting the sharing of knowledge and digital skills with family members. Moreover, evidence of more diverse and intense use of ICTs among lower class students reveals the development of digital skills related to educational activities. Finally, in terms of sociability, having a personal netbook enables access to information and cultural goods which are very significant in generating ties and strengthening identities and social integration

Digital and Social Inequalities : A Qualitative Assessment of the Impact of the Connecting Equality Program on Argentinean Youth

This paper focuses on the ties between social and digital inequalities among Argentinean youth. It uses a qualitative approach to explore different aspects of the everyday lives of adolescents, such as sociability, leisure time and family use of Information and Communication Technologies (ICTs), in order to assess the impact of the Connecting Equality Program (Programa Conectar Igualdad, PCI) on reducing digital inequalities and fostering social inclusion. What were the existing conditions of access for students and their families when the PCI was first implemented? What influence does the implementation of the PCI have on the individual, family and scholastic appropriation of ICTs? How does the use of computers and the Internet vary among youth? Has this large-scale incorporation of netbooks in schools, and especially homes and free time changed it in any way? Does the appropriation of ICTs through student participation in the PCI contribute to material and symbolic social inclusion? In order to answer these questions, we compare the processes of ICT appropriation among lower and middle class adolescents, focusing on the distinctive uses and meanings assigned to computers and the Internet by boys and girls in their daily lives. For this purpose we analyze data collected through semi-structured interviews in two schools in Greater La Plata, Argentina during 2012. The main findings show that in terms of access, skills and types of use, the implementation of the PCI has had a positive impact among lower class youth, guaranteeing access to their first computers and promoting the sharing of knowledge and digital skills with family members. Moreover, evidence of more diverse and intense use of ICTs among lower class students reveals the development of digital skills related to educational activities. Finally, in terms of sociability, having a personal netbook enables access to information and cultural goods which are very significant in generating ties and strengthening identities and social integration

Time perception in mild cognitive impairment: Interval length and subjective passage of time

Objectives: Patients with mild cognitive impairment (MCI) may have difficulties in time perception, which in turn might contribute to some of their symptoms, especially memory deficits. The aim of this study was to evaluate perception of interval length and subjective passage of time in MCI patients as compared to healthy controls. Methods: Fifty-five MCI patients and 57 healthy controls underwent an experimental protocol for time perception on interval length, a questionnaire for the subjective passage of time and a neuropsychological evaluation. Results: MCI patients presented no changes in the perception of interval length. However, for MCI patients, time seemed to pass more slowly than it did for controls. This experience was significantly correlated with memory deficits but not with performance in executive tests, nor with complaints of depression or anxiety. Conclusions: Memory deficits do not affect the perception of interval length, but are associated with alterations in the subjective passage of time.

As artes marciais chinesas para pessoas com deficiência : contextos, dilemas e possibilidades = Chinese martial arts for people with disabilities : contexts, dilemmas and possibilities

Universidade Estadual de Campinas . Faculdade de Educação Física

Survival time of random walk in random environment among soft obstacles

We consider a Random Walk in Random Environment (RWRE) moving in an i.i.d. random field of obstacles. When the particle hits an obstacle, it disappears with a positive probability. We obtain quenched and annealed bounds on the tails of the survival time in the general d-dimensional case. We then consider a simplified one-dimensional model (where transition probabilities and obstacles are independent and the RWRE only moves to neighbour sites), and obtain finer results for the tail of the survival time. In addition, we study also the ""mixed"" probability measures (quenched with respect to the obstacles and annealed with respect to the transition probabilities and vice-versa) and give results for tails of the survival time with respect to these probability measures. Further, we apply the same methods to obtain bounds for the tails of hitting times of Branching Random Walks in Random Environment (BRWRE).

Participation of kinin receptors on memory impairment after chronic infusion of human amyloid-beta 1-40 peptide in mice

Chronic infusion of human amyloid-beta 1-40 (A beta) in the lateral ventricle (LV) of rats is associated with memory impairment and increase of kinin receptors in cortical and hippocampal areas. Deletion of kinin B1 or B2 receptors abolished memory impairment caused by an acute single injection of A beta in the LV. As brain tissue and kinin receptors could unlikely react to acute or chronic administration of a similar quantity of A beta, we evaluated the participation of B1 or B2 receptors in memory impairment after chronic infusion of A beta. Male C57BI/6 J (wt), knock-out B1 (koB1) or B2 (koB2) mice (12 weeks of age) previously trained in a two-way shuttle-box and achieving conditioned avoidance responses (CAR, % of 50 trials) were infused with AB (550 pmol, 0.12 mu L/h, 28 days) or vehicle in the LV using a mini-osmotic pump. They were tested before the surgery (TO), 7 and 35 days after the infusion started (T7; T35). In T0, no difference was observed between CAR of the control (Cwt = 59.7 +/- 6.7%; CkoB1 = 46.7 +/- 4.0%; CkoB2 = 64.4 +/- 5.8%) and A beta (A beta wt = 66.0 +/- 3.0%; A beta koB1 = 66.8 +/- 8.2%; A beta koB2 = 58.7 +/- 5.9%) groups. In T7, A beta koB2 showed a significant decrease in CAR (41.0 +/- 8.6%) compared to the control-koB2 (72.8 +/- 2.2%, P <0.05). In T35, a significant decrease (P <0.05) was observed in A beta wt (40.7 +/- 3.3%) and A beta koB2 (41.2 +/- 10.7%) but not in the A beta koB1 (64.0 +/- 14.0%) compared to their control groups. No changes were observed in the controls at T35. We suggest that in chronic infusion of BA, B1 receptors could playan important role in the neurodegenerative process. Conversely, the premature memory impairment of koB2 suggests that it may be a protective factor. (C) 2009 Elsevier Ltd. All rights reserved.

COMPARATIVE STUDY OF THE SENSITIVITY OF DIABETIC LOWER EXTREMITIES WITH AND WITHOUT ULCERS USING THE PSSD (TM)

Introduction To determine and compare thresholds of cutaneous sensitivity of lower extremities in diabetic patients with an ulcer on only one lower extremity Methods and Materials The study group included 20 patients with mean age of 61 6 and average time with diabetes of 12 4 years All patients were previously tested using Semmes-Weinstein monofilament 5 07 Sensitivity was evaluated using the two point discrimination test and the PSSD (TM) (Pressure-Specified Sensory Device) in order to assess touch thresholds in a quantitative manner, in g/mm(2) Three skin areas were tested hallux pulp, dorsum of foot and medial heel, including four tests 1 point static, 1 point moving, 2 points static and 2 points moving Results Mean 2 point discrimination distance in mm was higher in feet with ulcers, but the difference between extremities was only statistically significant for the hallux. With the PSSD (TM), all patients had higher pressure thresholds in feet with ulcers when compared with feet without ulcers, in all tests, with statistical significance Conclusion The PSSD (TM) was able to differentiate levels of sensation between extremities with and without ulcers in diabetic patients, with statistical significance

Falls prevention in rural general practice: what stands the test of time and where to from here?

Objective: General practitioner recall of the 1992-96 'Stay on Your Feet'(SOYF) program and its influence on practice were surveyed five years post-intervention to gauge sustainability of the SOYF General Practice (GP) component. Methods: A survey assessed which SOYF components were still in existence, current practice related to falls prevention, and interest in professional development. All general practitioners (GPs) situated within the boundaries of a rural Area Health Service were mailed a survey in late 2001. Results: Response rate was 66.5% (139/ 209). Of 117 GPs in practice at the time of SOYF, 80.2% reported having heard of SOYF and 74.4% of those felt it had influenced practice. Half (50.9%) still had a copy of the SOYF GP resource and of those, 58.6% used it at least 'occasionally'. Three-quarters of GPs surveyed (75.2%) checked medications 'most/almost all' of the time with patients over 60 years; 46.7% assessed falls risk factors; 41.3% gave advice; and 22.6% referred to allied health practitioners. GPs indicated a strong interest in falls prevention- related professional development. There was no significant association between use of the SOYF resource package and any of the current falls prevention practices (all chi(2)>0.05). Conclusions and implications: There was high recall of SOYF and a general belief that it influenced practice. There was little indication that use of the resource had any lasting influence on GPs' practices. In future, careful thought needs to go into designing a program that has potential to affect long-term change in GPs' falls prevention practice.

Pre-treatment of cattle sperm and/or oocyte with antibody to lipocalin type prostaglandin D synthase inhibits in vitro fertilization and increases sperm-oocyte binding

The present study was conducted to determine the affect of pre-treating of oocytes and/or sperm with a rabbit polyclonal antibody against recombinant cattle lipocalin type prostaglandin D synthase (alpha L-PGDS) on in vitro sperm-oocyte binding and fertilization. In vitro matured cattle oocytes were incubated (39 degrees C, 5% CO2 in air) for I It in the following treatments either 500 mu L of fertilization medium (FM) or FM with alpha L-PGDS (1:2000). Frozen-thawed spermatozoa were washed by a 45/90% layered Percoll gradient centrifugation and incubated for I h either FM or FM with a L-PGDS. This study utilized five different treatments: (1) no antibody (control); (2) a rabbit IgG against a non-bovine antigen, bacterial histidase (alpha-hist); (3) a L-PGDS at fertilization time (with fertilization medium); (4) alpha L-PGDS-treated oocytes; or (5) a L-PGDS-treated sperm. Pre-treated oocytes were incubated with 10 X 10(4) washed spermatozoa per 25 oocytes. Oocytes used to assess sperm binding were stained with Hoescht 33342, and the number of sperm bound per zonae pellucidae counted. The remaining oocytes were fixed in acid alcohol, stained with 1% acetate-orcein and observed to determine the presence of pronuclei. More sperm bound to the zonae pellucidae when oocytes and/or sperm were pre-treated with alpha. L-PGDS: (1) 26.4 +/- 3.0; (2) 25.6 +/- 3.0; (3) 59.7 +/- 3.0; (4) 56.4 +/- 3.0; and (5) 57.1 +/- 3.0. Addition of alpha L-PGDS with sperm, oocytes, or both, decreased fertilization (P < 0.05) compared with the control: (1) 89.2 +/- 2.0%; (2) 87.5 +/- 2.0%; (3) 19.4 +/- 2.0%; (4) 27.2 +/- 3.1%; and (5) 14.1 +/- 3.4%. The alpha L-PGDS reacts with both oocytes and spermatozoa, resulting in increases of in vitro sperm-oocyte binding and inhibition of fertilization. These observations suggest that L-PGDS may have a role in cattle fertilization. (c) 2007 Elsevier B.V. All rights reserved.