×

On the average minimal prefix-length of the generalized semi-Dycklanguage. (English) Zbl 0877.68077

Summary: Given two disjoint alphabets \(T_\sqsubset\) and \(T_\sqsupset\) and a relation \({\mathcal R}\subseteq T_\sqsubset\times T_\sqsupset\), the “generalized semi-Dycklanguage” \(D^{\mathcal R}\) over \(T_\sqsubset\cup T_\sqsupset\) consists of all words \(w\in(T_\sqsubset\cup T_\sqsupset)^*\) which are equivalent to the empty word under the congruence \(\delta\) defined by \(xy\equiv\varepsilon\text{ mod }\delta\) for all \((x,y)\in{\mathcal R}\). For arbitrary \(\mathcal R\), we compute the average length of the shortest prefix which has to be read in order to decide whether or not a given word of length \(n\) over \((T_\sqsubset\cup T_\sqsupset)^*\) belongs to \(D^{\mathcal R}\).

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] 1. M. ABRAMOWITZ and A. STEGUN, Handbook of Mathematical Functions, Dover, 1970. · Zbl 0171.38503
[2] 2. E. A. BENDER, Asymptotic Methods in Enumeration, SIAM Review, 1974, 16 (4), pp. 485-515. Zbl0294.05002 MR376369 · Zbl 0294.05002 · doi:10.1137/1016082
[3] 3. L. CARLITZ, D. P. ROSELLE and R. A. SCOVILLE, Some Remarks on Ballot-Type Sequences of Positive Integers, J. Comb. Theory (A), 1971, 11, pp. 258-271. Zbl0227.05007 MR281636 · Zbl 0227.05007 · doi:10.1016/0097-3165(71)90053-7
[4] 4. L. COMTET, Advanced Combinatorics, D. Reidel, 1974. Zbl0283.05001 MR460128 · Zbl 0283.05001
[5] 5. Ph. FLAJOLET and A. M. ODLYZKO, Singularity Analysis of Generating Functions, SIAM J. Discrete Math., 1990, 3 (2), pp. 216-240. Zbl0712.05004 MR1039294 · Zbl 0712.05004 · doi:10.1137/0403019
[6] 6. M. A. HARRISON, Introduction to Formal Languages, Addison-Wesley, 1978. Zbl0411.68058 MR526397 · Zbl 0411.68058
[7] 7. R. KEMP, Fundamentals of the Average Case Analysis of Particular Algorithms, Wiley-Teubner, 1984. Zbl0638.68026 MR786659 · Zbl 0638.68026
[8] 8. R. KEMP, On Prefixes of Formal Languages and Their Relation to the Average-Case Complexity of the Membership Problem, Journal of Automata, Languages and Combinatorics, 1996 (to appear). Zbl0867.68070 MR1439128 · Zbl 0867.68070
[9] 9. D. E. KNUTH, The Art of Computer Programming, Vol. 1, 2nd ed., Addison-Wesley, 1973. MR378456 · Zbl 0191.17903
[10] 10. A. ODLYZKO, Asymptotic Enumeration Methods, in: Handbook of Combinatorics, Chapt. 22, Elsevier, 1995. Zbl0845.05005 MR1373678 · Zbl 0845.05005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.