Fundamenta Informaticae - Volume 45, issue 3

Authors: Apró, János | Vágvölgyi, Sándor

Article Type: Research Article

Abstract: We study that version of the ground tree transducer game where the same tree automaton appears as the first and second component of the associated ground tree transducer. We give conditions which imply that Beta has a winning strategy. Furthermore, we show the following decidability result. Given a ground tree transducer game where the underlying tree automaton A cannot evaluate some tree into a state or A is deterministic, we can decide which player has a …winning strategy. Moreover, whatever player has a winning strategy, we can effectively construct a partial recursive winning strategy for him. Show more

Keywords: games, automata, rewrite systems

Citation: Fundamenta Informaticae, vol. 45, no. 3, pp. 157-172, 2001

Authors: Balbiani, Philippe | Vakarelov, Dimiter

Article Type: Research Article

Abstract: This paper is devoted to the completeness issue of PDL_0^∩ – an iteration-free fragment of Propositional Dynamic Logic with intersection of programs. The trouble with PDL_0^∩ is that the operation of intersection is not modally definable. Using new techniques connected with rules for intersection and the notions of large and maximal programs, the paper demonstrates that the presented proof theory for PDL_0^∩ is complete for the standard Kripke semantics of PDL_0^∩.

Keywords: PDL with intersection, modal rules for intersection, maximal programs

Citation: Fundamenta Informaticae, vol. 45, no. 3, pp. 173-194, 2001

Authors: Champarnaud, Jean-Marc | Ziadi, Djelloul

Article Type: Research Article

Abstract: Our aim is to give a proof of the fact that two notions related to regular expressions, the prebases due to Mirkin and the partial derivatives introduced by Antimirov lead to the construction of identical nondeterministic automata recognizing the language of a given regular expression.

Keywords: Regular expressions, Finite automata, Prebases, Partial derivatives

Citation: Fundamenta Informaticae, vol. 45, no. 3, pp. 195-205, 2001

Authors: Hájek, Petr | Tulipani, Sauro

Article Type: Research Article

Abstract: The satisfiability problem for the logic FP(Ł) (fuzzy probability logic over Łukasiewicz logic) is shown to be NP-complete; satisfiability in FP(ŁΠ) (the same over the logic joining Łukasiewicz and product logic) is shown to be in PSPACE.

Keywords: fuzzy logic, probability, computational complexity

Citation: Fundamenta Informaticae, vol. 45, no. 3, pp. 207-213, 2001

Authors: Krishnan, Padmanabhan

Article Type: Research Article

Abstract: In this paper we define a particular type of timed push down automata. We show that the emptiness problem for this class is decidable. We also present a notion of homomorphism and parallel decomposition for these automata. These notions are a generalisation of the homomorphism and decomposition via partitions for finite automata.

Keywords: Time, push down automata, parallel decomposition

Citation: Fundamenta Informaticae, vol. 45, no. 3, pp. 215-229, 2001

Authors: Meduna, Alexander

Article Type: Research Article

Abstract: The present paper discusses the uniform generation of languages by scattered context grammars. More specifically, it demonstrates that every recursively enumerable language can be generated by a scattered context grammar, G, so that every sentential form in a generation of a sentence has the form y_1…y_m u, where $u$ is a terminal word and each y_i is a permutation of either of two equally long words, z_1∈{A, B, C}* and z_2∈{A, B, D}*, where A, B, …C, and D are G's nonterminals. Then, it presents an analogical result so that u precedes y_1…y_m. Show more

Keywords: uniform rewriting, permutations, scattered context grammars

Citation: Fundamenta Informaticae, vol. 45, no. 3, pp. 231-235, 2001

Authors: Nilsson, Bengt J.

Article Type: Research Article

Abstract: We present a fast algorithm for computing a watchman route in a simple polygon that is at most a constant factor longer than the shortest watchman route. The algorithm runs in O(n log n) time as compared to the best known algorithm that computes a shortest watchman route which runs in O(n^6) time.

Keywords: Computational geometry, art gallery problems, visibility, watchman routes

Citation: Fundamenta Informaticae, vol. 45, no. 3, pp. 235-281, 2001

Authors: Milnikel, Robert Saxon

Article Type: Research Article

Abstract: FC-normal logic programs are a generalization by Marek, Nerode, and Remmel of Reiter's normal default theories. They have the property that, unlike most logic programs, they are guaranteed to have simple stable models. In this paper it is shown that the problem of skeptical reasoning in FC-normal programs is Π^1_1-complete, the same complexity as for logic programs without the restriction of FC-normality. FC-normal programs are defined in such a way as to make testing a program …for FC-normality very difficult in general. A large subclass of FC-normal programs, locally FC-normal programs, is defined, shown to be recursive, and shown to have skeptical consequence as expressive as the entire class of FC-normal programs. Show more

Keywords:

Citation: Fundamenta Informaticae, vol. 45, no. 3, pp. 237-252, 2001