A note on Parikh maps, abstract languages, and decision problems (Q1065555): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:05, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on Parikh maps, abstract languages, and decision problems |
scientific article |
Statements
A note on Parikh maps, abstract languages, and decision problems (English)
0 references
1985
0 references
We consider formulas similar to Presburger formulas, but extended by allowing the predicate \(|\) (for divides), but not allowing universal quantification of the resulting expressions. The solution sets for such formulas are known to be not semilinear, in general. We show that some results concerning decidability questions for classes of languages with effectively constructible semilinear Parikh maps can be extended to languages whose effectively constructible Parikh maps are solutions to these new formulas, which we call ''modular''. We suggest that modularity may offer a natural extension of semilinearity, in which many previously established results may remain valid.
0 references
semilinear sets
0 references
division
0 references
Presburger formulas
0 references
decidability
0 references
Parikh maps
0 references