Bounded Parikh automata

DOI10.4204/EPTCS.63.13MaRDI QIDQ2789518zbMATH OpenOpenAlexFDO

Authors Michaël Cadilhac, Pierre McKenzie, Alain Finkel

Publication date 1 March 2016

Published in Electronic Proceedings in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.3625, http://www.emis.de/proceedings/Words2011/paper-11.html?WORDS2011.13

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: The Parikh finite word automaton model (PA) was introduced and studied by Klaedtke and Ruess in 2003. Here, by means of related models, it is shown that the bounded languages recognized by PA are the same as those recognized by deterministic PA. Moreover, this class of languages is the class of bounded languages whose set of iterations is semilinear.

Recommendations

• Bounded Parikh automata
• scientific article; zbMATH DE number 7439739
• Affine Parikh automata
• Tight bounds for complementing parity automata
• Determinising parity automata
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• Pushdown automata with bounded nondeterminism and bounded ambiguity
• Regular separability of Parikh automata
• The algebraic theory of Parikh automata
• The algebraic theory of Parikh automata

Cited in

(11)

• Bounded Parikh automata
• The algebraic theory of Parikh automata
• BORDERS AND FINITE AUTOMATA
• Affine Parikh automata
• Enumerated BSP Automata
• scientific article; zbMATH DE number 7439739 (Why is no real title available?)
• Determinisability of register and timed automata
• On the Parikh membership problem for FAs, PDAs, and CMs
• DFA with a Bounded Activity Level
• The algebraic theory of Parikh automata
• Semi-linearity, Parikh-boundedness and tree adjunct languages

This page was built for publication: Bounded Parikh automata

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