On the Efficient Generation of Language Instances

DOI10.1137/0219019MaRDI QIDQ3034825zbMATH OpenOpenAlexFDO

Authors Laura A. Sanchis, Mark A. Fulk

Publication date 1990

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0219019

zbMATH Keywords

constructorgeneratorNPoraclesPolynomial-time Turing machinessparse languages

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On an Effective Construction of a Grammar Generating a Given Language
• Language generation and recognition over terms
• scientific article; zbMATH DE number 3978431
• CONSTRUCTING LANGUAGE INSTANCES BASED ON PARTIAL INFORMATION
• Uniform generation of languages by scattered context grammars
• scientific article; zbMATH DE number 108497
• GENERATION OF LANGUAGES BY REWRITING SYSTEMS THAT RESEMBLE AUTOMATA
• scientific article; zbMATH DE number 3976291
• scientific article; zbMATH DE number 2149593
• Fixed point generation of varieties of languages

Cited in

(11)

• The complexity of computing maximal word functions
• Language sampling for universal grammars
• On the effective generation of set elements within specified ranges
• EFFICIENT DETECTORS AND CONSTRUCTORS FOR SIMPLE LANGUAGES
• CONSTRUCTING LANGUAGE INSTANCES BASED ON PARTIAL INFORMATION
• On languages accepted with simultaneous complexity bounds and their ranking problem
• Beginner's luck: a language for property-based generators
• Language generation and recognition over terms
• Folding schemes with privacy preserving selective verification
• On small generators
• On the complexity of test case generation for NP-hard problems

This page was built for publication: On the Efficient Generation of Language Instances

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