Automata with Reversal-Bounded Counters: A Survey

DOI10.1007/978-3-319-09704-6_2zbMath1416.68097OpenAlexW2182252111MaRDI QIDQ5496173

Oscar H. Ibarra

Publication date: 7 August 2014

Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-09704-6_2

zbMATH Keywords

finite automatoncontext-free grammarsemilinear setreversal-bounded counterstransducerpushdown automatondecidablevisibly pushdown automatonundecidablefinite-valuedfinitely-ambiguous

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (11)

The effect of end-markers on counter machines and commutativity ⋮ On history-deterministic one-counter nets ⋮ On the complexity and decidability of some problems involving shuffle ⋮ Unnamed Item ⋮ Reachability analysis of reversal-bounded automata on series-parallel graphs ⋮ Further remarks on DNA overlap assembly ⋮ Accepting runs in a two-way finite automaton ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the overlap assembly of strings and languages ⋮ Degrees of restriction for two-dimensional automata

This page was built for publication: Automata with Reversal-Bounded Counters: A Survey