On Counting Functions of Languages View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2018-08-05

AUTHORS

Oscar H. Ibarra , Ian McQuillan , Bala Ravikumar

ABSTRACT

We study counting-regular languages—these are languages L for which there is a regular language such that the number of strings of length n in L and are the same for all n. Our main result is that the languages accepted by the class of one-way unambiguous, reversal-bounded pushdown automata (’s) are counting-regular. This generalizes an old result of Baron and Kuich that such languages have rational generating functions. We show that this result is the best possible in the sense that the claim does not hold for either 2-ambiguous ’s, unambiguous ’s with no reversal-bound, and other generalizations. We provide a number of examples of languages that are (and are not) counting-regular. We study closure properties of the class of context-free languages that are counting-regular. We also show the undecidability of counting-regularity of ’s. The undecidability is shown to hold for even the subclass of 2-ambiguous ’s which make only one reversal on the stack. More... »

PAGES

429-440

References to SciGraph publications

Book

TITLE

Developments in Language Theory

ISBN

978-3-319-98653-1
978-3-319-98654-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-98654-8_35

DOI

http://dx.doi.org/10.1007/978-3-319-98654-8_35

DIMENSIONS

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


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/2004", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Linguistics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/20", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Language, Communication and Culture", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of California, Santa Barbara", 
          "id": "https://www.grid.ac/institutes/grid.133342.4", 
          "name": [
            "Department of Computer Science, University of California, 93106, Santa Barbara, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ibarra", 
        "givenName": "Oscar H.", 
        "id": "sg:person.014743313653.06", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014743313653.06"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Saskatchewan", 
          "id": "https://www.grid.ac/institutes/grid.25152.31", 
          "name": [
            "Department of Computer Science, University of Saskatchewan, S7N 5A9, Saskatoon, SK, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "McQuillan", 
        "givenName": "Ian", 
        "id": "sg:person.012723725175.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012723725175.00"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sonoma State University", 
          "id": "https://www.grid.ac/institutes/grid.263759.c", 
          "name": [
            "Department of Computer Science, Sonoma State University, 94928, Rohnert Park, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ravikumar", 
        "givenName": "Bala", 
        "id": "sg:person.016351317217.60", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016351317217.60"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/950620.950625", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003120605"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/322047.322058", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009177217"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2007.07.032", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022607513"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0019-9958(81)90634-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043091754"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2016.07.022", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052572370"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1051/ita/1993270201491", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1083550422"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.ic.2017.04.008", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1085090399"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1109710706", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-73235-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1109710706", 
          "https://doi.org/10.1007/978-3-642-73235-5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-73235-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1109710706", 
          "https://doi.org/10.1007/978-3-642-73235-5"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2018-08-05", 
    "datePublishedReg": "2018-08-05", 
    "description": "We study counting-regular languages\u2014these are languages L for which there is a regular language such that the number of strings of length n in L and are the same for all n. Our main result is that the languages accepted by the class of one-way unambiguous, reversal-bounded pushdown automata (\u2019s) are counting-regular. This generalizes an old result of Baron and Kuich that such languages have rational generating functions. We show that this result is the best possible in the sense that the claim does not hold for either 2-ambiguous \u2019s, unambiguous \u2019s with no reversal-bound, and other generalizations. We provide a number of examples of languages that are (and are not) counting-regular. We study closure properties of the class of context-free languages that are counting-regular. We also show the undecidability of counting-regularity of \u2019s. The undecidability is shown to hold for even the subclass of 2-ambiguous \u2019s which make only one reversal on the stack.", 
    "editor": [
      {
        "familyName": "Hoshi", 
        "givenName": "Mizuho", 
        "type": "Person"
      }, 
      {
        "familyName": "Seki", 
        "givenName": "Shinnosuke", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-98654-8_35", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-98653-1", 
        "978-3-319-98654-8"
      ], 
      "name": "Developments in Language Theory", 
      "type": "Book"
    }, 
    "name": "On Counting Functions of Languages", 
    "pagination": "429-440", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-98654-8_35"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "dc2c91c96b5f19296c432cfdc2f4b0279fba0966348137557e6215a8f419fc35"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1106005253"
        ]
      }
    ], 
    "publisher": {
      "location": "Cham", 
      "name": "Springer International Publishing", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-98654-8_35", 
      "https://app.dimensions.ai/details/publication/pub.1106005253"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T05:02", 
    "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/0000000325_0000000325/records_100812_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-319-98654-8_35"
  }
]
 

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/978-3-319-98654-8_35'

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/978-3-319-98654-8_35'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-98654-8_35'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-98654-8_35'


 

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

