Generalized finite automata theory with an application to a decision problem of second-order logic View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1968-03

AUTHORS

J. W. Thatcher, J. B. Wright

ABSTRACT

Many of the important concepts and results of conventional finite automata theory are developed for a generalization in which finite algebras take the place of finite automata. The standard closure theorems are proved for the class of sets “recognizable” by finite algebras, and a generalization of Kleene's regularity theory is presented. The theorems of the generalized theory are then applied to obtain a positive solution to a decision problem of second-order logic. More... »

PAGES

57-81

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf01691346

DOI

http://dx.doi.org/10.1007/bf01691346

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1038809008


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "IBM Research \u2013 Thomas J. Watson Research Center", 
          "id": "https://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "IBM Watson Research Center, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Thatcher", 
        "givenName": "J. W.", 
        "id": "sg:person.010457263475.37", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010457263475.37"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Research \u2013 Thomas J. Watson Research Center", 
          "id": "https://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "IBM Watson Research Center, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wright", 
        "givenName": "J. B.", 
        "id": "sg:person.014243322135.79", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014243322135.79"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/320924.320931", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011852161"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/s0002-9947-1963-0158822-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027419225"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/malq.19600060105", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029582399"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/s0002-9939-1958-0093479-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030428338"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/s0002-9947-1961-0139530-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043986220"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/zamm.19620421306", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047733352"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/zamm.19620420104", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052996124"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/s0305004100013463", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053865215"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1147/rd.32.0114", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1063181561"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1515/9781400882618-002", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086534352"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4064/fm-47-1-57-103", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1091702670"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1968-03", 
    "datePublishedReg": "1968-03-01", 
    "description": "Many of the important concepts and results of conventional finite automata theory are developed for a generalization in which finite algebras take the place of finite automata. The standard closure theorems are proved for the class of sets \u201crecognizable\u201d by finite algebras, and a generalization of Kleene's regularity theory is presented. The theorems of the generalized theory are then applied to obtain a positive solution to a decision problem of second-order logic.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf01691346", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1317508", 
        "issn": [
          "0025-5661"
        ], 
        "name": "Mathematical Systems Theory", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "2"
      }
    ], 
    "name": "Generalized finite automata theory with an application to a decision problem of second-order logic", 
    "pagination": "57-81", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "b8de75ec543e91a3d3b84873b0c613798c2045f72cc0639df29cd3e487359523"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01691346"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1038809008"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01691346", 
      "https://app.dimensions.ai/details/publication/pub.1038809008"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T13:30", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000370_0000000370/records_46751_00000002.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/BF01691346"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bf01691346'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bf01691346'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01691346'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01691346'


 

This table displays all metadata directly associated to this object as RDF triples.

