Technical Reports

A list with abstracts sorted by year - 1996

How to Parallelize Sequential Processes

by Antonín Kuèera, Accepted to the 8th International Conference on Concurrency Theory (CONCUR`97). December 1996, 24 pages.

FIMU-RS-96-05. Available as Postscript, PDF.

Abstract:

A process is prime if it cannot be decomposed into a parallel product of nontrivial processes. We characterize all non-prime normed BPA processes together with their decompositions in terms of normal forms which are designed in this paper. Then we show that it is decidable whether a given normed BPA process is prime and if not, its decomposition can be effectively constructed. This brings other positive decidability results. Finally, we prove that bisimilarity is decidable in a large subclass of normed PA processes.

Word Hy-phen-a-tion by Neural Networks

by Pavel Smr¾, Petr Sojka, August 1996, 10 pages.

FIMU-RS-96-04. Available as Postscript, PDF.

Abstract:

We are discussing our experiments we made when learning feedforward neural network to find possible hyphenation points in all words of given language. Neural networks show to be a good device for solving this difficult problem. The structure of the multilayer neural network used is given, together with a discussion about training sets, influence of input coding and results of experiments done for the Czech language. We end up with pros and cons of our approach tested - hybrid architecture suitable for a multilingual system.

Comparing Expressibility of Normed BPA and Normed BPP Processes

by Ivana Èerná, Mojmír Køetínský, Antonín Kuèera, This is a full version of the paper which is to be presented at CSL`96. June 1996, 28 pages.

FIMU-RS-96-02. Available as Postscript, PDF.

Abstract:

We compare the classes of behaviours (transition systems) which can be generated by normed BPA_{\tau} and normed BPP_{\tau} processes. We exactly classify the intersection of these two classes, i.e., the class of transition systems which can be equivalently (up to bisimilarity) described by the syntax of normed BPA_{\tau} and normed BPP_{\tau} processes. We provide such a characterisation for classes of normed BPA and normed BPP processes as well.

Next we show that it is decidable in polynomial time whether for a given normed BPA_{\tau} (or BPP_{\tau} respectively) process X there is some (unspecified) normed BPP_{\tau} (or BPA_{\tau} respectively) process X` such that X is bisimilar to X`. Moreover, if the answer is positive then our algorithms also construct the process X`. Simplified versions of the algorithms mentioned above for normed BPA and normed BPP are given too.

As an immediate (but important) consequence we also obtain the decidability of bisimilarity in the union of normed BPA_{\tau} and normed BPP_{\tau} processes.

Regularity is Decidable for Normed PA Processes in Polynomial Time

by Antonín Kuèera, This paper is going to be presented at FST&TCS`96 conference, LNCS 1180, Springer-Verlag. February 1996, 17 pages.

FIMU-RS-96-01. Available as Postscript, PDF.

Abstract:

A process X is regular if it is bisimilar to a process X` with finitely many states. We prove that regularity of normed PA processes is decidable and we present a practically usable polynomial-time algorithm. Moreover, if the tested normed PA process X is regular then the process X` can be effectively constructed. It implies decidability of bisimulation equivalence for any pair of processes such that one process is a normed PA process and the other process has finitely many states.