NDLI: On generalized finite automata and unrestricted generative grammars

Please wait, while we are loading the content...

Formal languages and power series

An algebraic theory of recursive definitions and recursive languages

Loop schemata

Some results concerning efficient and optimal algorithms

Fast matrix multiplication

Linear representation of tree structure - a mathematical theory of parenthesis-free notations

On generalized finite automata and unrestricted generative grammars

Some results in tree automata

Block structure (Extended Abstract): Retention or deletion?

On the parallel computation of local operations

An iteration theorem for one-counter languages.

Intersection-closed full AFL and the recursively enumerable languages

Absolutely parallel grammars and two-way deterministic finite-state transducers

Addressable data graphs (Extended Abstract)

The complexity of theorem-proving procedures

The care and feeding of LR(k) grammars

Domolki's algorithm applied to generalized overlap resolvable grammars

An algorithm generating the decision table of a deterministic bottom up parser for a subset of context free grammars

A decision procedure for generalized sequential mapability-onto of regular sets

Algebraic structure theory of stochastic machines

Complexity of formal translations and speed-up results

Classification of computable functions by primitive recursive classes

Complexity classes of partial recursive functions (Preliminary Version)

On generalized finite automata and unrestricted generative grammars

Content Provider	ACM Digital Library
Author	Buttelmann, H. W.
Abstract	The notion of the graphical representation of a “canonical derivation” is extended to semi-thue systems; the graphs are called “derivation structures.” Derivation structures are distinguished from phrase structures and generative grammars are distinguished from phrase structure grammars. The distinctions disappear only in the context free case. This paper considers generative grammars and derivation structures. (A subsequent paper will consider phrase-structure grammars and phrase structures.) The notion of generalized finite automaton (tree automaton) is extended to systems which process arbitrary labeled directed ordered acyclic graphs. We study a restriction of these automata which process derivation structures. Analogous to the hierarchy of generative grammars, it is shown that there is a hierarchy of generalized finite automata which recognize the same languages. Their structure-defining relationship is a generalization of the context free case, i.e., the structures recognized by the automata are projections of the structures defined by the grammars. The proofs give algorithms for constructing the automata from the grammars and the grammars from the automata.
Starting Page	63
Ending Page	77
Page Count	15
File Format	PDF
DOI	10.1145/800157.805039
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1971-05-03
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

IOS Press On the Generative Power of ω-Grammars and ω-Automata

On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata

Syntax-semantics systems as structure manipulation systems:phrase structure grammars and generalized finite automata

Adaptive Grammars - State of Art of the Applied Research on Adaptive Automata

Linear grammars with one-sided contexts and their automaton representation

Finite automata and non-self-embedding grammars

On the Intersection of Finite State Automata and De nite Clause Grammars

An adaptable FSA simulator

Local Grammars and Their Representation by Finite Automata (1993)

On generalized finite automata and unrestricted generative grammars

Similar Documents

IOS Press On the Generative Power of ω-Grammars and ω-Automata

On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata

Syntax-semantics systems as structure manipulation systems:phrase structure grammars and generalized finite automata

Adaptive Grammars - State of Art of the Applied Research on Adaptive Automata

Linear grammars with one-sided contexts and their automaton representation

Finite automata and non-self-embedding grammars

On the Intersection of Finite State Automata and De nite Clause Grammars

An adaptable FSA simulator

Local Grammars and Their Representation by Finite Automata (1993)

On generalized finite automata and unrestricted generative grammars