A note on Parikh maps, abstract languages, and decision problems

DOI10.1016/0020-0255(85)90047-7zbMath0577.68075OpenAlexW2006830748MaRDI QIDQ1065555

Louis E. Rosier, Alfred E. Borm

Publication date: 1985

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0255(85)90047-7

zbMATH Keywords

decidabilitydivisionsemilinear setsParikh mapsPresburger formulas

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Decidability of theories and sets of sentences (03B25)

Related Items (1)

A note on Parikh maps, abstract languages, and decision problems

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• A note on Parikh maps, abstract languages, and decision problems
• The complexity of decision problems for finite-turn multicounter machines
• 2DST mappings of languages and related problems
• One way finite visit automata
• Controlled pushdown automata
• A hierarchy between context-free and context-sensitive languages
• Finite-turn checking automata
• Absolutely parallel grammars and two-way finite-state transducers
• Two-way counter machines and finite-state transducers†
• Two-Way Counter Machines and Diophantine Equations
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• The Diophantine Problem for Addition and Divisibility
• Bounded Algol-Like Languages
• On Context-Free Languages
• Three models for the description of language
• Multi-tape and multi-head pushdown automata
• Programmed Grammars and Classes of Formal Languages
• Simple matrix languages
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Definability and decision problems in arithmetic

This page was built for publication: A note on Parikh maps, abstract languages, and decision problems