×

Descendants of regular language in a class of rewriting systems: Algorithm and complexity of an automata construction. (English) Zbl 0643.68119

Rewriting techniques and applications, Proc. 2nd Int. Conf., Bordeaux/France 1987, Lect. Notes Comput. Sci. 256, 121-132 (1987).
Summary: [For the entire collection see Zbl 0619.00025.]
Recent works on public key encryption for secure network communication [D. Dolev and A. C. Yao, IEEE Trans. Inf. Theory IT-29, 198- 208 (1983; Zbl 0502.94005)] have brought back the following problem: given a regular set R on A *, defined by a non deterministic finite automaton with n states and a rewriting system T, how can we construct an automaton that recognizes the set of descendants of \(R: \Delta\) *(R) when this language is regular [the author, C. R. Acad. Sci., Paris, Sér. A 269, 1188-1190 (1969; Zbl 0214.039)]. Some algorithms are found by R. V. Book and F. Otto [(*)Inf. Process. Lett. 20, 5-11 (1985; Zbl 0561.68030)] or J. Sakarovitch and me [(**)ibid. 23, 281-287 (1986; Zbl 0624.68070)], in very particular cases of systems and gave complexity in O(n 4) in (*) and O(n 3) in (**). Here we give a strong extension of these algorithms in a large class of systems however the complexity of our algorithm does not depend on the length of the words of T and is at most in O(n 6).

MSC:

68Q45 Formal languages and automata
68Q65 Abstract data types; algebraic specification
03D03 Thue and Post systems, etc.
03D40 Word problems, etc. in computability and recursion theory
68Q25 Analysis of algorithms and problem complexity