Equality Sets and Complexity Classes

DOI10.1137/0209057MaRDI QIDQ3891770zbMATH OpenOpenAlexFDO

Authors Ronald V. Book, Franz J. Brandenburg

Publication date 1980

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

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

zbMATH Keywords

balance of homomorphismscomplete twin shuffle languagecomplexity classes of formal languagesequality setsspace boundstime bounds

Mathematics Subject Classification ID

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

Cited in

(9)

• Representations of language families by homomorphic equality operations and generalized equality sets
• Multiple equality sets and Post machines
• 2DST mappings of languages and related problems
• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• Flatwords and Post Correspondence Problem
• Checking sets, test sets, rich languages and commutatively closed languages
• scientific article; zbMATH DE number 3808971 (Why is no real title available?)
• Uniform simulations of nondeterministic real time multitape turing machines
• A homomorphic characterization of time and space complexity classes of languages†

This page was built for publication: Equality Sets and Complexity Classes

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