Language Decompositions, Primality, and Trajectory-Based Operations

Kai Salomaa

                                                                 School of Computing, Queen's University
                                                                            Kingston, Ontario, Canada

Questions dealing with decompositions of languages were studied in depth already by Conway in the 70's. It is well known that it is decidable whether or not a given regular language can be written in a nontrivial way as a catenation of two languages. Decomposability questions become more involved when we consider operations other than catenation. Shuffle along trajectories provides a unified formalism to define many of the commonly used language operations. Decomposability of a regular language along a regular set of trajectories is known to be decidable only in very restricted cases.

In this talk I survey recent results and discuss open problems on language decomposability. Also, the related notions of primality and prime decompositions of languages are discussed.

Automata, Probability, and Recursion

Mihalis Yannakakis
Department of Computer Science, Columbia University
New York, NY, USA

We discuss work on the modeling and analysis of systems with probabilistic and recursive features. Recursive Markov chains extend ordinary finite state Markov chains with the ability to invoke other Markov chains in a potentially recursive manner. The equivalent model of Probabilistic Pushdown Automata extends ordinary pushdown automata with probabilistic actions. Both of these are natural abstract models for probabilistic programs with procedures, and related systems. They generalize other classical well-studied stochastic models, e.g., Stochastic Context-free Grammars and (Multi-type) Branching Processes, that arise in a variety of areas. More generally, Recursive Markov Decision Processes and Recursive Stochastic Games can be used to model recursive systems that have both probabilistic and nonprobabilistic, controllable actions. In recent years there has been substantial work on the algorithmic analysis of these models, regarding basic questions of termination, reachability, and analysis of the properties of their executions. In this talk we will present some of the basic theory, algorithmic methods, results, and challenges.

Concurrency, Synchronization, and Conflicts in Petri Nets

Hsu-Chun Yen
Dept. of Electrical Engineering, National Taiwan University
and
Dept. of Computer Science, Kainan University, Taiwan, R.O.C.

Petri nets represent one of the most popular formalisms for specifying, modeling, and analyzing concurrent systems. However, many interesting problems concerning Petri nets are either undecidable or of very high complexity. The computational power of Petri nets stems from the ability for Petri net transitions to compete for resources as well as to synchronize and to execute concurrently in the course of a computation. In this talk, we first give a brief survey of Petri nets from the perspectives of complexity and formal languages, and then show some recent progresses in characterizing the roles played by concurrency, synchronization and conflicts in various complexity and language issues of Petri nets and related models.


Nondeterministic Finite Automata---Recent Results on the Descriptional and Computational Complexity

Markus Holzer
Institut fur Informatik
Technische Universitat Munchen
 
 


Nondeterministic finite automata (NFAs) were introduced by Rabin and Scott (1959), where their equivalence to deterministic finite automata was shown. Over the last 50 years, a vast literature documenting the importance of finite automata as an enormously valuable concept has been developed. In the present paper, we tour a fragment of this literature. Mostly, we discuss recent developments relevant to NFAs related problems like, for example: (i) simulation of and by several types of finite automata,(ii) minimization and approximation,(iii) size estimation of minimal NFAs, and (iv) state complexity of language operations. We thus come across descriptional and computational complexity issues of nondeterministic finite automata. We do not prove these results but we merely draw attention to the big picture and some of the main ideas involved.