Reeder, Janina; Steffen, Peter; Giegerich, Robert: Effective ambiguity checking in biosequence analysis. In: BMC Bioinformatics. Jg.6 H. 1. 2005
Inhalt
- Previous work
- Formalization of ambiguity
- Formal grammars
- Context free grammars
- Stochastic context free grammars
- Syntactic versus semantic ambiguity
- Semantic ambiguity in dynamic programming
- SCFGs for RNA secondary structure analysis
- Results and discussion
- Sources of ambiguity, and how to avoid them
- Three simple cases
- Testing for ambiguity
- Proving non-ambiguity
- Semantic ambiguity in dynamic programming is unde-cidable
- Theorem 1 Semantic ambiguity in dynamic programming is formally undecidable
- Hand-made proof of non-ambiguity
- Mechanical proof of non-ambiguity
- Theorem 2 Let G* be derived from G according to the above rules. Then, G* is fl-ambiguous if and only if G is semantically ambiguous
- Conclusion
- Methods
- Authors' contributions
- Appendix: Ambiguity in DP is undecidable
- Note
- Acknowledgements
- References