Characterizing regular languages with polynomial densities
From MaRDI portal
Publication:5096862
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
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
