Unary Languages Recognized by Two-Way One-Counter Automata

DOI10.1007/978-3-319-08846-4_11zbMATH Open1302.68156arXiv1311.0849OpenAlexW1834009093MaRDI QIDQ3192259FDOQ3192259

Authors: Marzio De Biasi, Abuzer Yakaryılmaz

Publication date: 26 September 2014

Published in: Implementation and Application of Automata (Search for Journal in Brave)

Abstract: A two-way deterministic finite state automaton with one counter (2D1CA) is a fundamental computational model that has been examined in many different aspects since sixties, but we know little about its power in the case of unary languages. Up to our knowledge, the only known unary nonregular languages recognized by 2D1CAs are those formed by strings having exponential length, where the exponents form some trivial unary regular language. In this paper, we present some non-trivial subsets of these languages. By using the input head as a second counter, we present simulations of two-way deterministic finite automata with linearly bounded counters and linear--space Turing machines. We also show how a fixed-size quantum register can help to simplify some of these languages. Finally, we compare unary 2D1CAs with two--counter machines and provide some insights about the limits of their computational power.

Full work available at URL: https://arxiv.org/abs/1311.0849

Recommendations

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited In (7)

This page was built for publication: Unary Languages Recognized by Two-Way One-Counter Automata

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