On regularity of context-free languages
From MaRDI portal
Publication:759489
DOI10.1016/0304-3975(82)90124-4zbMath0553.68044OpenAlexW1989943994WikidataQ126298324 ScholiaQ126298324MaRDI QIDQ759489
Andrzej Ehrenfeucht, Grzegorz Rozenberg, David Haussler
Publication date: 1983
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(82)90124-4
context-free languagerewriting systemregular languagescommutativitysemi-Thue systemisertion languageiterative pairlinear languageperiodic languagespure squaressubword completeunitary grammarwell-quasi orders
Related Items (53)
Semigroups satisfying x m+n = x n ⋮ Rational languages and the Burnside problem ⋮ On square-increasing ordered monoids and idempotent semirings ⋮ On total regulators generated by derivation relations ⋮ Well-quasi-orders and regular \(\omega\)-languages ⋮ Well quasi-orders and regular languages ⋮ Embedding with patterns and associated recursive path ordering ⋮ Termination of rewriting ⋮ Automata-theoretical regularity characterizations for the iterated shuffle on commutative regular languages ⋮ Well quasi-orders arising from finite ordered semigroups ⋮ On the degree of non-regularity of context-free languages ⋮ Using unavoidable set of trees to generalize Kruskal's theorem ⋮ A characterization of (regular) circular languages generated by monotone complete splicing systems ⋮ On the rational subsets of the free group ⋮ Inventories of unavoidable languages and the word-extension conjecture ⋮ Well quasi-orders generated by a word-shuffle rewriting ⋮ Jumping Finite Automata: Characterizations and Complexity ⋮ Regularity Conditions for Iterated Shuffle on Commutative Regular Languages ⋮ Unavoidable languages, cuts and innocent sets of words ⋮ INTERLEAVING LOGIC AND COUNTING ⋮ Finite embeddability property for residuated lattices via regular languages ⋮ Unnamed Item ⋮ Number of holes in unavoidable sets of partial words. I. ⋮ Well Quasi-orders in Formal Language Theory ⋮ Well-Quasi Orders and Hierarchy Theory ⋮ Injective envelopes of transition systems and Ferrers languages ⋮ Minimum Number of Holes in Unavoidable Sets of Partial Words of Size Three ⋮ Generalized cancellation-and-permutation properties, regular languages and supports of rational series ⋮ On Basic Properties of Jumping Finite Automata ⋮ The size of Higman-Haines sets ⋮ Two complexity measures for context-free languages ⋮ Hybrid and generalized marked systems ⋮ Unnamed Item ⋮ On the regularity of languages on a binary alphabet generated by copying systems ⋮ Well quasi-orders and context-free grammars ⋮ Finite language forbidding-enforcing systems ⋮ Unavoidable sets and circular splicing languages ⋮ Unavoidable sets of partial words ⋮ Testing avoidability on sets of partial words is hard ⋮ Unavoidable Set: Extension and Reduction ⋮ On quasi orders of words and the confluence property ⋮ Two Results on Discontinuous Input Processing ⋮ Language equations ⋮ Well quasi-orders, unavoidable sets, and derivation systems ⋮ Commutative regular languages with product-form minimal automata ⋮ Insertion languages ⋮ Regular solutions of language inequalities and well quasi-orders ⋮ A regularity test for dual bordered OS systems ⋮ Rational subsets and submonoids of wreath products. ⋮ On the expressivity of time-varying graphs ⋮ Another generalization of Higman's well quasi order result on \(\Sigma ^*\) ⋮ Regularity conditions for iterated shuffle on commutative regular languages ⋮ Characterization and complexity results on jumping finite automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Insertion languages
- Cônes rationnels commutatifs
- Monadic Thue systems
- Scattered context grammars
- Une généralisation des ensembles de Dyck
- The theory of well-quasi-ordering: a frequently discovered concept
- Linear Automaton Transformations
- On basic properties of DOS systems and languages
- Well-quasi-orderings and sets of finite sequences
- Recursive Unsolvability of a problem of Thue
- On free monoids partially ordered by embedding
- Ordering by Divisibility in Abstract Algebras
This page was built for publication: On regularity of context-free languages
