On regularity of context-free languages
From MaRDI portal
This paper considers conditions under which a context-free language is regular and conditions which imposed on (productions of) a rewriting system generating a context-free language will guarantee that the generated language is regular. In particular: (1) necessary and sufficient conditions on productions of a unitary grammar are given that guarantee the generated language to be regular (a unitary grammar is a semi-Thue system in which the left-hand of each production is the empty word), and (2) it is proved that commutativity of a linear language implies its regularity. To obtain the former result, we give a generalization of the Myhill-Nerode characterization of the regular languages in terms of well-quasi orders, along with a generalization of Higman's well-quasi order result concerning the subsequence embedding relation on \(\Sigma^*\). In obtaining the latter results, we introduce the class of periodic languages, and demonstrate how they can be used to characterize the commutative regular languages. Here we also utilize the theory of well-quasi orders.
Recommendations
Cites work
- Cônes rationnels commutatifs
- scientific article; zbMATH DE number 3677223 (Why is no real title available?)
- scientific article; zbMATH DE number 3780588 (Why is no real title available?)
- scientific article; zbMATH DE number 3634526 (Why is no real title available?)
- scientific article; zbMATH DE number 3639163 (Why is no real title available?)
- scientific article; zbMATH DE number 3238653 (Why is no real title available?)
- scientific article; zbMATH DE number 3323852 (Why is no real title available?)
- scientific article; zbMATH DE number 3366846 (Why is no real title available?)
- scientific article; zbMATH DE number 3413820 (Why is no real title available?)
- scientific article; zbMATH DE number 3198033 (Why is no real title available?)
- Insertion languages
- Linear Automaton Transformations
- Monadic Thue systems
- On basic properties of DOS systems and languages
- On free monoids partially ordered by embedding
- Ordering by Divisibility in Abstract Algebras
- Recursive unsolvability of a problem of Thue
- Scattered context grammars
- The theory of well-quasi-ordering: a frequently discovered concept
- Une généralisation des ensembles de Dyck
- Well-quasi-orderings and sets of finite sequences
Cited in
(78)- Testing avoidability on sets of partial words is hard
- A regularity test for dual bordered OS systems
- Classes of regular and context-free languages over countably infinite alphabets
- Another generalization of Higman's well quasi order result on ^*
- Rational languages and the Burnside problem
- On total regulators generated by derivation relations
- Concerning two-adjacent context-free languages
- On the context-free production complexity of finite languages
- Termination of rewriting
- Using unavoidable set of trees to generalize Kruskal's theorem
- Inventories of unavoidable languages and the word-extension conjecture
- On the regularity of languages on a binary alphabet generated by copying systems
- On quasi orders of words and the confluence property
- On an extension of the class of context-free languages
- Well quasi-orders and regular languages
- Well-quasi-orders and regular \(\omega\)-languages
- On the rational subsets of the free group
- Finite language forbidding-enforcing systems
- Language equations
- Commutative regular languages with product-form minimal automata
- Regularity conditions for iterated shuffle on commutative regular languages
- Automata-theoretical regularity characterizations for the iterated shuffle on commutative regular languages
- Well quasi-orders arising from finite ordered semigroups
- Hybrid and generalized marked systems
- On the expressivity of time-varying graphs
- Characterization and complexity results on jumping finite automata
- On square-increasing ordered monoids and idempotent semirings
- Finite turns and the regular closure of linear context-free languages
- The size of Higman-Haines sets
- Regular solutions of language inequalities and well quasi-orders
- Two results on discontinuous input processing
- Jumping finite automata: characterizations and complexity
- Minimum number of holes in unavoidable sets of partial words of size three
- Regular and Context-Free Pattern Languages over Small Alphabets
- Kleene Closure on Regular and Prefix-Free Languages
- Well-Quasi Orders and Hierarchy Theory
- Injective envelopes of transition systems and Ferrers languages
- Well quasi-orders, unavoidable sets, and derivation systems
- On the degree of non-regularity of context-free languages
- Well Quasi-orders in Formal Language Theory
- On the Density of Regular and Context-Free Languages
- scientific article; zbMATH DE number 3911731 (Why is no real title available?)
- Generalized cancellation-and-permutation properties, regular languages and supports of rational series
- Two complexity measures for context-free languages
- scientific article; zbMATH DE number 611232 (Why is no real title available?)
- scientific article; zbMATH DE number 2013205 (Why is no real title available?)
- scientific article; zbMATH DE number 2040909 (Why is no real title available?)
- scientific article; zbMATH DE number 2051170 (Why is no real title available?)
- Number of holes in unavoidable sets of partial words. I.
- On basic properties of jumping finite automata
- Unavoidable Set: Extension and Reduction
- Every commutative quasirational language is regular
- On the commutative equivalence of bounded context-free and regular languages: the code case
- scientific article; zbMATH DE number 1822166 (Why is no real title available?)
- scientific article; zbMATH DE number 2102747 (Why is no real title available?)
- Unavoidable languages, cuts and innocent sets of words
- Embedding with patterns and associated recursive path ordering
- On the unavoidability of primitive words and other languages
- scientific article; zbMATH DE number 7561705 (Why is no real title available?)
- scientific article; zbMATH DE number 5205535 (Why is no real title available?)
- scientific article; zbMATH DE number 5251101 (Why is no real title available?)
- Regular Realizability Problems and Context-Free Languages
- scientific article; zbMATH DE number 2213327 (Why is no real title available?)
- Semigroups satisfying x m+n = x n
- A characterization of (regular) circular languages generated by monotone complete splicing systems
- State complexity bounds for the commutative closure of group languages
- Regularity Conditions for Iterated Shuffle on Commutative Regular Languages
- INTERLEAVING LOGIC AND COUNTING
- Finite embeddability property for residuated lattices via regular languages
- Language inclusion algorithms as complete abstract interpretations
- Characterization of ordered semigroups generating well quasi-orders of words
- State complexity bounds for projection, shuffle, up- and downward closure and interior on commutative regular languages
- How to demonstrate metalinearness and regularity by tree-restricted general grammars
- Well quasi-orders and context-free grammars
- Unavoidable sets and circular splicing languages
- Unavoidable sets of partial words
- Insertion languages
- Well quasi-orders generated by a word-shuffle rewriting
This page was built for publication: On regularity of context-free languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q759489)
