Efficient constructions of test sets for regular and context-free languages

DOI10.1016/0304-3975(93)90325-NMaRDI QIDQ685373zbMATH OpenOpenAlexFDO

Authors Juhani Karhumäki, Wojciech Rytter, Stefan Jarominek

Publication date 25 October 1993

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(93)90325-n

zbMATH Keywords

context-free grammarsfinite automataformal language theoryregular languagestest sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

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.

Recommendations

• scientific article; zbMATH DE number 176145
• scientific article; zbMATH DE number 777280
• Polynomial size test sets for context-free languages
• Polynomial size test sets for context-free languages
• scientific article; zbMATH DE number 3883627

Cites work

• A note on finite-valued and finitely ambiguous transducers
• A proof of Ehrenfeucht's conjecture
• scientific article; zbMATH DE number 4205980 (Why is no real title available?)
• scientific article; zbMATH DE number 4028926 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3767067 (Why is no real title available?)
• scientific article; zbMATH DE number 3551946 (Why is no real title available?)
• On binary equality sets and a solution to the test set conjecture in the binary case
• On the decidability of homomorphism equivalence for languages
• Test sets and checking words for homomorphism equivalence
• Test sets for context free languages and algebraic systems of equations over a free monoid
• The decidability of equivalence for deterministic finite transducers
• The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids

Cited in

(19)

• On test sets for checking morphism equivalence on languages with fair distribution of letters
• A graph-based regularity test for deterministic context-free languages
• Test sets for the universal and existential closure of regular tree languages.
• Explicit test sets for iterated morphisms in free monoids and metabelian groups
• Polynomial size test sets for context-free languages
• Finite transducers and rational transductions
• The size of Higman-Haines sets
• Linear size test sets for certain commutative languages
• scientific article; zbMATH DE number 3866597 (Why is no real title available?)
• Parikh test sets for commutative languages
• scientific article; zbMATH DE number 4091490 (Why is no real title available?)
• EFFICIENT DETECTORS AND CONSTRUCTORS FOR SIMPLE LANGUAGES
• scientific article; zbMATH DE number 176145 (Why is no real title available?)
• Polynomial size test sets for commutative languages
• scientific article; zbMATH DE number 1114045 (Why is no real title available?)
• scientific article; zbMATH DE number 1916668 (Why is no real title available?)
• Polynomial size test sets for context-free languages
• More on the Size of Higman-Haines Sets: Effective Constructions
• More on the Size of Higman-Haines Sets: Effective Constructions

This page was built for publication: Efficient constructions of test sets for regular and context-free languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685373)