Asymptotic approximation by regular languages
From MaRDI portal
Publication:831785
DOI10.1007/978-3-030-67731-2_6zbMATH Open1490.68129arXiv2008.01413OpenAlexW3127872916MaRDI QIDQ831785FDOQ831785
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
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
- Prefixes of infinite words and ambiguous context-free languages
- On the existence of regular approximations
- 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
Cited In (9)
- Regular Approximation of Weighted Linear Context-Free Tree Languages
- On primitive words with non-primitive product
- Carathéodory extensions of subclasses of regular languages
- Title not available (Why is that?)
- 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?)
Recommendations
- Rough approximations in varieties of regular languages 👍 👎
- On the Accuracy of Rough Approximations of Regular Languages 👍 👎
- On Approximating Non-regular Languages by Regular Languages 👍 👎
- Approximate Automata for Omega-Regular Languages 👍 👎
- On the Density of Regular Languages 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- 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)
