Classes of regular and context-free languages over countably infinite alphabets
type: Item
instance of: scholarly article
title: Classes of regular and context-free languages over countably infinite alphabets
zbMATH Open document ID: 0582.68046
DOI: 10.1016/0166-218X(85)90039-3
author: Friedrich Otto
published in: Discrete Applied Mathematics
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3932416
zbMATH Keywords: regular languages
zbMATH Keywords: context-free languages
MaRDI profile type: Publication
cites work: Langages sur des alphabets infinis
cites work: Q3859267
cites work: Q4079524
cites work: Q4198075
cites work: Q5592246
cites work: Rekursive Wortfunktionen Über Unendlichen Alphabeten
cites work: Q4044553
Recommended article: Context-free languages over infinite alphabets
Recommended article: Q4779173
Recommended article: On a subclass of \(\infty\)-regular languages
Recommended article: AN ALGEBRAIC THEORY FOR REGULAR LANGUAGES OF FINITE AND INFINITE WORDS
Recommended article: P Finite Automata and Regular Languages over Countably Infinite Alphabets
Recommended article: An algebraic characterization of deterministic regular languages over infinite alphabets.
Recommended article: A Characterisation of Languages on Infinite Alphabets with Nominal Regular Expressions
Recommended article: Fixed-point characterization of context-free ∞-languages
Recommended article: A classification of \(\omega\)-regular languages
Recommended article: On regularity of context-free languages
description: scientific article; zbMATH DE number 3932416