Characterizing regular languages with polynomial densities

DOI10.1007/3-540-55808-X_48zbMath1493.68195OpenAlexW1605153944MaRDI QIDQ5096862

Zhang, Kaizhong, Andrew L. Szilard, Sheng Yu, Jeffrey O. Shallit

Publication date: 18 August 2022

Published in: Mathematical Foundations of Computer Science 1992 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55808-x_48

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (25)

Automata and finite order elements in the Nottingham group ⋮ On the joint subword complexity of automatic sequences ⋮ Deciding determinism of caterpillar expressions ⋮ Synchronized sequences ⋮ Unnamed Item ⋮ When is an automatic set an additive basis? ⋮ Language-theoretic complexity of disjunctive sequences ⋮ On the regularity of \(\{\lfloor \log_b(\alpha n+\beta)\rfloor\}_{n\geq 0}\) ⋮ Deterministic Caterpillar Expressions ⋮ \(F\)-sets and finite automata ⋮ The Gelfand-Kirillov dimension of Hecke-Kiselman algebras ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time ⋮ On the expressiveness of Büchi arithmetic ⋮ Deciding regularity of hairpin completions of regular languages in polynomial time ⋮ Representing real numbers in a generalized numeration system ⋮ The growth function of \(S\)-recognizable sets ⋮ Numeration systems on a regular language: Arithmetic operations, recognizability and formal power series ⋮ Automatic Sequences and Generalised Polynomials ⋮ On lengths of words in context-free languages ⋮ Decidability of trajectory-based equations ⋮ Boolean algebras of regular languages ⋮ Structural properties of NFAs and growth rates of nondeterminism measures ⋮ A refinement of Christol's theorem for algebraic power series

Cites Work

• Can the catenation of two weakly sparse languages be dense?
• A homomorphic characterization of regular languages
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Finite counting automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Characterizing regular languages with polynomial densities