Unary finite automata vs. arithmetic progressions

DOI10.1016/j.ipl.2009.06.005zbMath1202.68241arXiv0812.1291OpenAlexW2004542062MaRDI QIDQ989556

Anthony Widjaja To

Publication date: 20 August 2010

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

algorithmsarithmetic progressionsformal languagesunary languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (17)

A Cookbook for Temporal Conceptual Data Modelling with Description Logics ⋮ Pairs of complementary unary languages with ``balanced nondeterministic automata ⋮ Distributed graph problems through an automata-theoretic lens ⋮ Knapsack in graph groups ⋮ Unnamed Item ⋮ On the expressiveness of Büchi arithmetic ⋮ Closure properties of knapsack semilinear groups ⋮ First-order rewritability of ontology-mediated queries in linear temporal logic ⋮ Efficient Construction of Semilinear Representations of Languages Accepted by Unary NFA ⋮ Two-way unary automata versus logarithmic space ⋮ Investigations on Automata and Languages Over a Unary Alphabet ⋮ Unnamed Item ⋮ Chrobak Normal Form Revisited, with Applications ⋮ Remarks on Separating Words ⋮ From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity ⋮ Nondeterministic complexity in subclasses of convex languages ⋮ Descriptional complexity of regular languages

Cites Work

• A special case of a unary regular language containment
• The Frobenius Problem and Its Generalizations
• Finite Automata, Palindromes, Powers, and Patterns
• On a Problem of Partitions
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Unary finite automata vs. arithmetic progressions