The Utilization of Single-Counter Systems Featuring Final Terminals with Non-Zero Counter Values

Öz

Hidden probabilistic one counter models (HPOCA) that are a specific model where spotting between hidden Markov models (HMMs) and probabilistic context-free grammars (PCFGs) which is a subclass of probabilistic pushdown automata contains only one stack symbol In this study, we propose a new model in which the final terminal counter value is different from zero. With this proposed model, we enhance the existing HPOCA, making it more complex. Consequently, as there will be a greater number of paths to reach the final terminal, we also evaluate the probability of reaching the target through alternative routes based on the given observation sequence. It makes the model more expressive than default HPOCA due to providing alternative final terminals. However, the inference of the final counter value could easily go to an infinite number without any threshold. A boundary is applied to prevent the occurrence of this unexpected condition. By applying this threshold value, we ensured that the computational complexity of the model is quadratic rather than cubic.

Anahtar Kelimeler

• Hidden Markov models
• Probabilistic Context-free Grammars
• Probabilistic one counter automata
• Probabilistic pushdown automata
• Natural language processing

Sıfırdan Farklı Sayaç Değerlerine Sahip Final Terminalleri İçeren Tek Sayaçlı Sistemlerin Kullanımı

Öz

Gizli olasılıklı bir sayaç modeli (HPOCA), gizli Markov modelleri (HMMs) ile olasılıklı bağlamdan bağımsız gramerler (PCFGs) arasında tespitin yalnızca bir yığın sembolü içerdiği belirli bir modeldir. Bu çalışmada, son terminal sayaç değerinin sıfırdan farklı olduğu yeni bir model öneriyoruz. Önerilen bu modelle, mevcut HPOCA'yı geliştirerek daha karmaşık hale getiriyoruz. Sonuç olarak, son terminale ulaşmak için daha fazla yol olacağından, verilen gözlem dizisine göre alternatif yollar aracılığıyla hedefe ulaşma olasılığını da değerlendiriyoruz. Alternatif son terminaller sağladığı için modeli varsayılan HPOCA'dan daha anlamlı hale getiriyor. Ancak, son sayaç değerinin çıkarımı herhangi bir eşik olmaksızın kolayca sonsuz bir sayıya gidebilir. Bu beklenmeyen durumun oluşmasını önlemek için bir sınır uygulanır. Bu eşik değerini uygulayarak, modelin hesaplama karmaşıklığının kübik değil, ikinci dereceden olmasını sağlamış oluyoruz.

Anahtar Kelimeler

• Gizli Markov modelleri
• Olasılıksal bağlamdan bağımsız gramerler
• Olasılıksal tek sayaç otomatları
• Olasılıksal itme otomatları
• Doğal dil işleme

Kaynakça

1. 1. Etessami, K., Wojtczak, D., Yannakakis, M., 2010. Quasi-birth-death processes, tree-like qbds, probabilistic 1-counter automata, and pushdown systems, Perform. Eval., 67(9), 837-857.
2. 2. Peng, L., Xie, P., Tang, Z., Liu, F., 2021. Modeling and analyzing transmission of infectious diseases using generalized stochastic petri nets. Applied Sciences, 11(18), 8400.
3. 3. Ouaknine, J., Sousa-Pinto, J., Worrell, J., 2014. On termination of integer linear loops. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 957-969.
4. 4. Ben-Amram, A.M., Genaim, S., 2013. On the linear ranking problem for integer linear-constraint loops. In Proceedings of the 40th Annual ACM Symposium on Principles of programming languages, Rome, Italy, 51-62.
5. 5. Kurucan, M., Özbaltan, M., Schewe, S., Wojtczak, D., 2022. Hidden 1-counter Markov models and how to learn them. International Joint Conferences on Artificial Intelligence Organization, Wien Austria, 4857- 4863.
6. 6. Kurucan, M., 2020. Hidden probabilistic one-counter automata. PhD Thesis, University of Liverpool, 157.
7. 7. Valiant, L.G., Paterson, M.S., 1975. Deterministic one-counter automata. Journal of Computer and System Sciences, 10(3), 340-350.
8. 8. Etessami, K., Wojtczak, D., Yannakakis, M., 2010. Quasi-birth-death processes, tree-like qbds, probabilistic 1-counter automata, and pushdown systems. Perform. Eval., 67(9), 37-857.

9. 9. Wojtczak, D., 2009. Recursive probabilistic models: efficient analysis and implementation. PhD Thesis, University of Edinburgh, UK, 201.
10. 10. Dubslaff, C., Baier, C., Berg, M., 2012. Model checking probabilistic systems against pushdown specifications. Information Processing Letters, 112(8-9), 320-328.
11. 11. Brázdil, T., Esparza, J., Kiefer, S., Kucera, A., 2013. Analyzing probabilistic pushdown automata. Formal Methods in System Design. 43(2), 1-43.
12. 12. Ford, B., 2003. Parsing expression grammars. ACM SIGPLAN Notices, 39(1), 1-12.
13. 13. Tan, Z., 2009. Validating XML constraints using automata. Proceedings of the 2009 8th IEEE/ACIS International Conference on Computer and Information Science, ICIS 2009. 1205-1210.
14. 14. Sakharov, A., Sakharov, T., 2018. The viterbi algorithm for subsets of stochastic context-free languages. Information Processing Letters, 135, 68-72.
15. 15. Siddalingappa, R., Hanumanthappa, P., Reddy, M., 2018. Hidden Markov model for speech recognition system-A pilot study and a naive approach for speech-to-text model. Advances in Intelligent Systems and Computing, 77-90.
16. 16. Fischer, A., Keller, A., Frinken, V., Bunke, H., 2012. Lexicon-free handwritten word spotting using character HMMs. Pattern Recogn. Lett., 33(7), 934-942.
17. 17. Xia, T., Chen, X., 2021. A weighted feature enhanced hidden Markov model for spam SMS filtering. Neurocomputing, 444, 48-58.
18. 18. Lakin, S.M., Kuhnle, A., Alipanahi, B., 2019. Hierarchical hidden Markov models enable accurate and diverse detection of antimicrobial resistance sequences. Commun Biol., 2, 294.
19. 19. Giada, S., Ben, S., 2021. Toward efficient Bayesian approaches to inference in hierarchical hidden Markov models for inferring animal behavior. Frontiers in Ecology and Evolution, 9, 62373.