100 TRIPLES      21 PREDICATES      38 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01691346 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N9ffcefc176304c45bc7704728acc55a5
4 schema:citation https://doi.org/10.1002/malq.19600060105
5 https://doi.org/10.1002/zamm.19620420104
6 https://doi.org/10.1002/zamm.19620421306
7 https://doi.org/10.1017/s0305004100013463
8 https://doi.org/10.1090/s0002-9939-1958-0093479-4
9 https://doi.org/10.1090/s0002-9947-1961-0139530-9
10 https://doi.org/10.1090/s0002-9947-1963-0158822-2
11 https://doi.org/10.1145/320924.320931
12 https://doi.org/10.1147/rd.32.0114
13 https://doi.org/10.1515/9781400882618-002
14 https://doi.org/10.4064/fm-47-1-57-103
15 schema:datePublished 1968-03
16 schema:datePublishedReg 1968-03-01
17 schema:description Many of the important concepts and results of conventional finite automata theory are developed for a generalization in which finite algebras take the place of finite automata. The standard closure theorems are proved for the class of sets “recognizable” by finite algebras, and a generalization of Kleene's regularity theory is presented. The theorems of the generalized theory are then applied to obtain a positive solution to a decision problem of second-order logic.
18 schema:genre research_article
19 schema:inLanguage en
20 schema:isAccessibleForFree false
21 schema:isPartOf Nb11ec72c4cee4a329ec91368f62e5751
22 Nd3c79ed1284d4dc8a7e5b66694c5c498
23 sg:journal.1317508
24 schema:name Generalized finite automata theory with an application to a decision problem of second-order logic
25 schema:pagination 57-81
26 schema:productId N4a79baa4d48144a79a676722c87e9c56
27 Ndffdd332e3b2476a8ccd104e2294c928
28 Nf0150f3c8e434b86a49cbdd8a59762aa
29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038809008
30 https://doi.org/10.1007/bf01691346
31 schema:sdDatePublished 2019-04-11T13:30
32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
33 schema:sdPublisher N32c89f2bfdd8454e9b9115f5e4cd87ce
34 schema:url http://link.springer.com/10.1007/BF01691346
35 sgo:license sg:explorer/license/
36 sgo:sdDataset articles
37 rdf:type schema:ScholarlyArticle
38 N102e5d83177b42b683caa43b5d4464fa rdf:first sg:person.014243322135.79
39 rdf:rest rdf:nil
40 N32c89f2bfdd8454e9b9115f5e4cd87ce schema:name Springer Nature - SN SciGraph project
41 rdf:type schema:Organization
42 N4a79baa4d48144a79a676722c87e9c56 schema:name readcube_id
43 schema:value b8de75ec543e91a3d3b84873b0c613798c2045f72cc0639df29cd3e487359523
44 rdf:type schema:PropertyValue
45 N9ffcefc176304c45bc7704728acc55a5 rdf:first sg:person.010457263475.37
46 rdf:rest N102e5d83177b42b683caa43b5d4464fa
47 Nb11ec72c4cee4a329ec91368f62e5751 schema:volumeNumber 2
48 rdf:type schema:PublicationVolume
49 Nd3c79ed1284d4dc8a7e5b66694c5c498 schema:issueNumber 1
50 rdf:type schema:PublicationIssue
51 Ndffdd332e3b2476a8ccd104e2294c928 schema:name doi
52 schema:value 10.1007/bf01691346
53 rdf:type schema:PropertyValue
54 Nf0150f3c8e434b86a49cbdd8a59762aa schema:name dimensions_id
55 schema:value pub.1038809008
56 rdf:type schema:PropertyValue
57 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
58 schema:name Mathematical Sciences
59 rdf:type schema:DefinedTerm
60 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
61 schema:name Pure Mathematics
62 rdf:type schema:DefinedTerm
63 sg:journal.1317508 schema:issn 0025-5661
64 schema:name Mathematical Systems Theory
65 rdf:type schema:Periodical
66 sg:person.010457263475.37 schema:affiliation https://www.grid.ac/institutes/grid.481554.9
67 schema:familyName Thatcher
68 schema:givenName J. W.
69 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010457263475.37
70 rdf:type schema:Person
71 sg:person.014243322135.79 schema:affiliation https://www.grid.ac/institutes/grid.481554.9
72 schema:familyName Wright
73 schema:givenName J. B.
74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014243322135.79
75 rdf:type schema:Person
76 https://doi.org/10.1002/malq.19600060105 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029582399
77 rdf:type schema:CreativeWork
78 https://doi.org/10.1002/zamm.19620420104 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052996124
79 rdf:type schema:CreativeWork
80 https://doi.org/10.1002/zamm.19620421306 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047733352
81 rdf:type schema:CreativeWork
82 https://doi.org/10.1017/s0305004100013463 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053865215
83 rdf:type schema:CreativeWork
84 https://doi.org/10.1090/s0002-9939-1958-0093479-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030428338
85 rdf:type schema:CreativeWork
86 https://doi.org/10.1090/s0002-9947-1961-0139530-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043986220
87 rdf:type schema:CreativeWork
88 https://doi.org/10.1090/s0002-9947-1963-0158822-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027419225
89 rdf:type schema:CreativeWork
90 https://doi.org/10.1145/320924.320931 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011852161
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1147/rd.32.0114 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063181561
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1515/9781400882618-002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086534352
95 rdf:type schema:CreativeWork
96 https://doi.org/10.4064/fm-47-1-57-103 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091702670
97 rdf:type schema:CreativeWork
98 https://www.grid.ac/institutes/grid.481554.9 schema:alternateName IBM Research – Thomas J. Watson Research Center
99 schema:name IBM Watson Research Center, USA
100 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...