Counting problems for Parikh images
From MaRDI portal
Publication:5111226
DOI10.4230/LIPICS.MFCS.2017.12zbMATH Open1441.68124OpenAlexW2774819238MaRDI QIDQ5111226FDOQ5111226
Authors: Christoph Haase, Stefan Kiefer, Markus Lohrey 
Publication date: 26 May 2020
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8059/pdf/LIPIcs-MFCS-2017-12.pdf/
Recommendations
- On the Parikh membership problem for FAs, PDAs, and CMs
- Parikh's theorem and descriptional complexity
- Tightening the complexity of equivalence problems for commutative grammars
- Operational State Complexity under Parikh Equivalence
- Converting nondeterministic automata and context-free grammars into Parikh equivalent deterministic automata
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- PP is as Hard as the Polynomial-Time Hierarchy
- The complexity of computing the number of strings of given length in context-free languages
- On the equivalence, containment, and covering problems for the regular and context-free languages
- First-order and counting theories ofω-automatic structures
- The power of the middle bit of a \(\#\)P function
- Efficient Construction of Semilinear Representations of Languages Accepted by Unary Nondeterministic Finite Automata
- Complexity of Problems of Commutative Grammars
- Polynomial Space Counting Problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- The Odds of Staying on Budget
- Title not available (Why is that?)
Cited In (2)
This page was built for publication: Counting problems for Parikh images
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111226)
