On regularity of context-free languages (Q759489): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / author | |||
Property / author: David Haussler / rank | |||
Property / author | |||
Property / author: David Haussler / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(82)90124-4 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1989943994 / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q126298324 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5602108 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3873564 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Monadic Thue systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5526125 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4195154 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Une généralisation des ensembles de Dyck / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5639639 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On basic properties of DOS systems and languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3959450 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Scattered context grammars / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On free monoids partially ordered by embedding / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198075 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Insertion languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Ordering by Divisibility in Abstract Algebras / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The theory of well-quasi-ordering: a frequently discovered concept / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Cônes rationnels commutatifs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Well-quasi-orderings and sets of finite sequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5734436 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Linear Automaton Transformations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Recursive Unsolvability of a problem of Thue / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5678435 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 15:20, 14 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On regularity of context-free languages |
scientific article |
Statements
On regularity of context-free languages (English)
0 references
1983
0 references
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.
0 references
iterative pair
0 references
pure squares
0 references
isertion language
0 references
subword complete
0 references
context-free language
0 references
rewriting system
0 references
unitary grammar
0 references
semi-Thue system
0 references
commutativity
0 references
linear language
0 references
periodic languages
0 references
regular languages
0 references
well-quasi orders
0 references