Amount of nonconstructivity in deterministic finite automata

DOI10.1016/J.TCS.2010.05.038MaRDI QIDQ1959651zbMATH OpenOpenAlexFDO

Authors Rūsiņš Freivalds

Publication date 7 October 2010

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

Full work available at URL https://doi.org/10.1016/j.tcs.2010.05.038

zbMATH Keywords

finite automataKolmogorov complexitynonconstructive methods

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Formal languages and automata (68Q45)

Recommendations

• Amount of Nonconstructivity in Finite Automata
• On the amount of nonconstructivity in learning recursive functions
• On the amount of nonconstructivity in learning formal languages from positive data
• On the amount of nonconstructivity in learning formal languages from text
• NON-CONSTRUCTIVE METHODS FOR FINITE PROBABILISTIC AUTOMATA

Cites work

• Amount of Nonconstructivity in Finite Automata
• Automata that take advice
• scientific article; zbMATH DE number 3588047 (Why is no real title available?)
• scientific article; zbMATH DE number 918133 (Why is no real title available?)
• scientific article; zbMATH DE number 1390024 (Why is no real title available?)
• scientific article; zbMATH DE number 3307567 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• scientific article; zbMATH DE number 3068971 (Why is no real title available?)
• Inductive inference of recursive functions: complexity bounds
• Non-constructive Methods for Finite Probabilistic Automata
• NON-CONSTRUCTIVE METHODS FOR FINITE PROBABILISTIC AUTOMATA
• Polynomial time quantum computation with advice
• SOFSEM 2004: Theory and Practice of Computer Science
• Some remarks on the theory of graphs
• The definition of random sequences
• The mathematics of coding theory. Information, compression, error correction and finite fields.
• Turing machines that take advice

Cited in

(14)

• On the amount of nonconstructivity in learning formal languages from text
• Advice hierarchies among finite automata
• Hartmanis-Stearns Conjecture on Real Time and Transcendence
• Multiple usage of random bits in finite automata
• On the amount of nonconstructivity in learning recursive functions
• On the influence of technology on learning processes
• Amount of Nonconstructivity in Finite Automata
• scientific article; zbMATH DE number 7559401 (Why is no real title available?)
• Finite automata with advice tapes
• Quantum state complexity of formal languages
• Determinism and Nondeterminism in Finite Automata with Advice
• Two-Way Non-Uniform Finite Automata
• Multi-head two-way finite automata with advice
• Two-way non-uniform finite automata

This page was built for publication: Amount of nonconstructivity in deterministic finite automata

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