article

Introduction to automata theory, languages, and computation, 2nd edition

Authors:

John E. Hopcroft,

Rajeev Motwani,

Jeffrey D. UllmanAuthors Info & Claims

ACM SIGACT News, Volume 32, Issue 1

Pages 60 - 65

https://doi.org/10.1145/568438.568455

Published: 01 March 2001 Publication History

Get Access

Cited By

View all

Borges Junior E(2024)A inteligência artificial seria mesmo artificial? Uma releitura do conceito de inteligência a partir das noções de extensão e de conectividadePalabra Clave10.5294/pacla.2024.27.1.1127:1(1-28)Online publication date: 2-May-2024
https://doi.org/10.5294/pacla.2024.27.1.11
Cardona GVasile C(2024)Planning for heterogeneous teams of robots with temporal logic, capability, and resource constraintsThe International Journal of Robotics Research10.1177/02783649241247285Online publication date: 28-Apr-2024
https://doi.org/10.1177/02783649241247285
Li ZZhou ZWang XWu JChen L(2024)Neural Correlates of Analogical Reasoning on Syntactic PatternsJournal of Cognitive Neuroscience10.1162/jocn_a_0211536:5(854-871)Online publication date: 1-May-2024
https://doi.org/10.1162/jocn_a_02115
Show More Cited By

Index Terms

Introduction to automata theory, languages, and computation, 2nd edition
1. Theory of computation
  1. Formal languages and automata theory
    1. Grammars and context-free languages
  2. Models of computation

Index terms have been assigned to the content through auto-classification.

Recommendations

Limited Automata and Context-Free Languages
Non-Classical Models of Automata and Applications V

Limited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. For each d ≥ 2, these devices characterize the class of context-free languages. We investigate the equivalence ...
Deterministic Pushdown Automata and Unary Languages
CIAA '08: Proceedings of the 13th international conference on Implementation and Applications of Automata

The simulation of deterministic pushdown automata defined over a one letter alphabet by finite state automata is investigated from a descriptional complexity point of view. We show that each unary deterministic pushdown automaton of size s can be ...
Alternating automata and a temporal fixpoint calculus for visibly pushdown languages
CONCUR'07: Proceedings of the 18th international conference on Concurrency Theory

We investigate various classes of alternating automata for visibly pushdown languages (VPL) over infinite words. First, we show that alternating visibly pushdown automata (AVPA) are exactly as expressive as their nondeterministic counterpart (NVPA) but ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGACT News Volume 32, Issue 1

March 2001

88 pages

ISSN:0163-5700

DOI:10.1145/568438

Issue’s Table of Contents

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 2001

Published in SIGACT Volume 32, Issue 1

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

465
Total Citations
View Citations
5,267
Total Downloads

Downloads (Last 12 months)738
Downloads (Last 6 weeks)60

Reflects downloads up to 14 Aug 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Borges Junior E(2024)A inteligência artificial seria mesmo artificial? Uma releitura do conceito de inteligência a partir das noções de extensão e de conectividadePalabra Clave10.5294/pacla.2024.27.1.1127:1(1-28)Online publication date: 2-May-2024
https://doi.org/10.5294/pacla.2024.27.1.11
Cardona GVasile C(2024)Planning for heterogeneous teams of robots with temporal logic, capability, and resource constraintsThe International Journal of Robotics Research10.1177/02783649241247285Online publication date: 28-Apr-2024
https://doi.org/10.1177/02783649241247285
Li ZZhou ZWang XWu JChen L(2024)Neural Correlates of Analogical Reasoning on Syntactic PatternsJournal of Cognitive Neuroscience10.1162/jocn_a_0211536:5(854-871)Online publication date: 1-May-2024
https://doi.org/10.1162/jocn_a_02115
Siddiq MZhang JSantos JBaysal OLinares-Vasquez MMoran KSteinmacher I(2024)Understanding Regular Expression Denial of Service (ReDoS): Insights from LLM-Generated Regexes and Developer ForumsProceedings of the 32nd IEEE/ACM International Conference on Program Comprehension10.1145/3643916.3644424(190-201)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1145/3643916.3644424
Siddiq MZhang JRoney LSantos JRoychoudhury APaiva AAbreu RStorey MHierons RMadeira H(2024)Re(gEx|DoS)Eval: Evaluating Generated Regular Expressions and their Proneness to DoS AttacksProceedings of the 2024 ACM/IEEE 44th International Conference on Software Engineering: New Ideas and Emerging Results10.1145/3639476.3639757(52-56)Online publication date: 14-Apr-2024
https://dl.acm.org/doi/10.1145/3639476.3639757
Meilandri EThamrin H(2024)Recursive Descent Parser and Context Free Grammar in Examining Indonesian Sentence Patterns2024 International Conference on Smart Computing, IoT and Machine Learning (SIML)10.1109/SIML61815.2024.10578240(286-290)Online publication date: 6-Jun-2024
https://doi.org/10.1109/SIML61815.2024.10578240
Neumüller DSihler FStraub RTichy M(2024)Exploring the Effectiveness of Abstract Syntax Tree Patterns for Algorithm Recognition2024 4th International Conference on Code Quality (ICCQ)10.1109/ICCQ60895.2024.10576984(1-18)Online publication date: 22-Jun-2024
https://doi.org/10.1109/ICCQ60895.2024.10576984
Cicolini LCarloni FSantambrogio MConficconi D(2024)One Automaton to Rule Them All: Beyond Multiple Regular Expressions Execution2024 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)10.1109/CGO57630.2024.10444810(193-206)Online publication date: 2-Mar-2024
https://doi.org/10.1109/CGO57630.2024.10444810
Jaspars H(2024)The stable conjugation-invariant word norm is rational in free groupsProceedings of the American Mathematical Society10.1090/proc/16786Online publication date: 25-Apr-2024
https://doi.org/10.1090/proc/16786
Liu JTeunisse MKorovin GVermaire IJin LBense Hvan Hecke M(2024)Controlled pathways and sequential information processing in serially coupled mechanical hysteronsProceedings of the National Academy of Sciences10.1073/pnas.2308414121121:22Online publication date: 20-May-2024
https://doi.org/10.1073/pnas.2308414121
Show More Cited By

View Options

Get Access

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

Limited Automata and Context-Free Languages

Deterministic Pushdown Automata and Unary Languages

Alternating automata and a temporal fixpoint calculus for visibly pushdown languages

Comments

Published In

Publisher

Publication History

Check for updates

Qualifiers

Other Metrics

Article Metrics

Other Metrics

Cited By

Login options

Full Access

PDF

eReader

Cited By

Index Terms

Recommendations

Limited Automata and Context-Free Languages

Deterministic Pushdown Automata and Unary Languages

Alternating automata and a temporal fixpoint calculus for visibly pushdown languages

Comments

Information

Published In

Publisher

Publication History

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Get Access

Login options

Full Access

View options

PDF

eReader

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations