Inference of Reversible Languages

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Inference of Reversible Languages

Full text

Pdf (1.39 MB)

Source

Journal of the ACM (JACM) archive
Volume 29 , Issue 3 (July 1982) table of contents

Pages: 741 - 765

Year of Publication: 1982

ISSN:0004-5411

Author

Dana Angluin

Department of Computer Science, Yale University, P O Box 2158, Yale Station, New Haven, CT

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 101, Citation Count: 44

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322326.322334 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	ANGLUIN, D On the complexity of rmnlmum inference of regular sets. Inf. Control 39 (1978), 337-350
	3	AnGLUIN, D Finding patterns common to a set of strings J Comput. Syst Sei. 21 (1980), 46--62.
	4	ANGLUIN, D Inductive reference of formal languages from posmve data Inf Control 45 (1980), 117-135
	5	BIER.MANN, A W, AND FELDMAN, J.A On the synthesis of finite-state machines from samples of their behavior IEEE Trans. Comput C-21 (1972), 592-597
	6	BLUM, L, AND BLUM, M.Toward a mathematic theory of inductive inference. Inf. Control 28 (1978), 125-155.
	7	John Case , Carl Smith, Anomaly hierarchies of mechanized inductive inference, Proceedings of the tenth annual ACM symposium on Theory of computing, p.314-319, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804360]
	8	Cohen, R.S, AND BRZOEOWSKI, J A.General propemes of star height of regular events. J Comput. Syst. Sct 4 (1970), 260-280.
	9	CRESPI-RegHIZZI, S An effective model for grammar inference. In Informatwn Processing, North Holland, 1972, pp 524-529
	10	S. Crespi-Reghizzi , G. Guida , D. Mandrioli, Noncounting Context-Free Languages, Journal of the ACM (JACM), v.25 n.4, p.571-580, Oct. 1978 [doi>10.1145/322092.322098]
	11	FELDMAN, J.A First thoughts on grammatical inference Tech, Rep., Artificial Intelhgence Project, Stanford Un,v., Stanford, Calif., 1967
	12	FELDMAN, J A Some decldabdlty results m grammaucal inference Inf. Control 20 (1972), 244-262,
	13	Jerome A. Feldman , James Gips , James J. Horning , Stephen Reder, Grammatical complexity and inference, Stanford University, Stanford, CA, 1969
	14	Fu,KS Syntactic Methods m Pattern Recognltwn Academic Press, New York, I975.
	15	Fu,K S Syntacac Pattern RecogniOon, Apphcations Spnnger-Veflag, New York, 1977.
	16	Fu, K S, AND BOOTH, T.L. Grammatical mference" Introduction and survey, Parts 1 and 2 IEEE Trans. Syst., Man Cybern SMC-5 (1975), 95-11.1,409-423.
	17	GINZBURG, A.About some properties of definite, reverse-defimte and related automata. IEEE Trans Electron. Comput. EC-15 (1966), 806-810
	18	GOLD, E M Language identification m the lmalt lnf Control 10 (1967), 447--474
	19	GOLD, E.M.Complexity of automaton identification from given data lnf Control 37 (1978), 302-320
	20	GONZAL~Z, R.C, AND TltOMASON, M.G.Syntacnc Pattern Recogmtwn, An Introducoon. Addison- Wesley, Reading, Mass, 1978.
	21	HARRISON, M.A Introducnon to Swttchmg and Automata Theory. McGraw-i-hU, New York. 1965
	22	M.A. A. Harrison , M. A. Harrison, Introduction to Formal Language Theory, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978
	23	HARTMANIS, J., AND STEARNS, R.E A lgebrmc Theory of Sequennal Machines Prentice-Hall, EAglewood Cliffs, N J, 1966
	24	John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	25	ITOGA, S Y. A new heuristic for inferring regular grammars. IEEE Trans Pattern Anal Mach. lntelL PAMI-3 (1981), 191-197,
	26	MCNAUGHTON, R.The loop complexity of pure-group events, lnf Control 11 (1967), 167-176
	27	Robert McNaughton, Parenthesis Grammars, Journal of the ACM (JACM), v.14 n.3, p.490-500, July 1967 [doi>10.1145/321406.321411]
	28	Robert McNaughton , Seymour A. Papert, Counter-Free Automata (M.I.T. research monograph no. 65), The MIT Press, 1971
	29	MICLET, L.Regular mferenees with a tad-clustenng method IEEE Trans Syst. Man Cybern. SMC- 10 (1980), 737-743
	30	PERLES, M, RAB1/q, M.O, AND SHAMIR, E.The theory of definite automata, IEEE Trans. Electron Comput EC-12 (1963), 233-243
	31	SMITH, C.H An inductive ,nference blbhography Tech Rep CSD TR 323, Computer Science Dep., Purdue Unw, Lafayette, Ind, 1979
	32	Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
	33	ZALCSTEIN, Y Locally testable languages J. Comput. Syst. Sct 6 (1972), 151-167

CITED BY 44

	Hellis Tamm , Esko Ukkonen, Bideterministic automata and minimal representations of regular languages, Theoretical Computer Science, v.328 n.1-2, p.135-149, 29 November 2004
	Philip Swann, Review of "Towards a theory of cognition and computing" by J. Gerard Wolff. Ellis Horwood Limited 1991., Computational Linguistics, v.18 n.3, September 1992
	Pedro García , Manuel Vázquez de Parga , Damián López, On the efficient construction of quasi-reversible automata for reversible languages, Information Processing Letters, v.107 n.1, p.13-17, June, 2008
	Samuel F. Pilato , Robert C. Berwick, Reversible automata and induction of the English auxiliary system, Proceedings of the 23rd annual meeting on Association for Computational Linguistics, p.70-75, July 08-12, 1985, Chicago, Illinois
	Leona F. Fass, Learning context-free languages from their structured sentences, ACM SIGACT News, v.15 n.3, p.24-35, Summer-Fall 1983
	Kathleen Fisher , David Walker , Kenny Q. Zhu , Peter White, From dirt to shovels: fully automatic tool generation from ad hoc data, ACM SIGPLAN Notices, v.43 n.1, January 2008
	Yasuki Kakishita , Kazutoshi Sasahara , Tetsuro Nishino , Miki Takahasi , Kazuo Okanoya, Ethological data mining: an automata-based approach to extract behavioral units and rules, Data Mining and Knowledge Discovery, v.18 n.3, p.446-471, June 2009
	Michel Latteux , Aurélien Lemay , Yves Roos , Alain Terlutte, Identification of biRFSA languages, Theoretical Computer Science, v.356 n.1, p.212-223, 5 May 2006
	Daowen Qiu, Automata theory based on quantum logic: Reversibilities and pushdown automata, Theoretical Computer Science, v.386 n.1-2, p.38-56, October, 2007
	Robert C. Berwick, Bounded context parsing and easy learnability, Proceedings of the 22nd annual meeting on Association for Computational Linguistics, p.20-23, July 02-06, 1984, Stanford, California
	Hiroki Arimura , Hiroki Ishizaka , Takeshi Shinohara, Polynomial time inference of a subclass of context-free transformations, Proceedings of the fifth annual workshop on Computational learning theory, p.136-143, July 27-29, 1992, Pittsburgh, Pennsylvania, United States
	Andrey Burago, Learning structurally reversible context-free grammars from queries and counterexamples in polynomial time, Proceedings of the seventh annual conference on Computational learning theory, p.140-146, July 12-15, 1994, New Brunswick, New Jersey, United States
	Ryo Yoshinaka, Learning efficiency of very simple grammars from positive data, Theoretical Computer Science, v.410 n.19, p.1807-1825, April, 2009
	François Denis, Learning Regular Languages from Simple Positive Examples, Machine Learning, v.44 n.1-2, p.37-66, July-August 2001
	Ronald L. Rivest , Robert E. Schapire, Diversity-based inference of finite automata, Journal of the ACM (JACM), v.41 n.3, p.555-589, May 1994
	Mitsuo Wakatsuki , Etsuji Tomita, Polynomial Time Identification of Strict Deterministic Restricted One-Counter Automata in Some Class from Positive Data, IEICE - Transactions on Information and Systems, v.E91-D n.6, p.1704-1718, June 2008
	Martin Kutrib , Andreas Malcher, Fast reversible language recognition using cellular automata, Information and Computation, v.206 n.9-10, p.1142-1151, September, 2008
	André L. Martins , H. Sofia Pinto , Arlindo L. Oliveira, USING GRAMMATICAL INFERENCE TECHNIQUES TO LEARN ONTOLOGIES THAT DESCRIBE THE STRUCTURE OF DOMAIN INSTANCES, Applied Artificial Intelligence, v.22 n.1-2, p.139-167, January 2008
	Valter Crescenzi , Paolo Merialdo, WRAPPER INFERENCE FOR AMBIGUOUS WEB PAGES, Applied Artificial Intelligence, v.22 n.1-2, p.21-52, January 2008
	Stefan Raeymaekers , Maurice Bruynooghe , Jan Bussche, Learning (k,l)-contextual tree languages for information extraction from web pages, Machine Learning, v.71 n.2-3, p.155-183, June 2008
	Martin Jansche, Learning Local Transductions Is Hard, Journal of Logic, Language and Information, v.13 n.4, p.439-455, March 2004
	Paul Rodriguez, Simple Recurrent Networks Learn Context-Free and Context-Sensitive Languages by Counting, Neural Computation, v.13 n.9, p.2093-2118, September 2001
	Pedro García , José Ruiz, Learning in varieties of the form *VLI** from positive data, Theoretical Computer Science, v.362 n.1, p.100-114, 11 October 2006
	Takashi Yokomori, Polynomial-time identification of very simple grammars from positive data, Theoretical Computer Science, v.298 n.1, p.179-206, 4 April 2003
	Ondej Klíma , Libor Polák, On varieties of meet automata, Theoretical Computer Science, v.407 n.1-3, p.278-289, November, 2008
	Anirban Dasgupta , Ravi Kumar , Amit Sasturkar, De-duping URLs via rewrite rules, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA
	Naoki Abe, Polynomial learnability and locality of formal grammars, Proceedings of the 26th annual meeting on Association for Computational Linguistics, p.225-232, June 07-10, 1988, Buffalo, New York
	Denis Béchet , Annie Foret, k-Valued non-associative Lambek grammars are learnable from generalized functor-argument structures, Theoretical Computer Science, v.355 n.2, p.139-152, 11 April 2006
	Henning Fernau, Even linear simple matrix languages: formal language properties and grammatical inference, Theoretical Computer Science, v.289 n.1, p.425-456, 23 October 2002
	Jonathan E. Cook , Alexander L. Wolf, Discovering models of software processes from event-based data, ACM Transactions on Software Engineering and Methodology (TOSEM), v.7 n.3, p.215-249, July 1998
	Ganesh R. Baliga , John Case , Sanjay Jain, Synthesizing enumeration techniques for language learning, Proceedings of the ninth annual conference on Computational learning theory, p.169-180, June 28-July 01, 1996, Desenzano del Garda, Italy
	Valter Crescenzi , Giansalvatore Mecca, Automatic information extraction from large websites, Journal of the ACM (JACM), v.51 n.5, p.731-779, September 2004
	Henning Fernau, Algorithms for learning regular expressions from positive data, Information and Computation, v.207 n.4, p.521-541, April, 2009
	Leonid (Aryeh) Kontorovich , Corinna Cortes , Mehryar Mohri, Kernel methods for learning languages, Theoretical Computer Science, v.405 n.3, p.223-236, October, 2008
	Takashi Yokomori , Satoshi Kobayashi, Learning Local Languages and Their Application to DNA Sequence Analysis, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.10, p.1067-1079, October 1998
	Henning Fernau, Identification of function distinguishable languages, Theoretical Computer Science, v.290 n.3, p.1679-1711, 3 January 2003
	Yen Kaow Ng , Takeshi Shinohara, Developments from enquiries into the learnability of the pattern languages from positive data, Theoretical Computer Science, v.397 n.1-3, p.150-165, May, 2008
	Steffen Lange , Thomas Zeugmann , Sandra Zilles, Learning indexed families of recursive languages from positive data: A survey, Theoretical Computer Science, v.397 n.1-3, p.194-232, May, 2008
	Leonard Pitt , Leslie G. Valiant, Computational limitations on learning from examples, Journal of the ACM (JACM), v.35 n.4, p.965-984, Oct. 1988
	H. Fernau, Identifying Terminal Distinguishable Languages, Annals of Mathematics and Artificial Intelligence, v.40 n.3-4, p.263-281, March 2004
	Yasubumi Sakakibara, Grammatical Inference in Bioinformatics, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.7, p.1051-1062, July 2005
	P. García , E. Vidal, Inference of k-Testable Languages in the Strict Sense and Application to Syntactic Pattern Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.9, p.920-925, September 1990
	Dana Angluin , Carl H. Smith, Inductive Inference: Theory and Methods, ACM Computing Surveys (CSUR), v.15 n.3, p.237-269, Sept. 1983
	J. Oncina , P. García , E. Vidal, Learning Subsequential Transducers for Pattern Recognition Interpretation Tasks, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.5, p.448-458, May 1993