Classes of regular and context-free languages over countably infinite alphabets (Q1068559): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Langages sur des alphabets infinis / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3859267 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4079524 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198075 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5592246 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Rekursive Wortfunktionen Über Unendlichen Alphabeten / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4044553 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 10:24, 17 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Classes of regular and context-free languages over countably infinite alphabets |
scientific article |
Statements
Classes of regular and context-free languages over countably infinite alphabets (English)
0 references
1985
0 references
For a countably infinite alphabet \(\Delta\), the classes Reg(\(\Delta)\) of regular languages and CFL(\(\Delta)\) of context-free languages over \(\Delta\) are defined by way of an encoding. All the languages contained in these classes are decidable, and these classes do have many properties in common with the class of regular languages Reg(\(\Sigma)\) and the class of context-free languages CFL(\(\Sigma)\), respectively, where \(\Sigma\) is a finite alphabet. In particular, each of these classes can be characterized in a semantical way by a certain type of automata over \(\Delta\). Finally, the classes Reg(\(\Delta)\) and CFL(\(\Delta)\) are compared to the classes of languages over \(\Delta\) that are defined by Autebert, Beauquier, and Boasson.
0 references
regular languages
0 references
context-free languages
0 references