×

Found 517 Documents (Results 1–100)

Cellular automata are generic. (English) Zbl 1476.68161

Dal Lago, Ugo (ed.) et al., Proceedings of the tenth international workshop on developments of computational models, DCM 2014, Vienna, Austria, July 13, 2014. Waterloo: Open Publishing Association (OPA). Electron. Proc. Theor. Comput. Sci. (EPTCS) 179, 17-32 (2015).
MSC:  68Q80 68Q04
PDFBibTeX XMLCite
Full Text: arXiv Link

Encoding the factorisation calculus. (English) Zbl 1476.68182

Crafa, Silvia (ed.) et al., Proceedings of the combined 22th international workshop on expressiveness in concurrency and 12th workshop on structural operational semantics, EXPRESS/SOS 2015, Madrid, Spain, August 31, 2015. Waterloo: Open Publishing Association (OPA). Electron. Proc. Theor. Comput. Sci. (EPTCS) 190, 76-90 (2015).
MSC:  68Q85 03B40
PDFBibTeX XMLCite
Full Text: arXiv Link

Executable behaviour and the \(\pi \)-calculus (extended abstract). (English) Zbl 1433.68255

Knight, Sophia (ed.) et al., Proceedings of the 8th interaction and concurrency experience workshop, ICE’15, Grenoble, France, June 4–5, 2015. Waterloo: Open Publishing Association (OPA). Electron. Proc. Theor. Comput. Sci. (EPTCS) 189, 37-52 (2015).
MSC:  68Q85 68Q09 68Q55
PDFBibTeX XMLCite
Full Text: arXiv Link

Safety, liveness and run-time refinement for modular process-aware information systems with dynamic sub processes. (English) Zbl 1427.68188

Bjørner, Nikolaj (ed.) et al., FM 2015: formal methods. 20th international symposium, Oslo, Norway, June 24–26, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9109, 143-160 (2015).
MSC:  68Q85 68Q45 68Q60
PDFBibTeX XMLCite
Full Text: DOI

Fairness for infinite-state systems. (English) Zbl 1420.68122

Baier, Christel (ed.) et al., Tools and algorithms for the construction and analysis of systems. 21st international conference, TACAS 2015, held as part of the European joint conferences on theory and practice of software, ETAPS 2015, London, UK, April 11–18, 2015. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 9035, 384-398 (2015).
MSC:  68Q60
PDFBibTeX XMLCite
Full Text: DOI

On the computational complexity of MapReduce. (English) Zbl 1394.68176

Moses, Yoram (ed.), Distributed computing. 29th international symposium, DISC 2015, Tokyo, Japan, October 7–9, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-48652-8/pbk; 978-3-662-48653-5/ebook). Lecture Notes in Computer Science 9363, 1-15 (2015).
MSC:  68Q25 68Q05 68Q10 68Q15 68Q45
PDFBibTeX XMLCite
Full Text: DOI arXiv

Timed pushdown automata revisited. (English) Zbl 1401.68157

Proceedings of the 2015 30th annual ACM/IEEE symposium on logic in computer science, LICS 2015, Kyoto, Japan, July 6–10, 2015. Los Alamitos, CA: IEEE Computer Society (ISBN 978-1-4799-8875-4). 738-749 (2015).
MSC:  68Q45 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

A unifying approach to the Gamma question. (English) Zbl 1395.03019

Proceedings of the 2015 30th annual ACM/IEEE symposium on logic in computer science, LICS 2015, Kyoto, Japan, July 6–10, 2015. Los Alamitos, CA: IEEE Computer Society (ISBN 978-1-4799-8875-4). 585-596 (2015).
MSC:  03D32 03D28
PDFBibTeX XMLCite
Full Text: DOI

Parallelism and synchronization in an infinitary context. (English) Zbl 1401.68030

Proceedings of the 2015 30th annual ACM/IEEE symposium on logic in computer science, LICS 2015, Kyoto, Japan, July 6–10, 2015. Los Alamitos, CA: IEEE Computer Society (ISBN 978-1-4799-8875-4). 559-572 (2015).
MSC:  68N18 03B70 68Q05 68Q10 68Q55
PDFBibTeX XMLCite
Full Text: DOI arXiv

Regularity preserving but not reflecting encodings. (English) Zbl 1394.68210

