Regular patterns, regular languages and context-free languages

In this paper we consider two questions. First we consider whether every pattern language which is regular can be generated by a regular pattern. We show that this is indeed the case for extended (erasing) pattern languages if alphabet size is at least four. In all other cases, we show that there are patterns generating a regular language which cannot be generated by a regular pattern. Next we consider whether there are pattern languages which are context-free but not regular. We show that, for alphabet size 2 and 3, there are both erasing and non-erasing pattern languages which are context-free but not regular. On the other hand, for alphabet size at least 4, every erasing pattern language which is context-free is also regular. It is open at present whether there exist non-erasing pattern languages which are context-free but not regular for alphabet size at least 4.     

A note on Lindenmayer systems,Szilard languages,spectra, and equivalence

We investigate the Szilard languages and the spectra of Lindenmayer systems through the generalization of Lindenmayer systems toK-iteration grammars and context-sensitiveK-iteration grammars. Various decidability and undecidability results are presented with respect to the evaluation of Szilard languages and spectra for particularK-iteration grammars. Further, two different definitions of the Szilard and spectral equivalence of twoK-iteration grammars are investigated.Work carried out under a National Research Council of Canada Grant No. A-7700.     

A formal library of set relations and its application to synchronous languages

Set relations are particularly suitable for specifying the small-step operational semantics of synchronous languages. In this paper, a formal library of set relations for the definition, verification of properties, and execution of binary set relations is presented. The formal library consists of a set of theories written in the Prototype Verification System (PVS) that contains definitions and proofs of properties, such as determinism and compositionality, for synchronous relations. The paper also proposes a serialization procedure that enables the simulation of synchronous set relations via set rewriting systems. The library and the serialization procedure are illustrated with the rewriting logic semantics of the Plan Execution Interchange Language (PLEXIL), a rich synchronous plan execution language developed by NASA to support autonomous spacecraft operations.     

String and graph grammar characterizations of bounded regular languages

Two grammatical characterizations of the bounded regular languages are presented: one in terms of graph grammars, the other using string grammars. First it is shown that a class of state graphs recognizing the bounded regular languages can be generated by a particular second-order contextfree graph grammar. Next we call uniquely recursive a right-linear (string) grammar having at most one right-recursive production for each of its nonterminals. It is then established that the class of languages generated by uniquely recursive, sequential right-linear grammars is exactly the bounded regular languages. Some comments on the relationship between string and graph grammars are made.     

A comparison of languages: CORAL,PASCAL, PEARL,ADA and ESL

The facilities of some languages used for real-time applications are summarized and compared. It is not intended to give a recommendation for the use of one of these languages. Rathermore a set of different approaches is presented which provides an overview.     

P-selective sets,tally languages,and the behavior of polynomial time reducibilities onNP

The notion ofp-selective sets, and tally languages, are used to study polynomial time reducibilities onNP. P-selectivity has the property that a setA belongs to the classP if and only if both _m ^p A andA isp-selective. We prove that for every tally language set inNP there exists a polynomial time equivalent set inNP that isp-selective. From this result it follows that if NEXT DEXT, then polynomial time Turing and many-one reducibilities differ onNP. This research was supported in part by the National Science Foundation under grant MCS 77-23493     

User acceptance of context-aware services: self-efficacy,user innovativeness and perceived sensitivity on contextual pressure

The aim of this paper is to empirically examine how individual characteristics affect user acceptance of context-aware services such as GPS-based telematics systems and location-based commerce, which together have become highly promising fields for mobile or ubiquitous e-commerce. To examine these individual characteristics, we applied a technology acceptance model to construct an amended model that focuses on three individual differences: self-efficacy, personal innovativeness and perceived sensitivity on contextual pressure. As a result, we discovered that the perceived sensitivity on contextual pressure, which is newly adopted as a construct in this paper, affects behavioural intention in using context-aware services.     

User acceptance of context-aware services: self-efficacy, user innovativeness and perceived sensitivity on contextual pressure

The aim of this paper is to empirically examine how individual characteristics affect user acceptance of context-aware services such as GPS-based telematics systems and location-based commerce, which together have become highly promising fields for mobile or ubiquitous e-commerce. To examine these individual characteristics, we applied a technology acceptance model to construct an amended model that focuses on three individual differences: self-efficacy, personal innovativeness and perceived sensitivity on contextual pressure. As a result, we discovered that the perceived sensitivity on contextual pressure, which is newly adopted as a construct in this paper, affects behavioural intention in using context-aware services.