Normality and two-way automata

DOI10.1016/J.IC.2015.02.001MaRDI QIDQ2343136zbMATH OpenOpenAlexFDO

Authors Olivier Carton, Pablo Ariel Heiber

Publication date 4 May 2015

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2015.02.001

zbMATH Keywords

normal numberscompressiontwo-way automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Normal numbers, radix expansions, Pisot numbers, Salem numbers, good lattice points, etc. (11K16)

Recommendations

• Normality and automata
• NORMALIZED EXPRESSIONS AND FINITE AUTOMATA
• Normal numbers and finite automata
• Two-way automaton computations
• Two-Way Non-Uniform Finite Automata
• Two-way non-uniform finite automata
• scientific article; zbMATH DE number 177806
• Two-way finite automata: old and recent results
• Two-way finite automata: old and recent results
• Two-way automata and length-preserving homomorphisms

Cites work

• scientific article; zbMATH DE number 2206109 (Why is no real title available?)
• A general theory of translation
• Distribution modulo one and Diophantine approximation
• Endliche Automaten und Zufallsfolgen
• Expressiveness of streaming string transducers
• Finite-state dimension
• MSO definable string transductions and two-way finite-state transducers
• Normal numbers and finite automata
• Selection functions that do not preserve normality
• The Equivalence Problem for Deterministic Two-Way Sequential Transducers is Decidable
• The Equivalence Problem for Single-Valued Two-Way Transducers (on NPDTOL Languages) is Decidable

Cited in

(14)

• A normal sequence compressed by PPM* but not by Lempel-Ziv 78
• Normality and automata
• NORMALIZED EXPRESSIONS AND FINITE AUTOMATA
• Pebble-depth
• Deterministic pushdown automata can compress some normal sequences
• Normal numbers and finite automata
• Preservation of normality by non-oblivious group selection
• Preservation of normality by unambiguous transducers
• Finite-state independence
• Normal numbers and computer science
• On normality in shifts of finite type
• Preservation of normality by transducers
• Finite-state independence and normal sequences
• scientific article; zbMATH DE number 4037204 (Why is no real title available?)

This page was built for publication: Normality and two-way automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2343136)