Language Equations with Complementation View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

Alexander Okhotin , Oksana Yakimova

ABSTRACT

Systems of language equations of the form Xi=ϕi(X1, ..., Xn) (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$1 \leqslant i \leqslant n$\end{document}) are studied, in which every ϕi may contain the operations of concatenation and complementation. The properties of having solutions and of having a unique solution are given mathematical characterizations. As decision problems, the former is NP-complete, while the latter is in co-RE and its decidability remains, in general, open. Uniqueness becomes decidable for a unary alphabet, where it is US-complete, and in the case of linear concatenation, where it is L-complete. The position of the languages defined by these equations in the hierarchy of language families is established. More... »

PAGES

420-432

Book

TITLE

Developments in Language Theory

ISBN

978-3-540-35428-4
978-3-540-35430-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11779148_38

DOI

http://dx.doi.org/10.1007/11779148_38

DIMENSIONS

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


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/20", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Language, Communication and Culture", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Mathematics, University of Turku, Finland", 
          "id": "http://www.grid.ac/institutes/grid.1374.1", 
          "name": [
            "Department of Mathematics, University of Turku, Finland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Okhotin", 
        "givenName": "Alexander", 
        "id": "sg:person.012144356031.48", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012144356031.48"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max-Planck-Institut f\u00fcr Mathematik, Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.461798.5", 
          "name": [
            "Max-Planck-Institut f\u00fcr Mathematik, Bonn, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yakimova", 
        "givenName": "Oksana", 
        "id": "sg:person.015674303467.99", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015674303467.99"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "Systems of language equations of the form Xi=\u03d5i(X1, ..., Xn) (\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$1 \\leqslant i \\leqslant n$\\end{document}) are studied, in which every \u03d5i may contain the operations of concatenation and complementation. The properties of having solutions and of having a unique solution are given mathematical characterizations. As decision problems, the former is NP-complete, while the latter is in co-RE and its decidability remains, in general, open. Uniqueness becomes decidable for a unary alphabet, where it is US-complete, and in the case of linear concatenation, where it is L-complete. The position of the languages defined by these equations in the hierarchy of language families is established.", 
    "editor": [
      {
        "familyName": "Ibarra", 
        "givenName": "Oscar H.", 
        "type": "Person"
      }, 
      {
        "familyName": "Dang", 
        "givenName": "Zhe", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11779148_38", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-35428-4", 
        "978-3-540-35430-7"
      ], 
      "name": "Developments in Language Theory", 
      "type": "Book"
    }, 
    "keywords": [
      "language equations", 
      "operations of concatenation", 
      "language families", 
      "mathematical characterization", 
      "linear concatenation", 
      "unary alphabet", 
      "unique solution", 
      "equations", 
      "decision problem", 
      "language", 
      "solution", 
      "alphabet", 
      "uniqueness", 
      "Co\u2013Re", 
      "concatenation", 
      "\u03d5i", 
      "hierarchy", 
      "problem", 
      "uses", 
      "decidability", 
      "form", 
      "NPs", 
      "properties", 
      "latter", 
      "system", 
      "family", 
      "position", 
      "operation", 
      "cases", 
      "characterization", 
      "complementation"
    ], 
    "name": "Language Equations with Complementation", 
    "pagination": "420-432", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1033516850"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11779148_38"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11779148_38", 
      "https://app.dimensions.ai/details/publication/pub.1033516850"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:15", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_164.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11779148_38"
  }
]
 

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/11779148_38'

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/11779148_38'

Turtle is a human-readable linked data format.

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

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

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


 

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

