2DST mappings of languages and related problems

DOI10.1016/0304-3975(82)90061-5MaRDI QIDQ1164438zbMATH OpenOpenAlexFDO

Authors Oscar H. Ibarra

Publication date 1982

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(82)90061-5

zbMATH Keywords

effectively constructible semilinear Parikh mapsfamily of languages effectively closed under inverse homomorphism and intersection with regular setsone-way nondeterministic multicounter machinetwo-way deterministic sequential transducers

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• A hierarchy between context-free and context-sensitive languages
• A homomorphic characterization of time and space complexity classes of languages†
• A Purely Homomorphic Characterization of Recursively Enumerable Sets
• A Remark on Code Sets and Context-Free Languages
• A useful device for showing the solvability of some decision problems
• Absolutely parallel grammars and two-way finite-state transducers
• AFL with the semilinear property
• Bounded Algol-Like Languages
• Checking automata and one-way stack languages
• Controlled pushdown automata
• Equality Sets and Complexity Classes
• Finite-turn checking automata
• Homomorphism equivalence on etol languages†
• scientific article; zbMATH DE number 3633742 (Why is no real title available?)
• scientific article; zbMATH DE number 3336816 (Why is no real title available?)
• Multi-tape and multi-head pushdown automata
• On the decidability of homomorphism equivalence for languages
• One way finite visit automata
• Programmed Grammars and Classes of Formal Languages
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• Reversal-bounded multipushdown machines
• Simple matrix languages
• Some decidability results about regular and pushdown translations
• Test sets and checking words for homomorphism equivalence
• The complexity of decision problems for finite-turn multicounter machines

Cited in

(6)

• A note on Parikh maps, abstract languages, and decision problems
• The equivalence of finite valued transducers (on HDT0L languages) is decidable
• Equivalence problem of mappings relative to languages
• The equivalence of deterministic gsm replications onQ-rational languages is decidable
• On some transducer equivalence problems for families of languages
• The equivalence problem for deterministic MSO tree transducers is decidable

Describes a project that uses

Uses Software

• ALGOL 60

This page was built for publication: 2DST mappings of languages and related problems

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