Automaticity. II: Descriptional complexity in the unary case

DOI10.1016/S0304-3975(96)00189-2zbMath0959.11015MaRDI QIDQ1390867

John Michael Robson, Carl B. Pomerance, Jeffrey O. Shallit

Publication date: 22 July 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

languagesdeterministic automaticity

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45) Automata sequences (11B85)

Related Items (5)

A new complexity function, repetitions in Sturmian words, and irrationality exponents of Sturmian numbers ⋮ Automaticity. IV: Sequences, sets, and diversity ⋮ Words and special factors ⋮ Enumerating regular expressions and their languages ⋮ On synchronized sequences and their separators

Cites Work

• On the number of cycles possible in digraphs with large girth
• On digraphs with no two disjoint directed cycles
• Finite automata and unary languages
• Automaticity. I: Properties of a measure of descriptional complexity
• On cube-free \(\omega\)-words generated by binary morphisms
• Approximate formulas for some functions of prime numbers
• On the power of finite automata with both nondeterministic and probabilistic states (preliminary version)
• Statistical Evidence for Small Generating Sets
• Explicit Bounds for Primality Testing and Related Problems
• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
• On independent circuits of a digraph
• Some Bounds on the Storage Requirements of Sequential Machines and Turing Machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Automaticity. II: Descriptional complexity in the unary case