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

DOI10.1016/0304-3975(93)90325-NzbMath0793.68090OpenAlexW2017795761MaRDI QIDQ685373

Stefan Jarominek, Juhani Karhumäki, Wojciech Rytter

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

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

Related Items (2)

Polynomial size test sets for commutative languages ⋮ Finite transducers and rational transductions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The decidability of equivalence for deterministic finite transducers
• The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids
• On binary equality sets and a solution to the test set conjecture in the binary case
• A proof of Ehrenfeucht's conjecture
• Test sets and checking words for homomorphism equivalence
• On the decidability of homomorphism equivalence for languages
• Test sets for context free languages and algebraic systems of equations over a free monoid
• A note on finite-valued and finitely ambiguous transducers

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