On Cardinality of Bigram Languages

Abstract

We consider formal languages that are defined by matrices of bigram frequences. These languages were studied by the author on the qualitative level in the paper “On bigram languages”. Here the connections between language cardinality and initial bigram frequency matrix are investigated and asymptotic estimates of language cardinalities and of fractions of numbers of bigram frequency matrices with various properties are presented.

Publication
Discrete Mathematics and Applications
Aleksandr Petiushko Александр Петюшко
Aleksandr Petiushko Александр Петюшко
Director, Head of ML Research / Adjunct Professor / PhD

Principal R&D Researcher (15+ years of experience), R&D Technical Leader (10+ years of experience), and R&D Manager (8+ years of experience). Running and managing industrial research and academic collaboration (35+ publications, 30+ patents). Inspired by theoretical computer science and how it changes the world.