LINEAR CONJUNCTIVE GRAMMARS AND ONE-TURN SYNCHRONIZED ALTERNATING PUSHDOWN AUTOMATA

In this paper we introduce a subfamily of synchronized alternating pushdown automata, one-turn synchronized alternating pushdown automata, which accept the same class of languages as those generated by linear conjunctive grammars. This equivalence of models of computation is analogous to the classic...

Full description

Saved in:
Bibliographic Details
Published in:International journal of foundations of computer science 2014-09, Vol.25 (6), p.781-802
Main Authors: AIZIKOWITZ, TAMAR, KAMINSKI, MICHAEL
Format: Article
Language:English
Subjects:
Computation
Computer simulation
Equivalence
Foundations
Grammars
Mathematical models
Strengthening
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites cdi_FETCH-LOGICAL-c2996-67a830ffef603ca54354634f491ed1040ccf49d8b1b814fc8e22ee1363675cb33
container_end_page 802
container_issue 6
container_start_page 781
container_title International journal of foundations of computer science
container_volume 25
creator AIZIKOWITZ, TAMAR
KAMINSKI, MICHAEL
description In this paper we introduce a subfamily of synchronized alternating pushdown automata, one-turn synchronized alternating pushdown automata, which accept the same class of languages as those generated by linear conjunctive grammars. This equivalence of models of computation is analogous to the classical equivalence between one-turn pushdown automata and linear grammars, thus strengthening the claim of synchronized alternating pushdown automata as a natural counterpart of conjunctive grammars.
doi_str_mv 10.1142/S0129054114500336
format article
fullrecord <record><control><sourceid>proquest_world</sourceid><recordid>TN_cdi_proquest_miscellaneous_1651401921</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>1651401921</sourcerecordid><originalsourceid>FETCH-LOGICAL-c2996-67a830ffef603ca54354634f491ed1040ccf49d8b1b814fc8e22ee1363675cb33</originalsourceid><addsrcrecordid>eNplkE1Lw0AQhhdRsGh_gLeAFy_Rnf1KclzS2EbSjeRD0UtItxuItE3Ntoj_3pSKB3uaGd7nHWZehG4A3wMw8pBjIAHmbBg4xpSKMzQCL6CuoB49R6OD7B70SzS2tl1gCATlhIsRypNYRTJzwlQ9lSos4pfImWZyPpdZ7kg1cVIVuUWZKSd_U-EsS1X8Hk0cmRRRpmQRq6nzXOazSfqqHFkW6VwW8hpdNPXKmvFvvULlY1SEMzdJp3EoE1eTIBCu8Gqf4qYxjcBU15xRzgRlDQvALAEzrPXQL_0FLHxgjfYNIcYAFVR4XC8ovUJ3x73bvvvcG7ur1q3VZrWqN6bb2woEBzb8SmBAb_-hH92-3wzXVQRAMMGJjwcKjpTuO2t701Tbvl3X_XcFuDokXZ0kPXjw0fPV9aul1a3Z7Nqm1X_WU8sPwjF2wA</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2116465280</pqid></control><display><type>article</type><title>LINEAR CONJUNCTIVE GRAMMARS AND ONE-TURN SYNCHRONIZED ALTERNATING PUSHDOWN AUTOMATA</title><source>World Scientific Journals</source><creator>AIZIKOWITZ, TAMAR ; KAMINSKI, MICHAEL</creator><creatorcontrib>AIZIKOWITZ, TAMAR ; KAMINSKI, MICHAEL</creatorcontrib><description>In this paper we introduce a subfamily of synchronized alternating pushdown automata, one-turn synchronized alternating pushdown automata, which accept the same class of languages as those generated by linear conjunctive grammars. This equivalence of models of computation is analogous to the classical equivalence between one-turn pushdown automata and linear grammars, thus strengthening the claim of synchronized alternating pushdown automata as a natural counterpart of conjunctive grammars.</description><identifier>ISSN: 0129-0541</identifier><identifier>EISSN: 1793-6373</identifier><identifier>DOI: 10.1142/S0129054114500336</identifier><language>eng</language><publisher>Singapore: World Scientific Publishing Company</publisher><subject>Computation ; Computer simulation ; Equivalence ; Foundations ; Grammars ; Mathematical models ; Strengthening</subject><ispartof>International journal of foundations of computer science, 2014-09, Vol.25 (6), p.781-802</ispartof><rights>2014, World Scientific Publishing Company</rights><rights>2014. World Scientific Publishing Company</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c2996-67a830ffef603ca54354634f491ed1040ccf49d8b1b814fc8e22ee1363675cb33</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.worldscientific.com/doi/reader/10.1142/S0129054114500336$$EPDF$$P50$$Gworldscientific$$H</linktopdf><link.rule.ids>314,780,784,3213,4872,27924,27925,55587</link.rule.ids></links><search><creatorcontrib>AIZIKOWITZ, TAMAR</creatorcontrib><creatorcontrib>KAMINSKI, MICHAEL</creatorcontrib><title>LINEAR CONJUNCTIVE GRAMMARS AND ONE-TURN SYNCHRONIZED ALTERNATING PUSHDOWN AUTOMATA</title><title>International journal of foundations of computer science</title><description>In this paper we introduce a subfamily of synchronized alternating pushdown automata, one-turn synchronized alternating pushdown automata, which accept the same class of languages as those generated by linear conjunctive grammars. This equivalence of models of computation is analogous to the classical equivalence between one-turn pushdown automata and linear grammars, thus strengthening the claim of synchronized alternating pushdown automata as a natural counterpart of conjunctive grammars.</description><subject>Computation</subject><subject>Computer simulation</subject><subject>Equivalence</subject><subject>Foundations</subject><subject>Grammars</subject><subject>Mathematical models</subject><subject>Strengthening</subject><issn>0129-0541</issn><issn>1793-6373</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2014</creationdate><recordtype>article</recordtype><recordid>eNplkE1Lw0AQhhdRsGh_gLeAFy_Rnf1KclzS2EbSjeRD0UtItxuItE3Ntoj_3pSKB3uaGd7nHWZehG4A3wMw8pBjIAHmbBg4xpSKMzQCL6CuoB49R6OD7B70SzS2tl1gCATlhIsRypNYRTJzwlQ9lSos4pfImWZyPpdZ7kg1cVIVuUWZKSd_U-EsS1X8Hk0cmRRRpmQRq6nzXOazSfqqHFkW6VwW8hpdNPXKmvFvvULlY1SEMzdJp3EoE1eTIBCu8Gqf4qYxjcBU15xRzgRlDQvALAEzrPXQL_0FLHxgjfYNIcYAFVR4XC8ovUJ3x73bvvvcG7ur1q3VZrWqN6bb2woEBzb8SmBAb_-hH92-3wzXVQRAMMGJjwcKjpTuO2t701Tbvl3X_XcFuDokXZ0kPXjw0fPV9aul1a3Z7Nqm1X_WU8sPwjF2wA</recordid><startdate>201409</startdate><enddate>201409</enddate><creator>AIZIKOWITZ, TAMAR</creator><creator>KAMINSKI, MICHAEL</creator><general>World Scientific Publishing Company</general><general>World Scientific Publishing Co. Pte., Ltd</general><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>201409</creationdate><title>LINEAR CONJUNCTIVE GRAMMARS AND ONE-TURN SYNCHRONIZED ALTERNATING PUSHDOWN AUTOMATA</title><author>AIZIKOWITZ, TAMAR ; KAMINSKI, MICHAEL</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c2996-67a830ffef603ca54354634f491ed1040ccf49d8b1b814fc8e22ee1363675cb33</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2014</creationdate><topic>Computation</topic><topic>Computer simulation</topic><topic>Equivalence</topic><topic>Foundations</topic><topic>Grammars</topic><topic>Mathematical models</topic><topic>Strengthening</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>AIZIKOWITZ, TAMAR</creatorcontrib><creatorcontrib>KAMINSKI, MICHAEL</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>International journal of foundations of computer science</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>AIZIKOWITZ, TAMAR</au><au>KAMINSKI, MICHAEL</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>LINEAR CONJUNCTIVE GRAMMARS AND ONE-TURN SYNCHRONIZED ALTERNATING PUSHDOWN AUTOMATA</atitle><jtitle>International journal of foundations of computer science</jtitle><date>2014-09</date><risdate>2014</risdate><volume>25</volume><issue>6</issue><spage>781</spage><epage>802</epage><pages>781-802</pages><issn>0129-0541</issn><eissn>1793-6373</eissn><abstract>In this paper we introduce a subfamily of synchronized alternating pushdown automata, one-turn synchronized alternating pushdown automata, which accept the same class of languages as those generated by linear conjunctive grammars. This equivalence of models of computation is analogous to the classical equivalence between one-turn pushdown automata and linear grammars, thus strengthening the claim of synchronized alternating pushdown automata as a natural counterpart of conjunctive grammars.</abstract><cop>Singapore</cop><pub>World Scientific Publishing Company</pub><doi>10.1142/S0129054114500336</doi><tpages>22</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0129-0541
ispartof International journal of foundations of computer science, 2014-09, Vol.25 (6), p.781-802
issn 0129-0541
1793-6373
language eng
recordid cdi_proquest_miscellaneous_1651401921
source World Scientific Journals
subjects Computation
Computer simulation
Equivalence
Foundations
Grammars
Mathematical models
Strengthening
title LINEAR CONJUNCTIVE GRAMMARS AND ONE-TURN SYNCHRONIZED ALTERNATING PUSHDOWN AUTOMATA
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-06T18%3A20%3A26IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_world&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=LINEAR%20CONJUNCTIVE%20GRAMMARS%20AND%20ONE-TURN%20SYNCHRONIZED%20ALTERNATING%20PUSHDOWN%20AUTOMATA&rft.jtitle=International%20journal%20of%20foundations%20of%20computer%20science&rft.au=AIZIKOWITZ,%20TAMAR&rft.date=2014-09&rft.volume=25&rft.issue=6&rft.spage=781&rft.epage=802&rft.pages=781-802&rft.issn=0129-0541&rft.eissn=1793-6373&rft_id=info:doi/10.1142/S0129054114500336&rft_dat=%3Cproquest_world%3E1651401921%3C/proquest_world%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c2996-67a830ffef603ca54354634f491ed1040ccf49d8b1b814fc8e22ee1363675cb33%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2116465280&rft_id=info:pmid/&rfr_iscdi=true