Efficient constructions of test sets for regular and context-free languages (Q685373)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 417327
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Efficient constructions of test sets for regular and context-free languages |
scientific article; zbMATH DE number 417327 |
Statements
Efficient constructions of test sets for regular and context-free languages (English)
0 references
25 October 1993
0 references
This paper involves a nice contribution to a formal language theory. It has been known (Ehrenfeucht conjecture) that, for any language \(L\), there exists a finite test set \(F_ L\) (for each pair of morphisms, if they agree on \(F_ L\), then they agree on the whole set \(L\)). Here, a simple construction of linear size test sets for regular languages and of single exponential test sets for context-free languages is presented. This essentially improves the best known upper bounds: exponential for regular and doubly exponential for context-free languages.
0 references
finite automata
0 references
context-free grammars
0 references
formal language theory
0 references
test sets
0 references
regular languages
0 references
0 references
0.8407371640205383
0 references
0.8324581384658813
0 references
