Asymptotic approximation by regular languages
From MaRDI portal
(Redirected from Publication:831785)
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.
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
- Approximating probabilistic automata by regular languages
Cites work
- scientific article; zbMATH DE number 3911733 (Why is no real title available?)
- scientific article; zbMATH DE number 3588051 (Why is no real title available?)
- scientific article; zbMATH DE number 2087235 (Why is no real title available?)
- scientific article; zbMATH DE number 7438576 (Why is no real title available?)
- scientific article; zbMATH DE number 2201365 (Why is no real title available?)
- scientific article; zbMATH DE number 3238653 (Why is no real title available?)
- scientific article; zbMATH DE number 3415406 (Why is no real title available?)
- A note on the density of inherently ambiguous context-free languages
- Analytic models and ambiguity of context-free languages
- Minimal cover-automata for finite languages
- On approximating non-regular languages by regular languages
- On the existence of regular approximations
- Prefixes of infinite words and ambiguous context-free languages
- Some properties of disjunctive languages on a free monoid
- Succinct representations of languages by DFA with different levels of reliability
- The Measure Theoretic Approach to Density
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
- scientific article; zbMATH DE number 522861 (Why is no real title available?)
- 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
- scientific article; zbMATH DE number 7439745 (Why is no real title available?)
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)
