Algorithms for Glushkov K-graphs

Details Algorithms for Glushkov K-graphs Algorithms for Glushkov K-graphs

2009-07-24

arxiv.org/abs/0907.4296v2

Computer Science

Formal Languages and Automata Theory

31 pages, 20 figures, 1 table

Scientific paper

The automata arising from the well known conversion of regular expression to non deterministic automata have rather particular transition graphs. We refer to them as the Glushkov graphs, to honour his nice expression-to-automaton algorithmic short cut (On a synthesis algorithm for abstract automata, Ukr. Matem. Zhurnal, 12(2):147-156, 1960, In Russian). The Glushkov graphs have been characterized (P. Caron and D. Ziadi, Characterization of Glushkov automata. Theoret. Comput. Sci., 233(1-2):75-90, 2000) in terms of simple graph theoretical properties and certain reduction rules. We show how to carry, under certain restrictions, this characterization over to the weighted Glushkov graphs. With the weights in a semiring K, they are defined as the transition Glushkov K-graphs of the Weighted Finite Automata (WFA) obtained by the generalized Glushkov construction (P. Caron and M. Flouret, Glushkov construction for series: the non commutative case, Internat. J. Comput. Math., 80(4):457-472, 2003) from the K-expressions. It works provided that the semiring K is factorial and the K-expressions are in the so called star normal form (SNF) of Bruggeman-Klein (Regular expressions into finite automata, Theoret. Comput. Sci., 120(2):197-213, 1993) The restriction to the factorial semiring ensures to obtain algorithms. The restriction to the SNF would not be necessary if every K-expressions were equivalent to some with the same litteral length, as it is the case for the boolean semiring B but remains an open question for a general K.

Affiliated with

Also associated with

No associations

Rating

Algorithms for Glushkov K-graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Algorithms for Glushkov K-graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithms for Glushkov K-graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-310344