117 TRIPLES      23 PREDICATES      35 URIs      19 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-98654-8_35 schema:about anzsrc-for:20
2 anzsrc-for:2004
3 schema:author Nd53633f7b36c430b966142a9684275fb
4 schema:citation sg:pub.10.1007/978-3-642-73235-5
5 https://app.dimensions.ai/details/publication/pub.1109710706
6 https://doi.org/10.1016/j.ic.2017.04.008
7 https://doi.org/10.1016/j.tcs.2007.07.032
8 https://doi.org/10.1016/j.tcs.2016.07.022
9 https://doi.org/10.1016/s0019-9958(81)90634-3
10 https://doi.org/10.1051/ita/1993270201491
11 https://doi.org/10.1145/322047.322058
12 https://doi.org/10.1145/950620.950625
13 schema:datePublished 2018-08-05
14 schema:datePublishedReg 2018-08-05
15 schema:description We study counting-regular languages—these are languages L for which there is a regular language such that the number of strings of length n in L and are the same for all n. Our main result is that the languages accepted by the class of one-way unambiguous, reversal-bounded pushdown automata (’s) are counting-regular. This generalizes an old result of Baron and Kuich that such languages have rational generating functions. We show that this result is the best possible in the sense that the claim does not hold for either 2-ambiguous ’s, unambiguous ’s with no reversal-bound, and other generalizations. We provide a number of examples of languages that are (and are not) counting-regular. We study closure properties of the class of context-free languages that are counting-regular. We also show the undecidability of counting-regularity of ’s. The undecidability is shown to hold for even the subclass of 2-ambiguous ’s which make only one reversal on the stack.
16 schema:editor Nee6213f1c69e4f8bb8a244a98e5434bf
17 schema:genre chapter
18 schema:inLanguage en
19 schema:isAccessibleForFree false
20 schema:isPartOf Na6571d2d1fca42539da8274b8e30a0a3
21 schema:name On Counting Functions of Languages
22 schema:pagination 429-440
23 schema:productId N2662f4fbac5e46dc92dd4a9e3e3d5a30
24 N4484032ade7b41a6a28f9fab0fff6f12
25 Na7800d27efa84cb4915142c724d4ddab
26 schema:publisher Nf2c836b002984eb39b62a0763be899a2
27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1106005253
28 https://doi.org/10.1007/978-3-319-98654-8_35
29 schema:sdDatePublished 2019-04-16T05:02
30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
31 schema:sdPublisher N320bb1baf7af4884878b880bd95421f3
32 schema:url https://link.springer.com/10.1007%2F978-3-319-98654-8_35
33 sgo:license sg:explorer/license/
34 sgo:sdDataset chapters
35 rdf:type schema:Chapter
36 N16cb179df4c445f7b49d6b2bbd297f15 schema:familyName Seki
37 schema:givenName Shinnosuke
38 rdf:type schema:Person
39 N2662f4fbac5e46dc92dd4a9e3e3d5a30 schema:name dimensions_id
40 schema:value pub.1106005253
41 rdf:type schema:PropertyValue
42 N320bb1baf7af4884878b880bd95421f3 schema:name Springer Nature - SN SciGraph project
43 rdf:type schema:Organization
44 N4484032ade7b41a6a28f9fab0fff6f12 schema:name readcube_id
45 schema:value dc2c91c96b5f19296c432cfdc2f4b0279fba0966348137557e6215a8f419fc35
46 rdf:type schema:PropertyValue
47 N47851f7ea5a64ba8ae245827f477fd3a rdf:first sg:person.012723725175.00
48 rdf:rest Nca1768aa40b84a5da06ac1a0f3ffb561
49 N5351a0646fd84cf4827b8a5ecc0fdaac rdf:first N16cb179df4c445f7b49d6b2bbd297f15
50 rdf:rest rdf:nil
51 N6f5fbaa7f05144e1a18d2b074dffad1e schema:familyName Hoshi
52 schema:givenName Mizuho
53 rdf:type schema:Person
54 Na6571d2d1fca42539da8274b8e30a0a3 schema:isbn 978-3-319-98653-1
55 978-3-319-98654-8
56 schema:name Developments in Language Theory
57 rdf:type schema:Book
58 Na7800d27efa84cb4915142c724d4ddab schema:name doi
59 schema:value 10.1007/978-3-319-98654-8_35
60 rdf:type schema:PropertyValue
61 Nca1768aa40b84a5da06ac1a0f3ffb561 rdf:first sg:person.016351317217.60
62 rdf:rest rdf:nil
63 Nd53633f7b36c430b966142a9684275fb rdf:first sg:person.014743313653.06
64 rdf:rest N47851f7ea5a64ba8ae245827f477fd3a
65 Nee6213f1c69e4f8bb8a244a98e5434bf rdf:first N6f5fbaa7f05144e1a18d2b074dffad1e
66 rdf:rest N5351a0646fd84cf4827b8a5ecc0fdaac
67 Nf2c836b002984eb39b62a0763be899a2 schema:location Cham
68 schema:name Springer International Publishing
69 rdf:type schema:Organisation
70 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
71 schema:name Language, Communication and Culture
72 rdf:type schema:DefinedTerm
73 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
74 schema:name Linguistics
75 rdf:type schema:DefinedTerm
76 sg:person.012723725175.00 schema:affiliation https://www.grid.ac/institutes/grid.25152.31
77 schema:familyName McQuillan
78 schema:givenName Ian
79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012723725175.00
80 rdf:type schema:Person
81 sg:person.014743313653.06 schema:affiliation https://www.grid.ac/institutes/grid.133342.4
82 schema:familyName Ibarra
83 schema:givenName Oscar H.
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014743313653.06
85 rdf:type schema:Person
86 sg:person.016351317217.60 schema:affiliation https://www.grid.ac/institutes/grid.263759.c
87 schema:familyName Ravikumar
88 schema:givenName Bala
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016351317217.60
90 rdf:type schema:Person
91 sg:pub.10.1007/978-3-642-73235-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109710706
92 https://doi.org/10.1007/978-3-642-73235-5
93 rdf:type schema:CreativeWork
94 https://app.dimensions.ai/details/publication/pub.1109710706 schema:CreativeWork
95 https://doi.org/10.1016/j.ic.2017.04.008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1085090399
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1016/j.tcs.2007.07.032 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022607513
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1016/j.tcs.2016.07.022 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052572370
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1016/s0019-9958(81)90634-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043091754
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1051/ita/1993270201491 schema:sameAs https://app.dimensions.ai/details/publication/pub.1083550422
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1145/322047.322058 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009177217
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1145/950620.950625 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003120605
108 rdf:type schema:CreativeWork
109 https://www.grid.ac/institutes/grid.133342.4 schema:alternateName University of California, Santa Barbara
110 schema:name Department of Computer Science, University of California, 93106, Santa Barbara, CA, USA
111 rdf:type schema:Organization
112 https://www.grid.ac/institutes/grid.25152.31 schema:alternateName University of Saskatchewan
113 schema:name Department of Computer Science, University of Saskatchewan, S7N 5A9, Saskatoon, SK, Canada
114 rdf:type schema:Organization
115 https://www.grid.ac/institutes/grid.263759.c schema:alternateName Sonoma State University
116 schema:name Department of Computer Science, Sonoma State University, 94928, Rohnert Park, CA, USA
117 rdf:type schema:Organization
 




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


...