Asymptotic approximation by regular languages
From MaRDI portal
Publication:831785
DOI10.1007/978-3-030-67731-2_6zbMATH Open1490.68129arXiv2008.01413OpenAlexW3127872916MaRDI QIDQ831785FDOQ831785
Authors: Ryoma Sin'ya 
Publication date: 24 March 2022
Abstract: This paper investigates a new property of formal languages called REG-measurability where REG is the class of regular languages. Intuitively, a language (L) is REG-measurable if there exists an infinite sequence of regular languages that "converges" to (L). A language without REG-measurability has a complex shape in some sense so that it can not be (asymptotically) approximated by regular languages. We show that several context-free languages are REG-measurable (including languages with transcendental generating function and transcendental density, in particular), while a certain simple deterministic context-free language and the set of primitive words are REG-immeasurable in a strong sense.
Full work available at URL: https://arxiv.org/abs/2008.01413
Recommendations
- Rough approximations in varieties of regular languages
- On approximating non-regular languages by regular languages
- On the accuracy of rough approximations of regular languages
- scientific article; zbMATH DE number 7439745
- scientific article; zbMATH DE number 222191
- scientific article; zbMATH DE number 2080921
- Towards a theory of complexity of regular languages
- Approximate automata for omega-regular languages
- On the density of regular languages
- scientific article; zbMATH DE number 7533339
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- The Measure Theoretic Approach to Density
- Minimal cover-automata for finite languages
- Analytic models and ambiguity of context-free languages
- Some properties of disjunctive languages on a free monoid
- Title not available (Why is that?)
- Prefixes of infinite words and ambiguous context-free languages
- On the existence of regular approximations
- Title not available (Why is that?)
- A note on the density of inherently ambiguous context-free languages
- Succinct representations of languages by DFA with different levels of reliability
- On Approximating Non-regular Languages by Regular Languages
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (11)
- Regular Approximation of Weighted Linear Context-Free Tree Languages
- On primitive words with non-primitive product
- Carathéodory extensions of subclasses of regular languages
- Asymptotical behaviour of some non-uniform measures
- Title not available (Why is that?)
- On the existence of regular approximations
- Measuring power of generalised definite languages
- Measuring power of locally testable languages
- Implementation and Application of Automata
- Measuring power of commutative group languages
- Title not available (Why is that?)
This page was built for publication: Asymptotic approximation by regular languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q831785)
