On inverse deterministic pushdown transductions

DOI10.1016/0022-0000(78)90028-4zbMath0376.68051OpenAlexW2038503876MaRDI QIDQ1245575

Walter J. Savitch, Paul M. B. Vitányi

Publication date: 1978

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(78)90028-4

Mathematics Subject Classification ID

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

Related Items

On characterizations of recursively enumerable languages ⋮ A note on dpda transductions of {0,1}^∗and inverse dpda transductions of the dyck set

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Space-bounded reducibility among combinatorial problems
• Relationships between nondeterministic and deterministic tape complexities
• How to Make Arbitrary Grammars Look Like Context-Free Grammars
• A universal context-free grammar
• On the Tape Complexity of Deterministic Context-Free Languages
• The Hardest Context-Free Language
• Jump PDA’s and Hierarchies of Deterministic Context-Free Languages
• Abstract families of deterministic languages
• Deterministic context free languages
• Two-way pushdown automata
• The theory of languages
• Recognition time of context-free languages by on-line Turing machines
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers