Computation of distances for regular and context-free probabilistic languages

Mark Jan Nederhof; Giorgio Satta

doi:10.1016/j.tcs.2008.01.010

Computation of distances for regular and context-free probabilistic languages

Mark Jan Nederhof, Giorgio Satta

School of Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

Several mathematical distances between probabilistic languages have been investigated in the literature, motivated by applications in language modeling, computational biology, syntactic pattern matching and machine learning. In most cases, only pairs of probabilistic regular languages were considered. In this paper we extend the previous results to pairs of languages generated by a probabilistic context-free grammar and a probabilistic finite automaton.

Original language	English
Pages (from-to)	235-254
Number of pages	20
Journal	Theoretical Computer Science
Volume	395
Issue number	2-3
DOIs	https://doi.org/10.1016/j.tcs.2008.01.010
Publication status	Published - 1 May 2008

Keywords

Probabilistic context-free languages
Probabilistic finite automata
Probabilistic language distances
Language entropy
Kullback-Leibler divergence
Relative entropy
Models

Access to Document

10.1016/j.tcs.2008.01.010

Open Access version in Research@StAndrews:FullText
This is an author version of an article published in Theoretical Computer Science 395 (2008), available at http://www.sciencedirect.com
Accepted author manuscript, 254 KB

Cite this

@article{b974c875947d4a23a26fe71ab60a58bb,

title = "Computation of distances for regular and context-free probabilistic languages",

abstract = "Several mathematical distances between probabilistic languages have been investigated in the literature, motivated by applications in language modeling, computational biology, syntactic pattern matching and machine learning. In most cases, only pairs of probabilistic regular languages were considered. In this paper we extend the previous results to pairs of languages generated by a probabilistic context-free grammar and a probabilistic finite automaton.",

keywords = "Probabilistic context-free languages, Probabilistic finite automata, Probabilistic language distances, Language entropy, Kullback-Leibler divergence, Relative entropy, Models",

author = "Nederhof, {Mark Jan} and Giorgio Satta",

year = "2008",

month = may,

day = "1",

doi = "10.1016/j.tcs.2008.01.010",

language = "English",

volume = "395",

pages = "235--254",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier Science BV",

number = "2-3",

}

TY - JOUR

T1 - Computation of distances for regular and context-free probabilistic languages

AU - Nederhof, Mark Jan

AU - Satta, Giorgio

PY - 2008/5/1

Y1 - 2008/5/1

N2 - Several mathematical distances between probabilistic languages have been investigated in the literature, motivated by applications in language modeling, computational biology, syntactic pattern matching and machine learning. In most cases, only pairs of probabilistic regular languages were considered. In this paper we extend the previous results to pairs of languages generated by a probabilistic context-free grammar and a probabilistic finite automaton.

AB - Several mathematical distances between probabilistic languages have been investigated in the literature, motivated by applications in language modeling, computational biology, syntactic pattern matching and machine learning. In most cases, only pairs of probabilistic regular languages were considered. In this paper we extend the previous results to pairs of languages generated by a probabilistic context-free grammar and a probabilistic finite automaton.

KW - Probabilistic context-free languages

KW - Probabilistic finite automata

KW - Probabilistic language distances

KW - Language entropy

KW - Kullback-Leibler divergence

KW - Relative entropy

KW - Models

UR - http://www.scopus.com/inward/record.url?scp=45849119469&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2008.01.010

DO - 10.1016/j.tcs.2008.01.010

M3 - Article

SN - 0304-3975

VL - 395

SP - 235

EP - 254

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 2-3

ER -

Computation of distances for regular and context-free probabilistic languages

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this