Article

On the learnability of finite automata

Authors:

Ming Li,

Umest VaziraniAuthors Info & Claims

COLT '88: Proceedings of the first annual workshop on Computational learning theory

Pages 359 - 370

Published: 01 December 1988 Publication History

Abstract

No abstract available.

Cited By

View all

Ron DRubinfeld R(1997)Exactly Learning Automata of Small Cover TimeMachine Language10.1023/A:100734892749127:1(69-96)Online publication date: 1-Apr-1997
https://dl.acm.org/doi/10.1023/A%3A1007348927491
Kearns MValiant L(1989)Crytographic limitations on learning Boolean formulae and finite automataProceedings of the twenty-first annual ACM symposium on Theory of computing10.1145/73007.73049(433-444)Online publication date: 1-Feb-1989
https://dl.acm.org/doi/10.1145/73007.73049
Pitt LWarmuth M(1989)The minimum consistent DFA problem cannot be approximated within and polynomialProceedings of the twenty-first annual ACM symposium on Theory of computing10.1145/73007.73048(421-432)Online publication date: 1-Feb-1989
https://dl.acm.org/doi/10.1145/73007.73048

Index Terms

On the learnability of finite automata
1. Computing methodologies
  1. Machine learning
2. Theory of computation

Recommendations

Oblivious two-way finite automata: Decidability and complexity

We investigate the descriptional complexity and decidability of obliviousness for two-way finite automata. In particular, we consider the simulation of two-way deterministic finite automata (2DFAs) by oblivious 2DFAs, the simulation of oblivious 2DFAs ...
Alternating finite automata and related problems
Complementing two-way finite automata

We study the relationship between the sizes of two-way finite automata accepting a language and its complement. In the deterministic case, for a given automaton (2dfa) with n states, we build an automaton accepting the complement with at most 4n states, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

COLT '88: Proceedings of the first annual workshop on Computational learning theory

December 1988

433 pages

Editors:
David Haussler
Univ. of California, Santa Cruz
,
Leonard Pitt
Univ. of Illinois, Urbana

Publisher

Morgan Kaufmann Publishers Inc.

San Francisco, CA, United States

Publication History

Published: 01 December 1988

Check for updates

Qualifiers

Article

Conference

COLT88

Sponsor:

SIGAI

COLT88: 1988 Working on Computational Learning Theory

August 3 - 5, 1988

Massachusetts, MIT, Cambridge, USA

Acceptance Rates

Overall Acceptance Rate 35 of 71 submissions, 49%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ron DRubinfeld R(1997)Exactly Learning Automata of Small Cover TimeMachine Language10.1023/A:100734892749127:1(69-96)Online publication date: 1-Apr-1997
https://dl.acm.org/doi/10.1023/A%3A1007348927491
Kearns MValiant L(1989)Crytographic limitations on learning Boolean formulae and finite automataProceedings of the twenty-first annual ACM symposium on Theory of computing10.1145/73007.73049(433-444)Online publication date: 1-Feb-1989
https://dl.acm.org/doi/10.1145/73007.73049
Pitt LWarmuth M(1989)The minimum consistent DFA problem cannot be approximated within and polynomialProceedings of the twenty-first annual ACM symposium on Theory of computing10.1145/73007.73048(421-432)Online publication date: 1-Feb-1989
https://dl.acm.org/doi/10.1145/73007.73048

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Oblivious two-way finite automata: Decidability and complexity

Alternating finite automata and related problems

Complementing two-way finite automata

Comments

Published In

Sponsors

Publisher

Publication History

Check for updates

Qualifiers

Conference

Acceptance Rates

Other Metrics

Article Metrics

Other Metrics

Cited By

Login options

Full Access

Abstract

Cited By

Index Terms

Recommendations

Oblivious two-way finite automata: Decidability and complexity

Alternating finite automata and related problems

Complementing two-way finite automata

Comments

Information

Published In

Sponsors

Publisher

Publication History

Check for updates

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations