Equality Sets and Complexity Classes

DOI10.1137/0209057zbMath0446.68040OpenAlexW2046041498MaRDI QIDQ3891770

Ronald V. Book, Franz-Josef 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

time boundsequality setsspace boundscomplexity classes of formal languagesbalance of homomorphismscomplete twin shuffle language

Mathematics Subject Classification ID

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

Related Items (9)

Flatwords and Post Correspondence Problem ⋮ Representations of language families by homomorphic equality operations and generalized equality sets ⋮ Uniform simulations of nondeterministic real time multitape turing machines ⋮ 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 ⋮ Unnamed Item ⋮ A homomorphic characterization of time and space complexity classes of languages† ⋮ Checking sets, test sets, rich languages and commutatively closed languages

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