scientific article; zbMATH DE number 3808971

MaRDI QIDQ3657451zbMATH OpenFDO

Authors Andreas Brandstädt

Publication date 1983

Full work available at URL https://eudml.org/doc/92180

zbMATH Keywords

checking stack languagescontext-free languageserasing bounded transducersone-counter languagesspace complexity classes

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• A homomorphic characterization of time and space complexity classes of languages†
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• Characterizations of transductions defined by abstract families of transducers
• Counter machines and counter languages
• Equality Sets and Complexity Classes
• scientific article; zbMATH DE number 3642709 (Why is no real title available?)
• scientific article; zbMATH DE number 3509706 (Why is no real title available?)
• scientific article; zbMATH DE number 3302285 (Why is no real title available?)
• On the Tape Complexity of Deterministic Context-Free Languages
• Optimization of LR(k) parsers
• Quasi-realtime languages
• Remarks on the complexity of nondeterministic counter languages
• Reversal-Bounded Acceptors and Intersections of Linear Languages
• Reversal-bounded multipushdown machines
• Time- and tape-bounded Turing acceptors and AFLs
• Translational lemmas, polynomial time, and \((\log n)^j\)-space

This page was built for publication:

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