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 N37ee739d56df4ea28b083b33a52b44a0
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 Nf95fac411af24742ba0446c70fa9c044
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N9676662e2ebb40c8aaa28e60fbf5fc06
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 N6c3343fac1da490caffe64c3f8930d6d
45 Nd1fdf7d0257942b7a1153b40ce40eeea
46 schema:publisher Nbafedbb5e9154bbe809028180b595b25
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 Nbca562a1289044968d8b5716ca668190
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 N0e9a8a3d3a01407395e5affa1a6dbe89 rdf:first N7c46b0a41b7149cdaa657df1766e9ef1
57 rdf:rest rdf:nil
58 N37ee739d56df4ea28b083b33a52b44a0 rdf:first sg:person.012144356031.48
59 rdf:rest Nb5ff757eb25540feb709e23badf9cd01
60 N6c3343fac1da490caffe64c3f8930d6d schema:name doi
61 schema:value 10.1007/11779148_38
62 rdf:type schema:PropertyValue
63 N74314c6ae2bf4c0789e9bf829c230409 schema:familyName Ibarra
64 schema:givenName Oscar H.
65 rdf:type schema:Person
66 N7c46b0a41b7149cdaa657df1766e9ef1 schema:familyName Dang
67 schema:givenName Zhe
68 rdf:type schema:Person
69 N9676662e2ebb40c8aaa28e60fbf5fc06 schema:isbn 978-3-540-35428-4
70 978-3-540-35430-7
71 schema:name Developments in Language Theory
72 rdf:type schema:Book
73 Nb5ff757eb25540feb709e23badf9cd01 rdf:first sg:person.015674303467.99
74 rdf:rest rdf:nil
75 Nbafedbb5e9154bbe809028180b595b25 schema:name Springer Nature
76 rdf:type schema:Organisation
77 Nbca562a1289044968d8b5716ca668190 schema:name Springer Nature - SN SciGraph project
78 rdf:type schema:Organization
79 Nd1fdf7d0257942b7a1153b40ce40eeea schema:name dimensions_id
80 schema:value pub.1033516850
81 rdf:type schema:PropertyValue
82 Nf95fac411af24742ba0446c70fa9c044 rdf:first N74314c6ae2bf4c0789e9bf829c230409
83 rdf:rest N0e9a8a3d3a01407395e5affa1a6dbe89
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)


...