article

Free access

Simple Representations of Certain Classes of Languages

Author:

Ronald V. BookAuthors Info & Claims

Journal of the ACM (JACM), Volume 25, Issue 1

Pages 23 - 31

https://doi.org/10.1145/322047.322050

Published: 01 January 1978 Publication History

PDF eReader

References

[1]

BAKER, B, ANO BOOK, R. Reversal-bounded multl-pushdown machmes J Comptr Syst Sci 8 (1974), 315-332

Google Scholar

[2]

BooK, R, Ar~O NIVAT, M Linear languages and intersections of classes of languages To appear in SIAM J Comptng

Google Scholar

[3]

BOOK, R, NIVAT, M, AND PATERSON, M Reversal-bounded acceptors and intersections of hnear languages SIAM J. Comptng 3 (1974), 283-295

Google Scholar

[4]

GINSnURG, S, AriD GREmACH, S Principal AFL J Comptr Syst Set 4 (1970), 308-338.

Google Scholar

[5]

GINSBURG, S, GREIBACH, S., AND HOPCROFr, S Pre-AFL Studtes tn Abstract Famlhes of Languages, Memoir No 87, Amer Math Soc, Providence, R I, 1969, pp 41-51

Google Scholar

[6]

GINSBURC, S, AND SPANtER, E Ftmte-term pushdown automata SlAM J Control 4 (1966), 429-453

Google Scholar

[7]

GINSBUR~, S, AND SPANIER, E AFL w~th the semdmear property. J Comptr Syst Sct 5 (1971), 365- 396

Google Scholar

[8]

GREmACI~, S Control sets on context-free grammar forms To appear m J Comptr Syst. Scz.

Google Scholar

[9]

GREmACH, S One-way fimte wslt automata To appear m Theoret. Comptr. Sct

Google Scholar

[10]

KLEENE, S lntroductton to Metamathemattcs Van Nostrand, Princeton, N J, 1952.

Google Scholar

[11]

KLINGENSTmN, K Structures of bounded languages m certain famd~es of languages To appear m Inform Control

Google Scholar

[12]

KLINGENSTEIN, K p-matrix languages To appear m Theoret Comptr Sct.

Google Scholar

[13]

RO~ERS, H Theory ofRecurstve Functtons and Effective Computabthty McGraw-Hall, New York, 1967

Crossref

Google Scholar

[14]

STOCKMEYER, L The polynomml-tlme hierarchy Theoret Comptr Scz. 3 (1977), 1-224

Google Scholar

[15]

SUDBOROU6H, I H The complexity of the membership problem for some extenstons of context-free languages To appear m Int J. Comptr. Math

Google Scholar

[16]

WRATHALL, C Subrecurswe predicates and automata Ph D Diss, Harvard U, Cambridge, Mass, 1975.

Google Scholar

[17]

WRATHALL, C Complete sets and polynomml hterarchy Theoret Comptr. Sct 3 (1977), 23-33

Google Scholar

[18]

WRATHALL, C Characterizations of the Dyck sets To appear m Revue Francazse d'Automatlque, lnformattque, Recherche Operattonnelle 11 (1977)

Google Scholar

[19]

WRATrIALL, C Rudimentary predicates and relatwe computation To appear m SlAM J Comptng

Google Scholar

Cited By

View all

Zetzsche GKuske DLohrey M(2017)On Boolean Closed Full Trios and Rational Kripke FramesTheory of Computing Systems10.1007/s00224-016-9694-060:3(438-472)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s00224-016-9694-0
Stenger H(2011)Algebraic caractérisations of NTIME$(F)$ and NTIME$(F, A)$RAIRO. Informatique théorique10.1051/ita/198418040365118:4(365-385)Online publication date: 8-Jan-2011
https://doi.org/10.1051/ita/1984180403651
Book RGreibach S(2011)The independence of certain operations on semiAFLsRAIRO. Informatique théorique10.1051/ita/197812040369112:4(369-385)Online publication date: 8-Jan-2011
https://doi.org/10.1051/ita/1978120403691
Show More Cited By

Index Terms

Simple Representations of Certain Classes of Languages
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Representation of mathematical objects
      1. Representation of polynomials
2. Theory of computation
  1. Formal languages and automata theory
    1. Grammars and context-free languages

Recommendations

Languages to diagonalize against advice classes
Abstract.
Variants of Kannan’s Theorem are given where the circuits of the original theorem are replaced by arbitrary recursively presentable classes of languages that use advice strings and satisfy certain mild conditions. Let poly_k denote those functions ...
Classes of Szilard Languages in NC^1
SYNASC '09: Proceedings of the 2009 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing

We prove that Szilard languages of context-free grammars can be accepted by an indexing alternating Turing machine (indexing ATM) in logarithmic time and space. The same result holds for leftmost Szilard languages of unrestricted (phrase-structure or ...
The complexity of properly learning simple concept classes

We consider the complexity of properly learning concept classes, i.e. when the learner must output a hypothesis of the same form as the unknown concept. We present the following new upper and lower bounds on well-known concept classes:*We show that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 25, Issue 1

Jan. 1978

175 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/322047

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1978

Published in JACM Volume 25, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
579
Total Downloads

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

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zetzsche GKuske DLohrey M(2017)On Boolean Closed Full Trios and Rational Kripke FramesTheory of Computing Systems10.1007/s00224-016-9694-060:3(438-472)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1007/s00224-016-9694-0
Stenger H(2011)Algebraic caractérisations of NTIME$(F)$ and NTIME$(F, A)$RAIRO. Informatique théorique10.1051/ita/198418040365118:4(365-385)Online publication date: 8-Jan-2011
https://doi.org/10.1051/ita/1984180403651
Book RGreibach S(2011)The independence of certain operations on semiAFLsRAIRO. Informatique théorique10.1051/ita/197812040369112:4(369-385)Online publication date: 8-Jan-2011
https://doi.org/10.1051/ita/1978120403691
Greibach S(2011)The strong independence of substitution and homomorphic replicationRAIRO. Informatique théorique10.1051/ita/197812030213112:3(213-234)Online publication date: 8-Jan-2011
https://doi.org/10.1051/ita/1978120302131
Allender EGore V(2005)On strong separations from AC oFundamentals of Computation Theory10.1007/3-540-54458-5_44(1-15)Online publication date: 9-Jun-2005
https://doi.org/10.1007/3-540-54458-5_44
Balcázar JDíaz JGabarró J(2005)On non-uniform polynomial spaceStructure in Complexity Theory10.1007/3-540-16486-3_88(35-50)Online publication date: 2-Jun-2005
https://doi.org/10.1007/3-540-16486-3_88
Monien B(2005)On the LBA problemFundamentals of Computation Theory10.1007/3-540-10854-8_30(265-280)Online publication date: 28-Jul-2005
https://doi.org/10.1007/3-540-10854-8_30
Dassow J(2005)Equality languages and language familiesFundamentals of Computation Theory10.1007/3-540-10854-8_10(100-109)Online publication date: 28-Jul-2005
https://doi.org/10.1007/3-540-10854-8_10
Book R(2005)Complexity classes of formal languagesMathematical Foundations of Computer Science 197910.1007/3-540-09526-8_4(43-56)Online publication date: 26-May-2005
https://doi.org/10.1007/3-540-09526-8_4
Book RGreibach SWrathall C(2005)Comparisons and reset machinesAutomata, Languages and Programming10.1007/3-540-08860-1_10(113-124)Online publication date: 26-May-2005
https://doi.org/10.1007/3-540-08860-1_10
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

References

Cited By

Index Terms

Recommendations

Languages to diagonalize against advice classes

Classes of Szilard Languages in NC^1

The complexity of properly learning simple concept classes

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations