Efficient constructions of test sets for regular and context-free languages
type: Item
instance of: scholarly article
title: Efficient constructions of test sets for regular and context-free languages
zbMATH Open document ID: 0793.68090
DOI: 10.1016/0304-3975(93)90325-N
author: Juhani Karhumäki
author: Wojciech Rytter
author: Stefan Jarominek
published in: Theoretical Computer Science
publication date: 1993-10-25T00:00:00Z
review text: 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.
reviewed by: Juraj Hromkovič
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 417327
zbMATH Keywords: finite automata
zbMATH Keywords: context-free grammars
zbMATH Keywords: formal language theory
zbMATH Keywords: test sets
zbMATH Keywords: regular languages
MaRDI profile type: Publication
cites work: Test sets for context free languages and algebraic systems of equations over a free monoid
cites work: A proof of Ehrenfeucht's conjecture
cites work: The decidability of equivalence for deterministic finite transducers
cites work: Q3355232
cites work: On the decidability of homomorphism equivalence for languages
cites work: Test sets and checking words for homomorphism equivalence
cites work: On binary equality sets and a solution to the test set conjecture in the binary case
cites work: A note on finite-valued and finitely ambiguous transducers
cites work: Q3862379
cites work: The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids
cites work: Q3769982
cites work: Q4125823
cites work: Q3948608
full work available at URL: 0304-3975(93)90325-n
OpenAlex ID: W2017795761
description: scientific article; zbMATH DE number 417327