105 TRIPLES      22 PREDICATES      56 URIs      49 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11779148_38 schema:about anzsrc-for:20
2 anzsrc-for:2004
3 schema:author N3ae33fea39ea4e2f8d87bf03209a480f
4 schema:datePublished 2006
5 schema:datePublishedReg 2006-01-01
6 schema:description Systems of language equations of the form Xi=ϕi(X1, ..., Xn) (\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$1 \leqslant i \leqslant n$\end{document}) are studied, in which every ϕi may contain the operations of concatenation and complementation. The properties of having solutions and of having a unique solution are given mathematical characterizations. As decision problems, the former is NP-complete, while the latter is in co-RE and its decidability remains, in general, open. Uniqueness becomes decidable for a unary alphabet, where it is US-complete, and in the case of linear concatenation, where it is L-complete. The position of the languages defined by these equations in the hierarchy of language families is established.
7 schema:editor N06b429d8cd624edbaefad8d661e1d00d
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Ne6c917f8e2e0460aaad9c4347aecb752
11 schema:keywords Co–Re
12 NPs
13 alphabet
14 cases
15 characterization
16 complementation
17 concatenation
18 decidability
19 decision problem
20 equations
21 family
22 form
23 hierarchy
24 language
25 language equations
26 language families
27 latter
28 linear concatenation
29 mathematical characterization
30 operation
31 operations of concatenation
32 position
33 problem
34 properties
35 solution
36 system
37 unary alphabet
38 unique solution
39 uniqueness
40 uses
41 ϕi
42 schema:name Language Equations with Complementation
43 schema:pagination 420-432
44 schema:productId N4b20a5f6b5e74cd2a18c9d5cbba85c52
45 N821087728bf64f3a97a27fb07b1cc004
46 schema:publisher Nd6d13046aa8b4a069cc92b84ce2943a3
47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033516850
48 https://doi.org/10.1007/11779148_38
49 schema:sdDatePublished 2022-08-04T17:15
50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
51 schema:sdPublisher N7d5fc8c86e3b40a9b8a8ea6ac8f3080e
52 schema:url https://doi.org/10.1007/11779148_38
53 sgo:license sg:explorer/license/
54 sgo:sdDataset chapters
55 rdf:type schema:Chapter
56 N06b429d8cd624edbaefad8d661e1d00d rdf:first Nf580d5a71c9840759074f606067a2a2f
57 rdf:rest N5f79da2906974c0ea0247e6b406d9ef4
58 N27ca4fe0b45e4ac599a28a48ad97b3d5 rdf:first sg:person.015674303467.99
59 rdf:rest rdf:nil
60 N2a11c118d84f42dcbb97a48e177f3c7f schema:familyName Dang
61 schema:givenName Zhe
62 rdf:type schema:Person
63 N3ae33fea39ea4e2f8d87bf03209a480f rdf:first sg:person.012144356031.48
64 rdf:rest N27ca4fe0b45e4ac599a28a48ad97b3d5
65 N4b20a5f6b5e74cd2a18c9d5cbba85c52 schema:name dimensions_id
66 schema:value pub.1033516850
67 rdf:type schema:PropertyValue
68 N5f79da2906974c0ea0247e6b406d9ef4 rdf:first N2a11c118d84f42dcbb97a48e177f3c7f
69 rdf:rest rdf:nil
70 N7d5fc8c86e3b40a9b8a8ea6ac8f3080e schema:name Springer Nature - SN SciGraph project
71 rdf:type schema:Organization
72 N821087728bf64f3a97a27fb07b1cc004 schema:name doi
73 schema:value 10.1007/11779148_38
74 rdf:type schema:PropertyValue
75 Nd6d13046aa8b4a069cc92b84ce2943a3 schema:name Springer Nature
76 rdf:type schema:Organisation
77 Ne6c917f8e2e0460aaad9c4347aecb752 schema:isbn 978-3-540-35428-4
78 978-3-540-35430-7
79 schema:name Developments in Language Theory
80 rdf:type schema:Book
81 Nf580d5a71c9840759074f606067a2a2f schema:familyName Ibarra
82 schema:givenName Oscar H.
83 rdf:type schema:Person
84 anzsrc-for:20 schema:inDefinedTermSet anzsrc-for:
85 schema:name Language, Communication and Culture
86 rdf:type schema:DefinedTerm
87 anzsrc-for:2004 schema:inDefinedTermSet anzsrc-for:
88 schema:name Linguistics
89 rdf:type schema:DefinedTerm
90 sg:person.012144356031.48 schema:affiliation grid-institutes:grid.1374.1
91 schema:familyName Okhotin
92 schema:givenName Alexander
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012144356031.48
94 rdf:type schema:Person
95 sg:person.015674303467.99 schema:affiliation grid-institutes:grid.461798.5
96 schema:familyName Yakimova
97 schema:givenName Oksana
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015674303467.99
99 rdf:type schema:Person
100 grid-institutes:grid.1374.1 schema:alternateName Department of Mathematics, University of Turku, Finland
101 schema:name Department of Mathematics, University of Turku, Finland
102 rdf:type schema:Organization
103 grid-institutes:grid.461798.5 schema:alternateName Max-Planck-Institut für Mathematik, Bonn, Germany
104 schema:name Max-Planck-Institut für Mathematik, Bonn, Germany
105 rdf:type schema:Organization
 




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


...