On the descriptional complexity of operations on semilinear sets

MaRDI QIDQ5016357zbMATH OpenFDO

Authors Simon Beier, Markus Holzer, Martin Kutrib

Publication date 13 December 2021

Full work available at URL https://arxiv.org/abs/1708.06460, http://eptcs.web.cse.unsw.edu.au/paper.cgi?AFL2017.8

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• The taming of the semi-linear set
• Semilinear sets and counter machines: a brief survey
• scientific article; zbMATH DE number 4172404
• Descriptional complexity and operations -- two non-classical cases
• New results on semilinear sets and variants of jumping finite automata

Cites work

• A Bound on Solutions of Linear Integer Equalities and Inequalities
• Bounded Algol-Like Languages
• Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata
• Finite-Turn Pushdown Automata
• scientific article; zbMATH DE number 3694623 (Why is no real title available?)
• Jumping finite automata
• On Context-Free Languages
• Operational state complexity and decidability of jumping finite automata
• Operational State Complexity under Parikh Equivalence
• The taming of the semi-linear set

Cited in

(18)

• Some descriptive-set-theoretical problems in complexity theory
• Closure properties of knapsack semilinear groups
• On the descriptive complexity of \(\overline{\varSigma ^*\overline{L}}\)
• Semilinear sets and counter machines: a brief survey
• scientific article; zbMATH DE number 4172404 (Why is no real title available?)
• The taming of the semi-linear set
• scientific article; zbMATH DE number 4001487 (Why is no real title available?)
• On the boundedness property of semilinear sets
• scientific article; zbMATH DE number 6415494 (Why is no real title available?)
• Operational accepting state complexity: the unary and finite case
• Operational state complexity and decidability of jumping finite automata
• Implementation and Application of Automata
• Jumping automata over Infinite words
• Exponent equations in HNN-extensions
• Geometric decision procedures and the VC dimension of linear arithmetic theories
• Jumping automata over infinite words
• Synchronization of Parikh automata
• The complexity of semilinear problems in succinct representation

This page was built for publication: On the descriptional complexity of operations on semilinear sets

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