Titlebook: Implementation and Applications of Automata; 13th International C Oscar H. Ibarra,Bala Ravikumar Conference proceedings 2008 Springer-Verla

颠簸地移动

Five Determinisation Algorithms aim to reduce memory usage and produce smaller output automata. One of them produces automata that are already minimal. We apply our algorithms to determinise automata that describe the possible sequences appearing after a fixed-length run of cellular automaton 110, and obtain a significant improvement in both memory and time efficiency.

整理

gimmick

Hopcroft’s Minimization Technique: Queues or Stacks?he setting of cover automata and an algorithm based on the Hopcroft’s method used for minimization of cover automata. We also show that a LIFO implementation for the splitting list is desirable for the case of unary languages in the setting of deterministic finite automata.

懒洋洋

A Translation from the HTML DTD into a Regular Hedge Grammarize a subclass of SGML DTDs and develop a translation into regular hedge grammars. Thus we can validate dynamically generated HTML documents. We have implemented this translation and incorporated it in the PHP string analyzer. The experimental results show that the validation through this translation works well in practice.

茁壮成长

On Complexity of Two Dimensional Languages Generated by Transducerserage growth rate of the number of blocks in the language as a measure of its complexity, also known as the entropy of the language, we show that every entropy value of a one-dimensional regular language can be obtained as an entropy value of a 2d transducer language.

insidious

hyperuricemia

Concurrency, Synchronization, and Conflicts in Petri Netswer and upper bounds, respectively, for the boundedness problem. As for the containment and the equivalence problems, Rabin [1] and Hack [5], respectively, showed these two problems to be undecidable. The reachability problem is known to be decidable [8] and exponential-space-hard [7].

maculated

aquatic

Exaggerate

Tree-Series-to-Tree-Series Transformationsactical condition that guarantees well-definedness of the ts-ts transformation in arbitrary commutative semirings. For positive (ie, zero-sum and zero-divisor free) semirings the condition actually characterizes the well-definedness, so that well-definedness is decidable in this scenario.