Fundamenta Informaticae - Volume 111, issue 2

Authors: Chen, Zhe

Article Type: Research Article

Abstract: An ω-grammar is a formal grammar used to generate ω-words (i.e. infinite length words), while an ω-automaton is an automaton used to recognize ω-words. This paper gives clean and uniform definitions for ω-grammars and ω-automata, provides a systematic study of the generative power of ω-grammars with respect to ω-automata, and presents a complete set of results for various types of ω-grammars and acceptance modes. We use the tuple (σ, ρ, π) to denote various acceptance modes, where σ denotes that some designated elements should appear at least once or infinitely often, ρ denotes some binary relation between two sets, and …π denotes normal or leftmost derivations. Technically, we propose (σ, ρ, π)-accepting ω-grammars, and systematically study their relative generative power with respect to (σ, ρ)-accepting ω-automata. We show how to construct some special forms of ω-grammars, such as ϵ-production-free ω-grammars. We study the equivalence or inclusion relations between ω-grammars and ω-automata by establishing the translation techniques. In particular, we show that, for some acceptance modes, the generative power of ω-CFG is strictly weaker than ω-PDA, and the generative power of ω-CSG is equal to ω-TM (rather than linear-bounded ω-automata-like devices). Furthermore, we raise some remaining open problems for two of the acceptance modes. Show more

Keywords: ω-automaton, ω-grammar, ω-language, generative power

DOI: 10.3233/FI-2011-557

Citation: Fundamenta Informaticae, vol. 111, no. 2, pp. 119-145, 2011

Authors: Foryś, Wit | Oprocha, Piotr

Article Type: Research Article

Abstract: We study interrelations between symbolic descriptions of concurrently evolving systems and underlying sequential dynamics. The basic framework for this research is formulated on the background of the theory of traces. We focus our interests on minimal shifts and t-shifts generated by them, that is shifts defined in the space of infinite real traces. We show that sets of infinite real traces generated by minimal shifts are always closed and, under some conditions, are also t-shifts. Additional discussion for the case of small alphabets (containing at most four letters) is also provided.

Keywords: word, trace, shift, shift on traces, minimal shift

DOI: 10.3233/FI-2011-558

Citation: Fundamenta Informaticae, vol. 111, no. 2, pp. 147-161, 2011

Authors: Fülöp, Zoltán | Maletti, Andreas | Vogler, Heiko

Article Type: Research Article

Abstract: Weighted extended tree transducers (wxtts) over countably complete semirings are systematically explored. It is proved that the extension in the left-hand sides of a wxtt can be simulated by the inverse of a linear and nondeleting tree homomorphism. In addition, a characterization of the class of weighted tree transformations computable by bottom-up wxtts in terms of bimorphisms is provided. Backward and forward application to recognizable weighted tree languages are standard operations for wxtts. It is shown that the backward application of a linear wxtt preserves recognizability and that the domain of an arbitrary bottom-up wxtt is recognizable. Examples demonstrate that …neither backward nor forward application of arbitrary wxtts preserves recognizability. Finally, a HASSE diagram relates most of the important subclasses of weighted tree transformations computable by wxtts. Show more

Keywords: weighted tree transducer, preservation of recognizability, HASSE diagram, forward application, backward application

DOI: 10.3233/FI-2011-559

Citation: Fundamenta Informaticae, vol. 111, no. 2, pp. 163-202, 2011

Authors: Intrigila, Benedetto | Statman, Richard

Article Type: Research Article

Abstract: The λ-theory ℋ is obtained from β-conversion by identifying all closed unsolvable terms (or, equivalently, terms without head normal form). The range problem for the theory ℋ asks whether a closed term has always (up to equality in ℋ) either an infinite range or a singleton range (that is, it is a constant function). Here we give a solution to a natural version of this problem, giving a positive answer for the theory ℋ restricted to Combinatory Logic. The method of proof applies also to the Lazy λ-Calculus.

Keywords: Lambda-Calculus, Combinatory Logic, Range Problem

DOI: 10.3233/FI-2011-560

Citation: Fundamenta Informaticae, vol. 111, no. 2, pp. 203-222, 2011

Authors: She, Yanhong | He, Xiaoli | Wang, Guojun

Article Type: Research Article

Abstract: A propositional logic PRL for rough sets was proposed in [1]. In this paper, we initially introduce the concepts of rough (upper, lower) truth degrees on the set of formulas in PRL. Then, by grading the rough equality relations, we propose the concepts of rough (upper, lower) similarity degree. Finally, three different pseudo-metrics on the set of rough formulas are obtained, and thus an approximate reasoning mechanism is established.

Keywords: Rough (upper, lower) truth degree, Rough (upper, lower) similarity degree, Rough (upper, lower) pseudo-metric, Approximate reasoning

DOI: 10.3233/FI-2011-561

Citation: Fundamenta Informaticae, vol. 111, no. 2, pp. 223-239, 2011

Authors: Yu, Jia | Kong, Fanyu | Cheng, Xiangguo | Hao, Rong | Fan, Jianxi

Article Type: Research Article

Abstract: In traditional identity-based encryption schemes, security will be entirely lost once secret keys are exposed. However, with more and more use of mobile and unprotected devices, key exposure seems unavoidable. To deal with this problem, we newly propose a forward-secure identity-based public-key encryption scheme. In this primitive, the exposure of the secret key in one period doesn't affect the security of the ciphertext generated in previous periods. Any parameter in our scheme has at most log-squared complexity in terms of the total number of time periods. We also give the semantic security notions of forward-secure identity-based public-key encryption. The proposed …scheme is proven semantically secure in the standard model. As far as we are concerned, it is the first forward-secure identity-based public-key encryption scheme without random oracles. Show more

Keywords: forward security, public-key encryption, key exposure, standard model

DOI: 10.3233/FI-2011-562

Citation: Fundamenta Informaticae, vol. 111, no. 2, pp. 241-256, 2011