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 automataregular languagestest setsformal language theory

Mathematics Subject Classification ID

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

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

• 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?)
• A note on finite-valued and finitely ambiguous transducers
• A proof of Ehrenfeucht's conjecture
• 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 Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids
• The decidability of equivalence for deterministic finite transducers

Cited in

(17)

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

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)