{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,15]],"date-time":"2022-12-15T06:32:59Z","timestamp":1671085979752},"reference-count":13,"publisher":"World Scientific Pub Co Pte Ltd","issue":"08","funder":[{"name":"Slovak Scientific Grant Agency VEGA","award":["1\/0601\/20"],"award-info":[{"award-number":["1\/0601\/20"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:p> A new framework to measure distances (similarity) between formal languages and between grammars based on distances between words is introduced. It is based on approximating languages by their finite subsets and using monotone sequences of such finite approximations to define an infinite language in the limit. Distances between finite languages are defined and extended to distances between monotone sequences of finite languages leading to distances between infinite languages. The framework captures several distances studied in the literature. <\/jats:p><jats:p> Context-free grammars with energy are introduced to enable finite approximations emphasizing \u201csyntactically important\u201d parts of words. Grammars with energy are also used to extend distances between monotone sequences of finite languages to distances between context-free grammars. <\/jats:p><jats:p> A basic toolkit for monotone sequences of finite languages and distances between languages resp. grammars is provided. As part of this toolkit a non-symmetric version of distances is defined, providing additional characterisation of distances in general. Additional properties of distances between grammars are derived by restricting the\u201cenergy use\u201d of grammars with energy. <\/jats:p><jats:p> Some methods of estimating the distances are presented to be used in cases where the distance is not computable or difficult to compute. <\/jats:p>","DOI":"10.1142\/s0129054122500113","type":"journal-article","created":{"date-parts":[[2022,5,29]],"date-time":"2022-05-29T15:19:41Z","timestamp":1653837581000},"page":"967-1003","source":"Crossref","is-referenced-by-count":0,"title":["Finite Approximations and Similarity of Languages"],"prefix":"10.1142","volume":"33","author":[{"given":"Branislav","family":"Rovan","sequence":"first","affiliation":[{"name":"Department of Computer Science, Faculty of Mathematics, Physics and Informatics, Comenius University in Bratislava, Mlynsk\u00e1 dolina, 842 48 Bratislava, Slovak Republic"}]},{"given":"Andr\u00e1s","family":"Varga","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Faculty of Mathematics, Physics and Informatics, Comenius University in Bratislava, Mlynsk\u00e1 dolina, 842 48 Bratislava, Slovak Republic"}]}],"member":"219","published-online":{"date-parts":[[2022,5,28]]},"reference":[{"key":"S0129054122500113BIB002","series-title":"Automata, Languages, and Programming","volume-title":"Edit Distance for Pushdown Automata","author":"Chatterjee K.","year":"2015"},{"key":"S0129054122500113BIB005","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-030-24886-4_8","volume-title":"Input-Driven Pushdown Automata for Edit Distance Neighborhood","author":"Geffert V.","year":"2019"},{"key":"S0129054122500113BIB006","series-title":"Implementation and Application of Automata","volume-title":"Alignment Distance of Regular Tree Languages","author":"Han Y.-S.","year":"2017"},{"key":"S0129054122500113BIB007","series-title":"SOFSEM 2017: Theory and Practice of Computer Science","volume-title":"Edit-Distance Between Visibly Pushdown Languages","author":"Han Y.-S.","year":"2017"},{"key":"S0129054122500113BIB008","series-title":"Implementation and Application of Automata","volume-title":"Approximate Matching between a Context-Free Grammar and a Finite-State Automaton","author":"Han Y.-S.","year":"2013"},{"key":"S0129054122500113BIB010","series-title":"Developments in Language Theory","volume-title":"Computing the Edit-Distance between a Regular Language and a Context-Free Language","author":"Han Y.-S.","year":"2012"},{"key":"S0129054122500113BIB011","series-title":"Language and Automata Theory and Applications","volume-title":"Top-Down Tree Edit-Distance of Regular Tree Languages","author":"Han Y.-S.","year":"2014"},{"key":"S0129054122500113BIB020","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-04298-5_37","volume-title":"Parameterized Prefix Distance between Regular Languages","author":"Kutrib M.","year":"2014"},{"key":"S0129054122500113BIB022","series-title":"Implementation and Application of Automata","volume-title":"Prefix Distance Between Regular Languages","author":"Ng T.","year":"2016"},{"key":"S0129054122500113BIB023","series-title":"Developments in Language Theory","volume-title":"Relative Prefix Distance Between Languages","author":"Ng T.","year":"2017"},{"key":"S0129054122500113BIB024","series-title":"Implementation and Application of Automata","volume-title":"State Complexity of Prefix Distance","author":"Ng T.","year":"2015"},{"key":"S0129054122500113BIB025","series-title":"Computer Science\u2014 Theory and Applications","volume-title":"Edit Distance Neighbourhoods of Input-Driven Pushdown Automata","author":"Okhotin A.","year":"2017"},{"key":"S0129054122500113BIB026","volume-title":"Descriptive Complexity of the Hamming Neighborhood of a Regular Language","author":"Povarov G.","year":"2007"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054122500113","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,14]],"date-time":"2022-12-14T03:47:42Z","timestamp":1670989662000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054122500113"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,28]]},"references-count":13,"journal-issue":{"issue":"08","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["10.1142\/S0129054122500113"],"URL":"https:\/\/doi.org\/10.1142\/s0129054122500113","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,28]]}}}