Automaticity. II: Descriptional complexity in the unary case
From MaRDI portal
Publication:1390867
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)
Related Items
A new complexity function, repetitions in Sturmian words, and irrationality exponents of Sturmian numbers, Words and special factors, Automaticity. IV: Sequences, sets, and diversity, 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
