Testing membership in counter automaton languages

DOI10.1007/978-3-642-40328-6_38MaRDI QIDQ2851885zbMATH OpenOpenAlexFDO

Authors Yonatan Goldhirsh, Michael Viderman

Publication date 4 October 2013

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-40328-6_38

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Randomized algorithms (68W20)

Recommendations

• Regular languages are testable with a constant number of queries
• Testing Membership in Languages that Have Small Width Branching Programs
• Space Complexity vs. Query Complexity
• Space complexity vs. query complexity
• scientific article; zbMATH DE number 2019622

Cited in

(7)

• Automaton-Based Criteria for Membership in CTL
• Testing membership in parenthesis languages
• scientific article; zbMATH DE number 2019622 (Why is no real title available?)
• Space complexity vs. query complexity
• \(\omega\)-regular languages are testable with a constant number of queries
• Regular languages are testable with a constant number of queries
• Space Complexity vs. Query Complexity

This page was built for publication: Testing membership in counter automaton languages

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