Proceedings of the 2015 30th annual ACM/IEEE symposium on logic in computer science, LICS 2015, Kyoto, Japan, July 6–10, 2015. Los Alamitos, CA: IEEE Computer Society (ISBN 978-1-4799-8875-4). 535-546 (2015).
MSC:  68Q45 03D05
PDFBibTeX XMLCite
Full Text: DOI arXiv

Feedback Turing computability, and Turing computability as feedback. (English) Zbl 1401.68074

Proceedings of the 2015 30th annual ACM/IEEE symposium on logic in computer science, LICS 2015, Kyoto, Japan, July 6–10, 2015. Los Alamitos, CA: IEEE Computer Society (ISBN 978-1-4799-8875-4). 523-534 (2015).
MSC:  68Q05 03D10
PDFBibTeX XMLCite
Full Text: DOI

Incomputability emergent, and higher type computation. (English) Zbl 1401.03069

Sommaruga, Giovanni (ed.) et al., Turing’s revolution. The impact of his ideas about computability. Cham: Birkhäuser/Springer (ISBN 978-3-319-22155-7/hbk; 978-3-319-22156-4/ebook). 311-329 (2015).
MSC:  03D10 03-03 01A60
PDFBibTeX XMLCite
Full Text: DOI

Proving things about the informal. (English) Zbl 1384.03070

Sommaruga, Giovanni (ed.) et al., Turing’s revolution. The impact of his ideas about computability. Cham: Birkhäuser/Springer (ISBN 978-3-319-22155-7/hbk; 978-3-319-22156-4/ebook). 283-296 (2015).
MSC:  03A05
PDFBibTeX XMLCite
Full Text: DOI

Proof theoretic analysis by iterated reflection. (English) Zbl 1402.03079

Sommaruga, Giovanni (ed.) et al., Turing’s revolution. The impact of his ideas about computability. Cham: Birkhäuser/Springer (ISBN 978-3-319-22155-7/hbk; 978-3-319-22156-4/ebook). 225-270 (2015).
MSC:  03F15 03F30
PDFBibTeX XMLCite
Full Text: DOI

The information content of typical reals. (English) Zbl 1403.03067

Sommaruga, Giovanni (ed.) et al., Turing’s revolution. The impact of his ideas about computability. Cham: Birkhäuser/Springer (ISBN 978-3-319-22155-7/hbk; 978-3-319-22156-4/ebook). 207-224 (2015).
MSC:  03D28
PDFBibTeX XMLCite
Full Text: DOI

Generalizing computability theory to abstract algebras. (English) Zbl 1403.03077

Sommaruga, Giovanni (ed.) et al., Turing’s revolution. The impact of his ideas about computability. Cham: Birkhäuser/Springer (ISBN 978-3-319-22155-7/hbk; 978-3-319-22156-4/ebook). 127-160 (2015).
MSC:  03D75 03D78
PDFBibTeX XMLCite
Full Text: DOI Link

Theses for computation and recursion on concrete and abstract structures. (English) Zbl 1403.03004

Sommaruga, Giovanni (ed.) et al., Turing’s revolution. The impact of his ideas about computability. Cham: Birkhäuser/Springer (ISBN 978-3-319-22155-7/hbk; 978-3-319-22156-4/ebook). 105-126 (2015).
PDFBibTeX XMLCite
Full Text: DOI

The stored-program universal computer: did Zuse anticipate Turing and von Neumann? (English) Zbl 1474.68008

Sommaruga, Giovanni (ed.) et al., Turing’s revolution. The impact of his ideas about computability. Cham: Birkhäuser/Springer. 43-101 (2015).
MSC:  68-03 01A60
PDFBibTeX XMLCite
Full Text: DOI

Algorithms: from Al-Khwarizmi to Turing and beyond. (English) Zbl 1384.68003

Sommaruga, Giovanni (ed.) et al., Turing’s revolution. The impact of his ideas about computability. Cham: Birkhäuser/Springer (ISBN 978-3-319-22155-7/hbk; 978-3-319-22156-4/ebook). 29-42 (2015).
PDFBibTeX XMLCite
Full Text: DOI

Conceptual confluence in 1936: Post and Turing. (English) Zbl 1400.01008

Sommaruga, Giovanni (ed.) et al., Turing’s revolution. The impact of his ideas about computability. Cham: Birkhäuser/Springer (ISBN 978-3-319-22155-7/hbk; 978-3-319-22156-4/ebook). 3-27 (2015).
PDFBibTeX XMLCite
Full Text: DOI

Incompressible functions, relative-error extractors, and the power of nondeterministic reductions (extended abstract). (English) Zbl 1388.68040

Zuckerman, David (ed.), 30th conference on computational complexity, CCC’15, Portland, OR, USA, June 17–19, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-81-1). LIPIcs – Leibniz International Proceedings in Informatics 33, 582-600 (2015).
MSC:  68Q05 68Q10 94C10
PDFBibTeX XMLCite
Full Text: DOI

Circuits with medium fan-in. (English) Zbl 1388.68047

Zuckerman, David (ed.), 30th conference on computational complexity, CCC’15, Portland, OR, USA, June 17–19, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-81-1). LIPIcs – Leibniz International Proceedings in Informatics 33, 381-391 (2015).
MSC:  68Q05 68Q10 68Q17 94C10
PDFBibTeX XMLCite
Full Text: DOI

Deterministic identity testing for sum of read-once oblivious arithmetic branching programs. (English) Zbl 1388.68118

Zuckerman, David (ed.), 30th conference on computational complexity, CCC’15, Portland, OR, USA, June 17–19, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-81-1). LIPIcs – Leibniz International Proceedings in Informatics 33, 323-346 (2015).
MSC:  68Q25 68Q05
PDFBibTeX XMLCite
Full Text: DOI

Subexponential size hitting sets for bounded depth multilinear formulas. (English) Zbl 1388.68132

Zuckerman, David (ed.), 30th conference on computational complexity, CCC’15, Portland, OR, USA, June 17–19, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-81-1). LIPIcs – Leibniz International Proceedings in Informatics 33, 304-322 (2015).
MSC:  68Q25 68Q05 68Q17 68W20 94C10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Verifiable stream computation and Arthur-Merlin communication. (English) Zbl 1388.68061

Zuckerman, David (ed.), 30th conference on computational complexity, CCC’15, Portland, OR, USA, June 17–19, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-81-1). LIPIcs – Leibniz International Proceedings in Informatics 33, 217-243 (2015).
MSC:  68Q10 68Q15
PDFBibTeX XMLCite
Full Text: DOI

Factors of low individual degree polynomials. (English) Zbl 1388.68320

Zuckerman, David (ed.), 30th conference on computational complexity, CCC’15, Portland, OR, USA, June 17–19, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-81-1). LIPIcs – Leibniz International Proceedings in Informatics 33, 198-216 (2015).
MSC:  68W30 68Q05 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Lower bounds for depth three arithmetic circuits with small bottom fanin. (English) Zbl 1388.68089

Zuckerman, David (ed.), 30th conference on computational complexity, CCC’15, Portland, OR, USA, June 17–19, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-81-1). LIPIcs – Leibniz International Proceedings in Informatics 33, 158-208 (2015).
MSC:  68Q17 68Q05 68Q10
PDFBibTeX XMLCite
Full Text: DOI

Faster deterministic volume estimation in the oracle model via thin lattice coverings. (English) Zbl 1378.68168

Arge, Lars (ed.) et al., 31st international symposium on computational geometry, SoCG’15, Eindhoven, Netherlands, June 22–25, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-83-5). LIPIcs – Leibniz International Proceedings in Informatics 34, 704-718 (2015).
MSC:  68U05 52A20 52C07 52C17 68Q05 68Q25 68W25
PDFBibTeX XMLCite
Full Text: DOI

Pattern overlap implies runaway growth in hierarchical tile systems. (English) Zbl 1378.68039

Arge, Lars (ed.) et al., 31st international symposium on computational geometry, SoCG’15, Eindhoven, Netherlands, June 22–25, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-83-5). LIPIcs – Leibniz International Proceedings in Informatics 34, 360-373 (2015).
MSC:  68Q05
PDFBibTeX XMLCite
Full Text: DOI

A stable marriage requires communication. (English) Zbl 1372.68125

Indyk, Piotr (ed.), Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4–6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-374-7; 978-1-61197-373-0/ebook). 1003-1017 (2015).
MSC:  68Q25 68Q05 68Q10 68Q17 91B68
PDFBibTeX XMLCite
Full Text: DOI

Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels. (English) Zbl 1371.68212

