2DST mappings of languages and related problems
From MaRDI portal
Publication:1164438
DOI10.1016/0304-3975(82)90061-5zbMath0485.68072OpenAlexW2080256878MaRDI QIDQ1164438
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
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
Related Items (6)
The equivalence of finite valued transducers (on HDT0L languages) is decidable ⋮ The equivalence problem for deterministic MSO tree transducers 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 ⋮ A note on Parikh maps, abstract languages, and decision problems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Test sets and checking words for homomorphism equivalence
- The complexity of decision problems for finite-turn multicounter machines
- Reversal-bounded multipushdown machines
- A useful device for showing the solvability of some decision problems
- One way finite visit automata
- On the decidability of homomorphism equivalence for languages
- Some decidability results about regular and pushdown translations
- Controlled pushdown automata
- Checking automata and one-way stack languages
- A hierarchy between context-free and context-sensitive languages
- Finite-turn checking automata
- AFL with the semilinear property
- Absolutely parallel grammars and two-way finite-state transducers
- A homomorphic characterization of time and space complexity classes of languages†
- Equality Sets and Complexity Classes
- A Remark on Code Sets and Context-Free Languages
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- A Purely Homomorphic Characterization of Recursively Enumerable Sets
- Homomorphism equivalence on etol languages†
- Bounded Algol-Like Languages
- Multi-tape and multi-head pushdown automata
- Programmed Grammars and Classes of Formal Languages
- Simple matrix languages
This page was built for publication: 2DST mappings of languages and related problems
