Titlebook: STACS 2001; 18th Annual Symposiu Afonso Ferreira,Horst Reichel Conference proceedings 2001 Springer-Verlag Berlin Heidelberg 2001 Automat.a

艺术

Star-Free Open Languages and Aperiodic Loopsure properties. We also prove that aperiodic loops recognize only star-free open languages and give some examples. Finally, we show that the wreath product principle can be applied to groupoids, and we use it to prove a decomposition theorem for recognizers of regular open languages.

Landlocked

Residual Finite State Automataially smaller. We provide an algorithm that computes the canonical RFSA equivalent to a given NFA. We study the complexity of several decision and construction problems linked to the class of RFSA: most of them are PSPACE-complete.

立即

Deterministic Radio Broadcasting at Low Costios depending on whether nodes know or do not know global parameters of the network: the number . of nodes and the eccentricity . of the source. Our main contribution are lower bounds on time of low-cost broadcasting which show sharp differences between these scenarios.

Alopecia-Areata

escalate

2-Nested Simulation Is Not Finitely Equationally Axiomatizabletyft/tyxt format is a congruence format. In the linear time-branching time spectrum of van Glabbeek [.], 2-nested simulation is one of the few equivalences for which no finite equational axiomati- zation is presented. In this paper we prove that such an axiomatization does not exist for 2-nested simulation.

etiquette

Stress-Fracture

tendinitis

The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE—Complete constraints, i.e., such that a possible solution has to respect a specification given by a rational language. Our main result states that the existential theory of equations with rational constraints in free groups is PSPACE-complete.

encomiast

Concerto