article

Aural Pattern Recognition Experiments and the Subregular Hierarchy

Authors:

Geoffrey K. PullumAuthors Info & Claims

Journal of Logic, Language and Information, Volume 20, Issue 3

Pages 329 - 342

https://doi.org/10.1007/s10849-011-9140-2

Published: 01 July 2011 Publication History

Abstract

We explore the formal foundations of recent studies comparing aural pattern recognition capabilities of populations of human and non-human animals. To date, these experiments have focused on the boundary between the Regular and Context-Free stringsets. We argue that experiments directed at distinguishing capabilities with respect to the Subregular Hierarchy, which subdivides the class of Regular stringsets, are likely to provide better evidence about the distinctions between the cognitive mechanisms of humans and those of other species. Moreover, the classes of the Subregular Hierarchy have the advantage of fully abstract descriptive (model-theoretic) characterizations in addition to characterizations in more familiar grammar- and automata-theoretic terms. Because the descriptive characterizations make no assumptions about implementation, they provide a sound basis for drawing conclusions about potential cognitive mechanisms from the experimental results. We review the Subregular Hierarchy and provide a concrete set of principles for the design and interpretation of these experiments.

References

[1]

Benedikt, M., & Segoufin, L. (2005). Regular tree languages definable in FO. In V. Diekert & B. Durand (Eds.), 22nd annual symposium on theoretical aspects of computer science (STACS 2005), lecture notes in computer science (Vol. 3404, pp. 327-339).

[2]

Bresnan, J. W. (1978). Evidence for a theory of unbounded transformations. Linguistic Analysis, 2, 353-393.

[3]

Büchi, J. R. (1960). Week second-order arithmetic and finite automata. Zeitschrift für Mathematische Logik Und Grundlagen der Mathematik, 6, 66-92.

[4]

Chomsky, N. (1962). Context-free grammars and pushdown storage. Quarterly Progress Report 65, MIT Res. Lab. Elect.

[5]

Elgot, C. C. (1961). Decision problems of finite automata and related arithmetics. Transactions of the American Mathematical Society, 98, 21-51.

[6]

Fitch, W. T., & Hauser, M. D. (2004). Computational constraints on syntactic processing in nonhuman primates. Science, 303, 377-380.

[7]

García, P., & Ruiz, J. (1990). Inference of k-testable languages in the strict sense and applications to syntactic pattern recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 9, 920-925.

Digital Library

[8]

Gentner, T. Q., Fenn, K. M., Margoliash, D., & Nusbaum, H. C. (2006). Recursive syntactic pattern learning by songbirds. Nature, 440, 1204-1207.

[9]

Hauser, M. D., Chomsky, N., & Fitch, W. T. (2002). The faculty of language: What is it, who has it, and how did it evolve. Science, 298, 1569-1579.

[10]

Heinz, J. (2007). Inductive learning of phonotactic patterns. PhD thesis, Department of Linguistics, UCLA.

[11]

Huybregts, R. (1984). The weak inadequacy of context-free phrase structure grammars. In G. J. Haan, M. de Trommelen, & W. Zonneveld (Eds.), Van Periferie Naar Kern (pp. 81-99). Dordrecht: Foris Publications.

[12]

Lautemann, C., Schwentick, T., & Théien, D. (1994). Logics for context-free languages. In L. Pacholski & J. Tiuryn (Ed.), Computer science logic (pp. 203-216). Poland: Kazimierz.

[13]

McNaughton, R., & Papert, S. (1971). Counter-free automata. Cambridge: MIT Press.

[14]

Medvedev, Y. T. (1964). On the class of events representable in a finite automaton. In E. F. Moore (Ed.), Computer science logic (pp. 215-227). Addison-Wesley: Sequential Machines-- Selected Papers. originally in Russian in Avtomaty (1956), pp. 385-401.

[15]

Perruchet, P., & Rey, A. (2005). Does the mastery of center-embedded linguistic structures distinguish humans from nonhuman primates?. Psychonomic Bulletin and Review, 12, 307-313.

[16]

Shieber, S. (1985). Evidence against the context-freeness of human language. Linguistics and Philosophy, 8, 333-343.

[17]

Straubing, H. (1994). Finite automata, formal logic and circuit complexity. Boston: Birkhäuser.

[18]

Thomas, W. (1982). Classifying regular events in symbolic logic. Journal of Computer and Systems Sciences, 25, 360-376.

Cited By

