On regularity of context-free languages

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

zbMATH Keywords

context-free language rewriting system regular languages commutativity semi-Thue system isertion language iterative pair linear language periodic languages pure squares subword complete unitary grammar well-quasi orders

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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

This page was built for publication: On regularity of context-free languages