Indyk, Piotr (ed.), Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4–6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-374-7; 978-1-61197-373-0/ebook). 616-629 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Universal computation with arbitrary polyomino tiles in non-cooperative self-assembly. (English) Zbl 1371.68084

Indyk, Piotr (ed.), Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4–6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-374-7; 978-1-61197-373-0/ebook). 148-167 (2015).
MSC:  68Q05 05B50
PDFBibTeX XMLCite
Full Text: DOI arXiv

Mutual upper bounds of size and time for a Turing machine and a Markov-Post algorithm for mutual simulations. (English. Russian original) Zbl 1370.68093

Vestn. St. Petersbg. Univ., Math. 48, No. 2, 72-74 (2015); translation from Vestn. St-Peterbg. Univ., Ser. I, Mat. Mekh. Astron. 2(60), No. 2, 190-193 (2015).
MSC:  68Q05 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Forward and backward bisimulations for chemical reaction networks. (English) Zbl 1374.68204

Aceto, Luca (ed.) et al., 26th international conference on concurrency theory, CONCUR’15, Madrid, Spain, September 1–4, 2015. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-91-0). LIPIcs – Leibniz International Proceedings in Informatics 42, 226-239 (2015).
MSC:  68Q05 68Q10 68Q85 92C40
PDFBibTeX XMLCite
Full Text: DOI arXiv

Infinite and bi-infinite words with decidable monadic theories. (English) Zbl 1434.03102

Kreutzer, Stephan (ed.), 24th EACSL annual conference and 29th workshop on computer science logic, CSL’15, Berlin, Germany, September 7–10, 2015. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 41, 472-486 (2015).
MSC:  03D05 03B16
PDFBibTeX XMLCite
Full Text: DOI

Confluence of layered rewrite systems. (English) Zbl 1373.68276

Kreutzer, Stephan (ed.), 24th EACSL annual conference and 29th workshop on computer science logic, CSL’15, Berlin, Germany, September 7–10, 2015. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-90-3). LIPIcs – Leibniz International Proceedings in Informatics 41, 423-440 (2015).
MSC:  68Q42
PDFBibTeX XMLCite
Full Text: DOI arXiv

Separating decision tree complexity from subcube partition complexity. (English) Zbl 1375.68061

Garg, Naveen (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Proceedings of the 18th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2015) and the 19th international workshop on randomization and computation (RANDOM 2015), Princeton, NJ, USA, August 24–26, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-89-7). LIPIcs – Leibniz International Proceedings in Informatics 40, 915-930 (2015).
MSC:  68Q17 68Q05 68W20
PDFBibTeX XMLCite
Full Text: DOI arXiv

Two structural results for low degree polynomials and applications. (English) Zbl 1375.11074

Garg, Naveen (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Proceedings of the 18th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2015) and the 19th international workshop on randomization and computation (RANDOM 2015), Princeton, NJ, USA, August 24–26, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-89-7). LIPIcs – Leibniz International Proceedings in Informatics 40, 680-709 (2015).
MSC:  11T06 11Y16 68Q05 68Q10 68W20 94C10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Universal sketches for the frequency negative moments and other decreasing streaming sums. (English) Zbl 1375.68211

Garg, Naveen (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Proceedings of the 18th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2015) and the 19th international workshop on randomization and computation (RANDOM 2015), Princeton, NJ, USA, August 24–26, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-89-7). LIPIcs – Leibniz International Proceedings in Informatics 40, 591-605 (2015).
MSC:  68W25 68Q05
PDFBibTeX XMLCite
Full Text: DOI arXiv

Zero-one laws for sliding windows and universal sketches. (English) Zbl 1375.68050

Garg, Naveen (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Proceedings of the 18th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2015) and the 19th international workshop on randomization and computation (RANDOM 2015), Princeton, NJ, USA, August 24–26, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-89-7). LIPIcs – Leibniz International Proceedings in Informatics 40, 573-590 (2015).
MSC:  68Q05 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Parameterized algorithms for deletion to \((r,\ell)\)-graphs. (English) Zbl 1366.68368

Harsha, Prahladh (ed.) et al., 35th IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS 2015, Bangalore, India, December 16–18, 2015. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-97-2). LIPIcs – Leibniz International Proceedings in Informatics 45, 420-433 (2015).
MSC:  68W25 68Q25 68R10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Filter Results by …

Document Type

Database

all top 5

Author

all top 5

Serial

all top 3

Main Field

all top 3

Software