Lambert D(2023)Relativized AdjacencyJournal of Logic, Language and Information10.1007/s10849-023-09398-x32:4(707-731)Online publication date: 19-May-2023
https://dl.acm.org/doi/10.1007/s10849-023-09398-x
Vágvölgyi S(2022)Deterministic top-down tree automata with Boolean deterministic look-aheadTheoretical Computer Science10.1016/j.tcs.2022.05.027927:C(42-64)Online publication date: 26-Aug-2022
https://dl.acm.org/doi/10.1016/j.tcs.2022.05.027
Ji JHeinz J(2020)Input Strictly Local Tree TransducersLanguage and Automata Theory and Applications10.1007/978-3-030-40608-0_26(369-381)Online publication date: 4-Mar-2020
https://dl.acm.org/doi/10.1007/978-3-030-40608-0_26
Show More Cited By

Aural Pattern Recognition Experiments and the Subregular Hierarchy

Recommendations

Decision Problems for Subregular Classes
Implementation and Application of Automata
Abstract
We study the computational complexity of deciding whether a given deterministic or nondeterministic finite automaton (DFA or NFA) recognizes a language in a given subclass of regular languages. We prove NL-completeness of this problem on both ...
Determination of finite automata accepting subregular languages

We investigate the descriptional complexity of the nondeterministic finite automaton (NFA) to the deterministic finite automaton (DFA) conversion problem, for automata accepting subregular languages such as combinational languages, definite languages ...
On Complexity of Two Dimensional Languages Generated by Transducers
CIAA '08: Proceedings of the 13th international conference on Implementation and Applications of Automata

We consider two-dimensional languages, called here 2d transducer languages , generated by iterative applications of transducers (finite state automata with output). To each transducer a two-dimensional language consisting of blocks of symbols is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Logic, Language and Information

Journal of Logic, Language and Information Volume 20, Issue 3

July 2011

142 pages

ISSN:0925-8531

Issue’s Table of Contents

Copyright © Copyright © 2011 Springer Science+Business Media B.V.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 July 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 19 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lambert D(2023)Relativized AdjacencyJournal of Logic, Language and Information10.1007/s10849-023-09398-x32:4(707-731)Online publication date: 19-May-2023
https://dl.acm.org/doi/10.1007/s10849-023-09398-x
Vágvölgyi S(2022)Deterministic top-down tree automata with Boolean deterministic look-aheadTheoretical Computer Science10.1016/j.tcs.2022.05.027927:C(42-64)Online publication date: 26-Aug-2022
https://dl.acm.org/doi/10.1016/j.tcs.2022.05.027
Ji JHeinz J(2020)Input Strictly Local Tree TransducersLanguage and Automata Theory and Applications10.1007/978-3-030-40608-0_26(369-381)Online publication date: 4-Mar-2020
https://dl.acm.org/doi/10.1007/978-3-030-40608-0_26
Jardine A(2019)The Expressivity of Autosegmental GrammarsJournal of Logic, Language and Information10.1007/s10849-018-9270-x28:1(9-54)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1007/s10849-018-9270-x
Mayer CMajor T(2018)A Challenge for Tier-Based Strict Locality from Uyghur Backness HarmonyFormal Grammar 201810.1007/978-3-662-57784-4_4(62-83)Online publication date: 11-Aug-2018
https://dl.acm.org/doi/10.1007/978-3-662-57784-4_4
Heinz JRawal CTanner HLin D(2011)Tier-based strictly local constraints for phonologyProceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies: short papers - Volume 210.5555/2002736.2002750(58-64)Online publication date: 19-Jun-2011
https://dl.acm.org/doi/10.5555/2002736.2002750
Heinz Jde la Higuera Cvan Zaanen MWay APantel P(2011)Formal and empirical grammatical inferenceProceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Tutorial Abstracts of ACL 201110.5555/2002465.2002467(1-83)Online publication date: 19-Jun-2011
https://dl.acm.org/doi/10.5555/2002465.2002467
Yli-jyr?? AKornai ASakarovitch J(2011)Finite-state methods and models in natural language processingNatural Language Engineering10.1017/S135132491100001517:2(141-144)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1017/S1351324911000015
Heinz JKoirala CHeinz JCahill LWicentowski R(2010)Maximum likelihood estimation of feature-based distributionsProceedings of the 11th Meeting of the ACL Special Interest Group on Computational Morphology and Phonology10.5555/1870478.1870482(28-37)Online publication date: 15-Jul-2010
https://dl.acm.org/doi/10.5555/1870478.1870482
Heinz JHajič J(2010)String extension learningProceedings of the 48th Annual Meeting of the Association for Computational Linguistics10.5555/1858681.1858773(897-906)Online publication date: 11-Jul-2010
https://dl.acm.org/doi/10.5555/1858681.1858773
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents