×

Found 221 Documents (Results 1–100)

Traversability, reconfiguration, and reachability in the gadget framework. (English) Zbl 07556560

Mutzel, Petra (ed.) et al., WALCOM: algorithms and computation. 16th international conference and workshops, WALCOM 2022, Jember, Indonesia, March 24–26, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13174, 47-58 (2022).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Cons-free programs and complexity classes between logspace and ptime. (English) Zbl 07453191

Fribourg, Laurent (ed.) et al., Proceedings of the eighth international workshop on verification and program transformation and the seventh workshop on Horn clauses for verification and synthesis, VPT/HCVS 2020, Dublin, Ireland, April 25–26, 2020. Waterloo: Open Publishing Association (OPA). Electron. Proc. Theor. Comput. Sci. (EPTCS) 320, 65-79 (2020).
MSC:  68N30 68Q60
PDFBibTeX XMLCite
Full Text: arXiv Link

Expressive power of broadcast consensus protocols. (English) Zbl 07649939

Fokkink, Wan (ed.) et al., 30th international conference on concurrency theory, CONCUR 2019, Amsterdam, the Netherlands, August 27–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 140, Article 31, 16 p. (2019).
MSC:  68Q85
PDFBibTeX XMLCite
Full Text: DOI arXiv

From normal functors to logarithmic space queries. (English) Zbl 07561616

Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 123, 15 p. (2019).
MSC:  68Nxx 68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Supportive oracles for parameterized polynomial-time sub-linear-space computations in relation to L, NL, and P. (English) Zbl 1527.68081

Gopal, T. V. (ed.) et al., Theory and applications of models of computation. 15th annual conference, TAMC 2019, Kitakyushu, Japan, April 13–16, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11436, 659-673 (2019).
MSC:  68Q15 68Q27
PDFBibTeX XMLCite
Full Text: DOI arXiv

Expressivity within second-order transitive-closure logic. (English) Zbl 1528.68141

Ghica, Dan R. (ed.) et al., 27th EACSL annual conference on computer science logic, CSL 2018, Birmingham, United Kingdom, September 4–8, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 119, Article 22, 18 p. (2018).
MSC:  68Q19 03B16 03C13
PDFBibTeX XMLCite
Full Text: DOI arXiv

Topological sorting with regular constraints. (English) Zbl 1499.68166

Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 115, 14 p. (2018).
MSC:  68Q45 68Q17 68R10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Pseudo-deterministic proofs. (English) Zbl 1462.68049

Karlin, Anna R. (ed.), 9th innovations in theoretical computer science conference, ITCS 2018, Cambridge, MA, USA, January 11–14, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 94, Article 17, 18 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

The 2CNF Boolean formula satisfiability problem and the linear space hypothesis. (English) Zbl 1441.68102

Larsen, Kim G. (ed.) et al., 42nd international symposium on mathematical foundations of computer science, MFCS 2017, August 21–25, 2017, Aalborg, Denmark. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 83, Article 62, 14 p. (2017).
MSC:  68Q25 68R07 68T20
PDFBibTeX XMLCite
Full Text: DOI arXiv

Generalized predecessor existence problems for Boolean finite dynamical systems. (English) Zbl 1441.68140

Larsen, Kim G. (ed.) et al., 42nd international symposium on mathematical foundations of computer science, MFCS 2017, August 21–25, 2017, Aalborg, Denmark. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 83, Article 8, 13 p. (2017).
MSC:  68Q80 37B15 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Clocked population protocols. (English) Zbl 1379.68020

Proceedings of the 2017 ACM symposium on principles of distributed computing, PODC ’17, Washington, DC, USA, July 25–27, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4992-5). 431-440 (2017).
MSC:  68M14 68M12
PDFBibTeX XMLCite
Full Text: DOI

Optimal reachability in divergent weighted timed games. (English) Zbl 1486.68092

Esparza, Javier (ed.) et al., Foundations of software science and computation structures. 20th international conference, FOSSACS 2017, held as part of the European joint conferences on theory and practice of software, ETAPS 2017, Uppsala, Sweden, April 22–29, 2017. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 10203, 162-178 (2017).
MSC:  68Q45 91A05 91A80
PDFBibTeX XMLCite
Full Text: DOI arXiv HAL

Inconsistency-tolerant querying of description logic knowledge bases. (English) Zbl 1358.68285

Pan, Jeff Z. (ed.) et al., Reasoning web. Logical foundation of knowledge graph construction and query answering. 12th international summer school 2016, Aberdeen, UK, September 5–9, 2016. Tutorial lectures. Cham: Springer (ISBN 978-3-319-49492-0/pbk; 978-3-319-49493-7/ebook). Lecture Notes in Computer Science 9885, 156-202 (2017).
MSC:  68T35 68T27 68T30
PDFBibTeX XMLCite
Full Text: DOI HAL

The almost equivalence by asymptotic probabilities for regular languages and its computational complexities. (English) Zbl 1478.68132

Cantone, Domenico (ed.) et al., Proceedings of the seventh international symposium on games, automata, logics and formal verification, GandALF 2016, Catania, Italy, September 14–16, 2016. Waterloo: Open Publishing Association (OPA). Electron. Proc. Theor. Comput. Sci. (EPTCS) 226, 272-286 (2016).
MSC:  68Q45 68Q19 68Q25
PDFBibTeX XMLCite
Full Text: arXiv Link

A logical characterization of small 2NFAs. (English) Zbl 1379.68225

Han, Yo-Sub (ed.) et al., Implementation and application of automata. 21st international conference, CIAA 2016, Seoul, South Korea, July 19–22, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-40945-0/pbk; 978-3-319-40946-7/ebook). Lecture Notes in Computer Science 9705, 163-175 (2016).
PDFBibTeX XMLCite
Full Text: DOI

Alternating demon space is closed under complement and other simulations for sublogarithmic space. (English) Zbl 1359.68095

Brlek, Srečko (ed.) et al., Developments in language theory. 20th international conference, DLT 2016, Montréal, Canada, July 25–28, 2016. Proceedings. Berlin: Springer (ISBN 978-3-662-53131-0/pbk; 978-3-662-53132-7/ebook). Lecture Notes in Computer Science 9840, 190-202 (2016).
MSC:  68Q15 68Q05
PDFBibTeX XMLCite
Full Text: DOI

Space complexity of the directed reachability problem over surface-embedded graphs. (English) Zbl 1345.68149

Agrawal, Manindra (ed.) et al., Perspectives in computational complexity. The Somenath Biswas anniversary volume. Selected papers based on the presentations at the workshop, Kanpur, India, Summer 2012. Cham: Birkhäuser/Springer (ISBN 978-3-319-05445-2/hbk; 978-3-319-05446-9/ebook). Progress in Computer Science and Applied Logic 26, 37-49 (2014).
MSC:  68Q15 05C85 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Complexity theory basics: NP and NL. (English) Zbl 1345.68143

Agrawal, Manindra (ed.) et al., Perspectives in computational complexity. The Somenath Biswas anniversary volume. Selected papers based on the presentations at the workshop, Kanpur, India, Summer 2012. Cham: Birkhäuser/Springer (ISBN 978-3-319-05445-2/hbk; 978-3-319-05446-9/ebook). Progress in Computer Science and Applied Logic 26, 1-22 (2014).
MSC:  68Q15 68-02
PDFBibTeX XMLCite
Full Text: DOI

Turing machines for dummies. Why representations do matter. (English) Zbl 1298.68092

Bieliková, Mária (ed.) et al., SOFSEM 2012: Theory and practice of computer science. 38th conference on current trends in theory and practice of computer science, Špindlerův Mlýn, Czech Republic, January 21–27, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-27659-0/pbk). Lecture Notes in Computer Science 7147, 14-30 (2012).
MSC:  68Q05
PDFBibTeX XMLCite
Full Text: DOI

Planarity testing revisited. (English) Zbl 1331.68102

Ogihara, Mitsunori (ed.) et al., Theory and applications of models of computation. 8th annual conference, TAMC 2011, Tokyo, Japan, May 23–25, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-20876-8/pbk). Lecture Notes in Computer Science 6648, 540-551 (2011).
MSC:  68Q25 05C10 05C85
PDFBibTeX XMLCite
Full Text: DOI arXiv

Descriptional and computational complexity of finite automata. (English) Zbl 1234.68211

Dediu, Adrian Horia (ed.) et al., Language and automata theory and applications. Third international conference, LATA 2009, Tarragona, Spain, April 2–8, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-00981-5/pbk). Lecture Notes in Computer Science 5457, 23-42 (2009).
MSC:  68Q45 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Lattice automata. (English) Zbl 1132.68455

Cook, Byron (ed.) et al., Verification, model checking, and abstract interpretation. 8th international conference, VMCAI 2007, Nice, France, January 14–16, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-69735-0/pbk). Lecture Notes in Computer Science 4349, 199-213 (2007).
MSC:  68Q45 03B44 68Q60
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field

all top 3

Software