@misc{pastetarozle, title={P(Izraz|Gramatika): delo diplomskega seminarja}, author={Urh Primožič and Ljupčo Todorovski and Matej Petković}, year={2022}, url={https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=slv&id=139173}, publisher = {Univerza v Ljubljani}, note = {\url{https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=slv&id=139173}} } @misc{pastetakekec, title={P(Expression|Grammar): Probability of deriving an algebraic expression with a probabilistic context-free grammar}, author={Urh Primožič and Ljupčo Todorovski and Matej Petković}, year={2022}, eprint={2212.00751}, archivePrefix={arXiv}, primaryClass={cs.FL}, url={https://arxiv.org/pdf/2212.00751.pdf}, note = {\url{https://arxiv.org/pdf/2212.00751.pdf}} } @article{kousha, doi = {10.48550/ARXIV.1201.2374}, url = {https://arxiv.org/abs/1201.2374}, author = {Etessami, Kousha and Stewart, Alistair and Yannakakis, Mihalis}, keywords = {Computational Complexity (cs.CC), FOS: Computer and information sciences, FOS: Computer and information sciences}, title = {Polynomial Time Algorithms for Multi-Type Branching Processes and Stochastic Context-Free Grammars}, publisher = {arXiv}, year = {2012}, copyright = {arXiv.org perpetual, non-exclusive license} } @article{gec, title={Odkrivanje enačb za celoštevilska zaporedja z verjetnostnimi gramatikami: magistrsko delo}, url={https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=slv&id=131669}, abstractNote={Algoritmi za odkrivanje enačb, ki uporabljajo verjetnostne gramatike, delujejo tako, da najprej vzorčijo strukture izrazov iz gramatike in nato na podlagi teh poiščejo enačbe, ki se najbolj prilegajo vhodnim podatkom. Strukture izrazov vzorčijo na podlagi verjetnosti, ki jih določa verjetnostna gramatika. Problem, ki ga srečamo pri tem je, da želimo tvoriti samo končne strukture in želimo imeti ustrezno verjetnostno porazdelitev na množici vseh možnih končnih struktur izrazov, ki jih tvori gramatika. Na srečo lahko v ta namen na verjetnostne gramatike gledamo kot na večtipske procese razvejanja. Za te obstaja izrek, ki pod določenimi pogoji pove, kdaj lahko ustrezno porazdelitev definiramo in kdaj ne. Poleg tega v magistrskem delu razvijem empirično okolje, ki omogoča uporabo omenjenih algoritmov za odkrivanje enačb v celoštevilskih zaporedjih iz Spletne enciklopedije celoštevilskih zaporedij (OEIS). Uporabo okolja ilustriram na odkrivanju enačb za štirinajst izbranih zaporedij iz OEIS.}, author={Gec, Boštjan}, year={2021}} @article{wang, author = {Xiaofeng Wang and Guo Li and Ling Yang and Hanling Lin}, title = {Groups With Two Generators Having Unsolvable Word Problem and Presentations of Mihailova Subgroups of Braid Groups}, journal = {Communications in Algebra}, volume = {44}, number = {7}, pages = {3020-3037}, year = {2016}, publisher = {Taylor & Francis}, doi = {10.1080/00927872.2015.1065867}, URL = { https://www.tandfonline.com/doi/abs/10.1080/00927872.2015.1065867 }, eprint = { https://www.tandfonline.com/doi/pdf/10.1080/00927872.2015.1065867 } } @article{borisov, doi = {10.1007/bf01101402}, url = {https://doi.org/10.1007/bf01101402}, year = {1969}, month = nov, publisher = {Springer Science and Business Media {LLC}}, volume = {6}, number = {5}, pages = {768--775}, author = {V. V. Borisov}, title = {Simple examples of groups with unsolvable word problem}, journal = {Mathematical Notes of the Academy of Sciences of the {USSR}} } @book{slucajni-proces, title={Multitype branching processes: theory and applications}, author={Mode, C.}, isbn={9780024038500}, url={https://books.google.si/books?id=cD3VzgEACAAJ}, year={1971} } @article{boone, title={An algebraic characterization of groups with soluble word problem1}, author={Boone, William W and Higman, Graham}, journal={Journal of the Australian Mathematical Society}, volume={18}, number={1}, pages={41--53}, year={1974}, publisher={Cambridge University Press} } @article{proged, title = {Probabilistic grammars for equation discovery}, journal = {Knowledge-Based Systems}, volume = {224}, pages = {107077}, year = {2021}, issn = {0950-7051}, doi = {https://doi.org/10.1016/j.knosys.2021.107077}, url = {https://www.sciencedirect.com/science/article/pii/S0950705121003403}, author = {Jure Brence and Ljupčo Todorovski and Sašo Džeroski}, keywords = {Equation discovery, Symbolic regression, Automated modeling, Grammar, Probabilistic context-free grammar, Monte-Carlo}, abstract = {Equation discovery, also known as symbolic regression, is a type of automated modeling that discovers scientific laws, expressed in the form of equations, from observed data and expert knowledge. Deterministic grammars, such as context-free grammars, have been used to limit the search spaces in equation discovery by providing hard constraints that specify which equations to consider and which not. In this paper, we propose the use of probabilistic context-free grammars in equation discovery. Such grammars encode soft constraints, specifying a prior probability distribution on the space of possible equations. We show that probabilistic grammars can be used to elegantly and flexibly formulate the parsimony principle, that favors simpler equations, through probabilities attached to the rules in the grammars. We demonstrate that the use of probabilistic, rather than deterministic grammars, in the context of a Monte-Carlo algorithm for grammar-based equation discovery, leads to more efficient equation discovery. Finally, by specifying prior probability distributions over equation spaces, the foundations are laid for Bayesian approaches to equation discovery.} } @misc{primozic, title={P(Expression|Grammar): Probability of deriving an algebraic expression with a probabilistic context-free grammar}, author={Urh Primožič and Ljupčo Todorovski and Matej Petković}, year={2022}, eprint={2212.00751}, archivePrefix={arXiv}, primaryClass={cs.FL} } @BOOK{petkovsek, title = "A = {B}", author = "Petkovsek, Marko and Wilf, Herbert S and Zeilberger, Doron", publisher = "A K Peters", month = jan, year = {1996}, address = "Natick, MA" } @article{probabilistic-grammars, title={Probabilistic languages: A review and some open questions}, author={Wetherell, Charles S}, journal={ACM Computing Surveys (CSUR)}, volume={12}, number={4}, pages={361--379}, year={1980}, publisher={ACM New York, NY, USA} } @article{richardson, title={Some undecidable problems involving elementary functions of a real variable}, volume={33}, DOI={10.2307/2271358}, number={4}, journal={Journal of Symbolic Logic}, publisher={Cambridge University Press}, author={Richardson, Daniel}, year={1969}, pages={514–520}} @article{chi, author = {Chi, Zhiyi}, year = {2002}, month = {07}, pages = {}, title = {Statistical Properties of Probabilistic Context-Free Grammars}, volume = {25}, journal = {Computational Linguistics} }