java -Xss1g -Xmx8000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp18-benchmarks/lia/chc-lia-0061.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-8d74a04 [2018-06-20 22:55:20,623 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-20 22:55:20,625 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-20 22:55:20,639 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-20 22:55:20,639 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-20 22:55:20,640 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-20 22:55:20,641 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-20 22:55:20,645 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-20 22:55:20,647 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-20 22:55:20,647 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-20 22:55:20,648 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-20 22:55:20,648 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-20 22:55:20,649 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-20 22:55:20,650 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-20 22:55:20,651 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-20 22:55:20,652 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-20 22:55:20,653 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-20 22:55:20,655 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-20 22:55:20,656 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-20 22:55:20,657 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-20 22:55:20,658 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-20 22:55:20,661 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-20 22:55:20,661 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-20 22:55:20,661 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-20 22:55:20,662 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-20 22:55:20,663 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-20 22:55:20,664 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-20 22:55:20,664 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-20 22:55:20,665 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-20 22:55:20,665 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-20 22:55:20,666 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-20 22:55:20,667 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-20 22:55:20,667 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-20 22:55:20,668 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-20 22:55:20,668 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-20 22:55:20,669 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-20 22:55:20,698 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-20 22:55:20,698 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-20 22:55:20,699 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-20 22:55:20,706 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-20 22:55:20,707 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-20 22:55:20,708 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-20 22:55:20,708 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-20 22:55:20,708 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-20 22:55:20,708 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-20 22:55:20,708 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-20 22:55:20,709 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-20 22:55:20,709 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-20 22:55:20,709 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-20 22:55:20,709 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-20 22:55:20,709 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-20 22:55:20,709 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-20 22:55:20,710 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-20 22:55:20,711 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-20 22:55:20,711 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-20 22:55:20,759 INFO ]: Repository-Root is: /tmp [2018-06-20 22:55:20,772 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-20 22:55:20,778 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-20 22:55:20,779 INFO ]: Initializing SmtParser... [2018-06-20 22:55:20,780 INFO ]: SmtParser initialized [2018-06-20 22:55:20,780 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp18-benchmarks/lia/chc-lia-0061.smt2 [2018-06-20 22:55:20,782 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-20 22:55:20,873 INFO ]: Executing SMT file /storage/chc-comp18-benchmarks/lia/chc-lia-0061.smt2 unknown [2018-06-20 22:55:21,080 INFO ]: Succesfully executed SMT file /storage/chc-comp18-benchmarks/lia/chc-lia-0061.smt2 [2018-06-20 22:55:21,086 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-20 22:55:21,095 INFO ]: Walking toolchain with 4 elements. [2018-06-20 22:55:21,095 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-20 22:55:21,095 INFO ]: Initializing ChcToBoogie... [2018-06-20 22:55:21,095 INFO ]: ChcToBoogie initialized [2018-06-20 22:55:21,099 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 20.06 10:55:21" (1/1) ... [2018-06-20 22:55:21,152 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 10:55:21 Unit [2018-06-20 22:55:21,152 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-20 22:55:21,153 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-20 22:55:21,153 INFO ]: Initializing Boogie Preprocessor... [2018-06-20 22:55:21,153 INFO ]: Boogie Preprocessor initialized [2018-06-20 22:55:21,172 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 10:55:21" (1/1) ... [2018-06-20 22:55:21,172 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 10:55:21" (1/1) ... [2018-06-20 22:55:21,179 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 10:55:21" (1/1) ... [2018-06-20 22:55:21,179 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 10:55:21" (1/1) ... [2018-06-20 22:55:21,183 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 10:55:21" (1/1) ... [2018-06-20 22:55:21,184 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 10:55:21" (1/1) ... [2018-06-20 22:55:21,196 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 10:55:21" (1/1) ... [2018-06-20 22:55:21,198 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-20 22:55:21,199 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-20 22:55:21,199 INFO ]: Initializing RCFGBuilder... [2018-06-20 22:55:21,199 INFO ]: RCFGBuilder initialized [2018-06-20 22:55:21,200 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 10:55:21" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-20 22:55:21,216 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-20 22:55:21,216 INFO ]: Found specification of procedure gotoProc [2018-06-20 22:55:21,216 INFO ]: Found implementation of procedure gotoProc [2018-06-20 22:55:21,216 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-20 22:55:21,216 INFO ]: Found specification of procedure Ultimate.START [2018-06-20 22:55:21,216 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-20 22:55:21,436 INFO ]: Using library mode [2018-06-20 22:55:21,437 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.06 10:55:21 BoogieIcfgContainer [2018-06-20 22:55:21,437 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-20 22:55:21,443 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-20 22:55:21,443 INFO ]: Initializing TraceAbstraction... [2018-06-20 22:55:21,446 INFO ]: TraceAbstraction initialized [2018-06-20 22:55:21,447 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 20.06 10:55:21" (1/3) ... [2018-06-20 22:55:21,447 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@20d06d31 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 20.06 10:55:21, skipping insertion in model container [2018-06-20 22:55:21,447 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 20.06 10:55:21" (2/3) ... [2018-06-20 22:55:21,448 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@20d06d31 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.06 10:55:21, skipping insertion in model container [2018-06-20 22:55:21,448 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.06 10:55:21" (3/3) ... [2018-06-20 22:55:21,449 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-20 22:55:21,461 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-20 22:55:21,476 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-20 22:55:21,525 INFO ]: Using default assertion order modulation [2018-06-20 22:55:21,525 INFO ]: Interprodecural is true [2018-06-20 22:55:21,525 INFO ]: Hoare is false [2018-06-20 22:55:21,525 INFO ]: Compute interpolants for FPandBP [2018-06-20 22:55:21,525 INFO ]: Backedges is TWOTRACK [2018-06-20 22:55:21,525 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-20 22:55:21,525 INFO ]: Difference is false [2018-06-20 22:55:21,525 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-20 22:55:21,525 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-20 22:55:21,539 INFO ]: Start isEmpty. Operand 10 states. [2018-06-20 22:55:21,547 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-20 22:55:21,547 INFO ]: Found error trace [2018-06-20 22:55:21,548 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-20 22:55:21,548 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 22:55:21,552 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-20 22:55:21,554 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 22:55:21,554 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 22:55:21,587 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 22:55:21,587 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-20 22:55:21,587 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 22:55:21,627 INFO ]: Conjunction of SSA is unsat [2018-06-20 22:55:21,689 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 22:55:21,691 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-20 22:55:21,691 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-20 22:55:21,692 INFO ]: Interpolant automaton has 3 states [2018-06-20 22:55:21,702 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-20 22:55:21,703 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-20 22:55:21,705 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-20 22:55:21,752 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 22:55:21,752 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-20 22:55:21,753 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-20 22:55:21,753 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-20 22:55:21,754 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 22:55:21,761 INFO ]: With dead ends: 9 [2018-06-20 22:55:21,761 INFO ]: Without dead ends: 9 [2018-06-20 22:55:21,763 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-20 22:55:21,775 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-20 22:55:21,791 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-20 22:55:21,792 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-20 22:55:21,793 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-20 22:55:21,794 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-20 22:55:21,794 INFO ]: Finished accepts. word is rejected. [2018-06-20 22:55:21,794 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-20 22:55:21,794 INFO ]: Interpolant automaton has 3 states. [2018-06-20 22:55:21,794 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-20 22:55:21,794 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-20 22:55:21,794 INFO ]: Found error trace [2018-06-20 22:55:21,794 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 22:55:21,795 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 22:55:21,795 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-20 22:55:21,795 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 22:55:21,795 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 22:55:21,796 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 22:55:21,796 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-20 22:55:21,796 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 22:55:21,819 INFO ]: Conjunction of SSA is unsat [2018-06-20 22:55:21,912 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 22:55:21,912 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 22:55:21,912 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-20 22:55:21,919 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-20 22:55:21,967 INFO ]: Conjunction of SSA is unsat [2018-06-20 22:55:21,977 INFO ]: Computing forward predicates... [2018-06-20 22:55:22,315 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 22:55:22,335 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-20 22:55:22,335 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-20 22:55:22,336 INFO ]: Interpolant automaton has 5 states [2018-06-20 22:55:22,336 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-20 22:55:22,336 INFO ]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-20 22:55:22,336 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-20 22:55:22,471 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 22:55:22,471 INFO ]: Finished difference Result 11 states and 11 transitions. [2018-06-20 22:55:22,471 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-20 22:55:22,471 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-20 22:55:22,472 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 22:55:22,472 INFO ]: With dead ends: 11 [2018-06-20 22:55:22,472 INFO ]: Without dead ends: 11 [2018-06-20 22:55:22,472 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-20 22:55:22,473 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-20 22:55:22,474 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-20 22:55:22,474 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-20 22:55:22,474 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 11 transitions. [2018-06-20 22:55:22,474 INFO ]: Start accepts. Automaton has 11 states and 11 transitions. Word has length 8 [2018-06-20 22:55:22,474 INFO ]: Finished accepts. word is rejected. [2018-06-20 22:55:22,474 INFO ]: Abstraction has 11 states and 11 transitions. [2018-06-20 22:55:22,474 INFO ]: Interpolant automaton has 5 states. [2018-06-20 22:55:22,474 INFO ]: Start isEmpty. Operand 11 states and 11 transitions. [2018-06-20 22:55:22,474 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-20 22:55:22,475 INFO ]: Found error trace [2018-06-20 22:55:22,475 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 22:55:22,475 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 22:55:22,475 INFO ]: Analyzing trace with hash 145098516, now seen corresponding path program 2 times [2018-06-20 22:55:22,475 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 22:55:22,475 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 22:55:22,476 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 22:55:22,476 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-20 22:55:22,476 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 22:55:22,555 INFO ]: Conjunction of SSA is unsat [2018-06-20 22:55:22,750 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 22:55:22,751 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 22:55:22,751 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-20 22:55:22,765 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-20 22:55:22,837 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-20 22:55:22,837 INFO ]: Conjunction of SSA is unsat [2018-06-20 22:55:22,840 INFO ]: Computing forward predicates... [2018-06-20 22:55:23,723 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 22:55:23,753 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-20 22:55:23,753 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2018-06-20 22:55:23,753 INFO ]: Interpolant automaton has 7 states [2018-06-20 22:55:23,753 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-20 22:55:23,753 INFO ]: CoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2018-06-20 22:55:23,754 INFO ]: Start difference. First operand 11 states and 11 transitions. Second operand 7 states. [2018-06-20 22:55:24,090 WARN ]: Spent 326.00 ms on a formula simplification. DAG size of input: 10 DAG size of output: 9 [2018-06-20 22:55:24,384 WARN ]: Spent 164.00 ms on a formula simplification. DAG size of input: 9 DAG size of output: 5 [2018-06-20 22:55:24,385 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 22:55:24,385 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-20 22:55:24,385 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-20 22:55:24,385 INFO ]: Start accepts. Automaton has 7 states. Word has length 10 [2018-06-20 22:55:24,386 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 22:55:24,386 INFO ]: With dead ends: 12 [2018-06-20 22:55:24,386 INFO ]: Without dead ends: 12 [2018-06-20 22:55:24,386 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 8 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=39, Invalid=51, Unknown=0, NotChecked=0, Total=90 [2018-06-20 22:55:24,386 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-20 22:55:24,388 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-20 22:55:24,388 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-20 22:55:24,388 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-20 22:55:24,388 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 10 [2018-06-20 22:55:24,388 INFO ]: Finished accepts. word is rejected. [2018-06-20 22:55:24,388 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-20 22:55:24,388 INFO ]: Interpolant automaton has 7 states. [2018-06-20 22:55:24,388 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-20 22:55:24,389 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-20 22:55:24,389 INFO ]: Found error trace [2018-06-20 22:55:24,389 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 22:55:24,389 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 22:55:24,389 INFO ]: Analyzing trace with hash 201204236, now seen corresponding path program 3 times [2018-06-20 22:55:24,389 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 22:55:24,389 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 22:55:24,390 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 22:55:24,390 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-20 22:55:24,390 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 22:55:24,426 INFO ]: Conjunction of SSA is unsat [2018-06-20 22:55:24,764 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 22:55:24,764 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 22:55:24,764 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-20 22:55:24,773 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-20 22:55:24,829 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-20 22:55:24,829 INFO ]: Conjunction of SSA is unsat [2018-06-20 22:55:24,832 INFO ]: Computing forward predicates... [2018-06-20 22:55:26,662 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 22:55:26,693 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-20 22:55:26,693 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 9 [2018-06-20 22:55:26,694 INFO ]: Interpolant automaton has 9 states [2018-06-20 22:55:26,694 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-20 22:55:26,694 INFO ]: CoverageRelationStatistics Valid=24, Invalid=48, Unknown=0, NotChecked=0, Total=72 [2018-06-20 22:55:26,694 INFO ]: Start difference. First operand 12 states and 12 transitions. Second operand 9 states. [2018-06-20 22:55:26,906 WARN ]: Spent 123.00 ms on a formula simplification that was a NOOP. DAG size: 7 [2018-06-20 22:55:27,803 WARN ]: Spent 794.00 ms on a formula simplification. DAG size of input: 13 DAG size of output: 11 [2018-06-20 22:55:27,892 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 22:55:27,892 INFO ]: Finished difference Result 13 states and 13 transitions. [2018-06-20 22:55:27,892 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-20 22:55:27,892 INFO ]: Start accepts. Automaton has 9 states. Word has length 11 [2018-06-20 22:55:27,892 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 22:55:27,892 INFO ]: With dead ends: 13 [2018-06-20 22:55:27,892 INFO ]: Without dead ends: 13 [2018-06-20 22:55:27,893 INFO ]: 0 DeclaredPredicates, 22 GetRequests, 7 SyntacticMatches, 3 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=69, Invalid=113, Unknown=0, NotChecked=0, Total=182 [2018-06-20 22:55:27,893 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-20 22:55:27,894 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-20 22:55:27,894 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-20 22:55:27,894 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 13 transitions. [2018-06-20 22:55:27,895 INFO ]: Start accepts. Automaton has 13 states and 13 transitions. Word has length 11 [2018-06-20 22:55:27,895 INFO ]: Finished accepts. word is rejected. [2018-06-20 22:55:27,895 INFO ]: Abstraction has 13 states and 13 transitions. [2018-06-20 22:55:27,895 INFO ]: Interpolant automaton has 9 states. [2018-06-20 22:55:27,895 INFO ]: Start isEmpty. Operand 13 states and 13 transitions. [2018-06-20 22:55:27,895 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-20 22:55:27,895 INFO ]: Found error trace [2018-06-20 22:55:27,895 INFO ]: trace histogram [5, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 22:55:27,895 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 22:55:27,895 INFO ]: Analyzing trace with hash 1940481556, now seen corresponding path program 4 times [2018-06-20 22:55:27,895 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 22:55:27,895 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 22:55:27,896 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 22:55:27,896 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-20 22:55:27,896 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 22:55:27,934 INFO ]: Conjunction of SSA is unsat [2018-06-20 22:55:28,214 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 22:55:28,214 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 22:55:28,214 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-20 22:55:28,220 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-20 22:55:28,263 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-20 22:55:28,264 INFO ]: Conjunction of SSA is unsat [2018-06-20 22:55:28,268 INFO ]: Computing forward predicates... [2018-06-20 22:55:29,118 WARN ]: expecting exponential blowup for input size 11 [2018-06-20 22:55:33,664 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 22:55:33,697 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-20 22:55:33,697 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 12 [2018-06-20 22:55:33,697 INFO ]: Interpolant automaton has 12 states [2018-06-20 22:55:33,697 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-20 22:55:33,697 INFO ]: CoverageRelationStatistics Valid=45, Invalid=87, Unknown=0, NotChecked=0, Total=132 [2018-06-20 22:55:33,697 INFO ]: Start difference. First operand 13 states and 13 transitions. Second operand 12 states. [2018-06-20 22:55:33,837 WARN ]: Spent 111.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 34 [2018-06-20 22:55:34,214 WARN ]: Spent 190.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 31 [2018-06-20 22:55:34,215 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 22:55:34,215 INFO ]: Finished difference Result 15 states and 15 transitions. [2018-06-20 22:55:34,215 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-20 22:55:34,215 INFO ]: Start accepts. Automaton has 12 states. Word has length 12 [2018-06-20 22:55:34,215 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 22:55:34,216 INFO ]: With dead ends: 15 [2018-06-20 22:55:34,216 INFO ]: Without dead ends: 15 [2018-06-20 22:55:34,217 INFO ]: 0 DeclaredPredicates, 24 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 53 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=102, Invalid=170, Unknown=0, NotChecked=0, Total=272 [2018-06-20 22:55:34,217 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-20 22:55:34,218 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-20 22:55:34,218 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-20 22:55:34,219 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 15 transitions. [2018-06-20 22:55:34,219 INFO ]: Start accepts. Automaton has 15 states and 15 transitions. Word has length 12 [2018-06-20 22:55:34,219 INFO ]: Finished accepts. word is rejected. [2018-06-20 22:55:34,219 INFO ]: Abstraction has 15 states and 15 transitions. [2018-06-20 22:55:34,219 INFO ]: Interpolant automaton has 12 states. [2018-06-20 22:55:34,219 INFO ]: Start isEmpty. Operand 15 states and 15 transitions. [2018-06-20 22:55:34,219 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-20 22:55:34,219 INFO ]: Found error trace [2018-06-20 22:55:34,219 INFO ]: trace histogram [7, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 22:55:34,220 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 22:55:34,220 INFO ]: Analyzing trace with hash 726730004, now seen corresponding path program 5 times [2018-06-20 22:55:34,220 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 22:55:34,220 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 22:55:34,220 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 22:55:34,221 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-20 22:55:34,221 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 22:55:34,275 INFO ]: Conjunction of SSA is unsat [2018-06-20 22:55:34,926 WARN ]: Spent 250.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 20 [2018-06-20 22:55:34,984 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 22:55:34,985 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 22:55:34,985 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-20 22:55:34,991 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-20 22:55:35,034 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2018-06-20 22:55:35,034 INFO ]: Conjunction of SSA is unsat [2018-06-20 22:55:35,038 INFO ]: Computing forward predicates... [2018-06-20 22:55:45,659 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 22:55:45,691 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-20 22:55:45,691 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 14 [2018-06-20 22:55:45,692 INFO ]: Interpolant automaton has 14 states [2018-06-20 22:55:45,692 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-20 22:55:45,692 INFO ]: CoverageRelationStatistics Valid=52, Invalid=130, Unknown=0, NotChecked=0, Total=182 [2018-06-20 22:55:45,692 INFO ]: Start difference. First operand 15 states and 15 transitions. Second operand 14 states. [2018-06-20 22:55:45,989 WARN ]: Spent 190.00 ms on a formula simplification. DAG size of input: 41 DAG size of output: 29 [2018-06-20 22:55:46,308 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 22:55:46,308 INFO ]: Finished difference Result 16 states and 16 transitions. [2018-06-20 22:55:46,308 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-20 22:55:46,308 INFO ]: Start accepts. Automaton has 14 states. Word has length 14 [2018-06-20 22:55:46,308 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 22:55:46,309 INFO ]: With dead ends: 16 [2018-06-20 22:55:46,309 INFO ]: Without dead ends: 16 [2018-06-20 22:55:46,309 INFO ]: 0 DeclaredPredicates, 31 GetRequests, 7 SyntacticMatches, 4 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 94 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=161, Invalid=301, Unknown=0, NotChecked=0, Total=462 [2018-06-20 22:55:46,309 INFO ]: Start minimizeSevpa. Operand 16 states. [2018-06-20 22:55:46,310 INFO ]: Finished minimizeSevpa. Reduced states from 16 to 16. [2018-06-20 22:55:46,310 INFO ]: Start removeUnreachable. Operand 16 states. [2018-06-20 22:55:46,311 INFO ]: Finished removeUnreachable. Reduced from 16 states to 16 states and 16 transitions. [2018-06-20 22:55:46,311 INFO ]: Start accepts. Automaton has 16 states and 16 transitions. Word has length 14 [2018-06-20 22:55:46,311 INFO ]: Finished accepts. word is rejected. [2018-06-20 22:55:46,311 INFO ]: Abstraction has 16 states and 16 transitions. [2018-06-20 22:55:46,311 INFO ]: Interpolant automaton has 14 states. [2018-06-20 22:55:46,311 INFO ]: Start isEmpty. Operand 16 states and 16 transitions. [2018-06-20 22:55:46,311 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-20 22:55:46,311 INFO ]: Found error trace [2018-06-20 22:55:46,311 INFO ]: trace histogram [8, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 22:55:46,311 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 22:55:46,312 INFO ]: Analyzing trace with hash 1051911180, now seen corresponding path program 6 times [2018-06-20 22:55:46,312 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 22:55:46,312 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 22:55:46,312 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 22:55:46,312 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-20 22:55:46,312 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 22:55:46,373 INFO ]: Conjunction of SSA is unsat [2018-06-20 22:55:47,688 WARN ]: Spent 1.05 s on a formula simplification. DAG size of input: 17 DAG size of output: 15 [2018-06-20 22:55:47,807 INFO ]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 22:55:47,807 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 22:55:47,807 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-20 22:55:47,827 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-20 22:55:47,920 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2018-06-20 22:55:47,920 INFO ]: Conjunction of SSA is unsat [2018-06-20 22:55:47,924 INFO ]: Computing forward predicates... [2018-06-20 22:55:51,775 WARN ]: expecting exponential blowup for input size 6 [2018-06-20 22:55:51,784 WARN ]: expecting exponential blowup for input size 8 [2018-06-20 22:55:54,731 WARN ]: expecting exponential blowup for input size 6 [2018-06-20 22:55:54,759 WARN ]: expecting exponential blowup for input size 6 [2018-06-20 22:55:54,768 WARN ]: expecting exponential blowup for input size 6 [2018-06-20 22:55:54,878 WARN ]: expecting exponential blowup for input size 6 [2018-06-20 22:56:17,248 INFO ]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 22:56:17,267 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-20 22:56:17,268 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 15 [2018-06-20 22:56:17,268 INFO ]: Interpolant automaton has 15 states [2018-06-20 22:56:17,268 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-20 22:56:17,268 INFO ]: CoverageRelationStatistics Valid=62, Invalid=148, Unknown=0, NotChecked=0, Total=210 [2018-06-20 22:56:17,268 INFO ]: Start difference. First operand 16 states and 16 transitions. Second operand 15 states. [2018-06-20 22:56:17,663 WARN ]: Spent 149.00 ms on a formula simplification. DAG size of input: 34 DAG size of output: 31 [2018-06-20 22:56:17,891 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-20 22:56:17,891 INFO ]: Finished difference Result 17 states and 17 transitions. [2018-06-20 22:56:17,891 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-20 22:56:17,891 INFO ]: Start accepts. Automaton has 15 states. Word has length 15 [2018-06-20 22:56:17,891 INFO ]: Finished accepts. some prefix is accepted. [2018-06-20 22:56:17,892 INFO ]: With dead ends: 17 [2018-06-20 22:56:17,892 INFO ]: Without dead ends: 17 [2018-06-20 22:56:17,892 INFO ]: 0 DeclaredPredicates, 33 GetRequests, 7 SyntacticMatches, 5 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 121 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=177, Invalid=329, Unknown=0, NotChecked=0, Total=506 [2018-06-20 22:56:17,892 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-20 22:56:17,894 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-20 22:56:17,894 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-20 22:56:17,894 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 17 transitions. [2018-06-20 22:56:17,895 INFO ]: Start accepts. Automaton has 17 states and 17 transitions. Word has length 15 [2018-06-20 22:56:17,895 INFO ]: Finished accepts. word is rejected. [2018-06-20 22:56:17,895 INFO ]: Abstraction has 17 states and 17 transitions. [2018-06-20 22:56:17,895 INFO ]: Interpolant automaton has 15 states. [2018-06-20 22:56:17,895 INFO ]: Start isEmpty. Operand 17 states and 17 transitions. [2018-06-20 22:56:17,895 INFO ]: Finished isEmpty. Found accepting run of length 17 [2018-06-20 22:56:17,895 INFO ]: Found error trace [2018-06-20 22:56:17,895 INFO ]: trace histogram [9, 1, 1, 1, 1, 1, 1, 1] [2018-06-20 22:56:17,895 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-20 22:56:17,895 INFO ]: Analyzing trace with hash -1752374252, now seen corresponding path program 7 times [2018-06-20 22:56:17,895 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-20 22:56:17,895 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-20 22:56:17,896 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 22:56:17,897 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-20 22:56:17,897 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-20 22:56:18,026 INFO ]: Conjunction of SSA is unsat [2018-06-20 22:56:18,333 WARN ]: Spent 149.00 ms on a formula simplification. DAG size of input: 14 DAG size of output: 4 [2018-06-20 22:56:18,699 WARN ]: Spent 316.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 19 [2018-06-20 22:56:19,074 INFO ]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-20 22:56:19,074 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-20 22:56:19,074 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-20 22:56:19,086 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-20 22:56:19,143 INFO ]: Conjunction of SSA is unsat [2018-06-20 22:56:19,147 INFO ]: Computing forward predicates... [2018-06-20 22:56:19,785 WARN ]: expecting exponential blowup for input size 6 [2018-06-20 22:56:19,824 WARN ]: expecting exponential blowup for input size 8 [2018-06-20 22:56:19,843 WARN ]: expecting exponential blowup for input size 6 [2018-06-20 22:56:23,801 WARN ]: expecting exponential blowup for input size 6 Received shutdown request... [2018-06-20 22:56:27,231 INFO ]: Timeout while computing interpolants [2018-06-20 22:56:27,432 WARN ]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-20 22:56:27,432 WARN ]: Verification canceled [2018-06-20 22:56:27,435 WARN ]: Timeout [2018-06-20 22:56:27,436 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.06 10:56:27 BoogieIcfgContainer [2018-06-20 22:56:27,436 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-20 22:56:27,436 INFO ]: Toolchain (without parser) took 66349.81 ms. Allocated memory was 305.7 MB in the beginning and 2.8 GB in the end (delta: 2.5 GB). Free memory was 259.0 MB in the beginning and 223.8 MB in the end (delta: 35.2 MB). Peak memory consumption was 2.6 GB. Max. memory is 7.1 GB. [2018-06-20 22:56:27,437 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 305.7 MB. Free memory is still 269.1 MB. There was no memory consumed. Max. memory is 7.1 GB. [2018-06-20 22:56:27,437 INFO ]: ChcToBoogie took 57.40 ms. Allocated memory is still 305.7 MB. Free memory was 259.0 MB in the beginning and 257.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 7.1 GB. [2018-06-20 22:56:27,438 INFO ]: Boogie Preprocessor took 45.43 ms. Allocated memory is still 305.7 MB. Free memory was 257.1 MB in the beginning and 255.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 7.1 GB. [2018-06-20 22:56:27,438 INFO ]: RCFGBuilder took 238.19 ms. Allocated memory is still 305.7 MB. Free memory was 255.1 MB in the beginning and 247.0 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 7.1 GB. [2018-06-20 22:56:27,439 INFO ]: TraceAbstraction took 65992.28 ms. Allocated memory was 305.7 MB in the beginning and 2.8 GB in the end (delta: 2.5 GB). Free memory was 246.1 MB in the beginning and 223.8 MB in the end (delta: 22.2 MB). Peak memory consumption was 2.6 GB. Max. memory is 7.1 GB. [2018-06-20 22:56:27,443 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.08 ms. Allocated memory is still 305.7 MB. Free memory is still 269.1 MB. There was no memory consumed. Max. memory is 7.1 GB. * ChcToBoogie took 57.40 ms. Allocated memory is still 305.7 MB. Free memory was 259.0 MB in the beginning and 257.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 7.1 GB. * Boogie Preprocessor took 45.43 ms. Allocated memory is still 305.7 MB. Free memory was 257.1 MB in the beginning and 255.1 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 7.1 GB. * RCFGBuilder took 238.19 ms. Allocated memory is still 305.7 MB. Free memory was 255.1 MB in the beginning and 247.0 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 7.1 GB. * TraceAbstraction took 65992.28 ms. Allocated memory was 305.7 MB in the beginning and 2.8 GB in the end (delta: 2.5 GB). Free memory was 246.1 MB in the beginning and 223.8 MB in the end (delta: 22.2 MB). Peak memory consumption was 2.6 GB. Max. memory is 7.1 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 17 with TraceHistMax 9, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantifier-free) to 14 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 65.9s OverallTime, 8 OverallIterations, 9 TraceHistogramMax, 3.7s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 49 SDtfs, 25 SDslu, 165 SDs, 0 SdLazy, 69 SolverSat, 55 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 143 GetRequests, 45 SyntacticMatches, 17 SemanticMatches, 81 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 320 ImplicationChecksByTransitivity, 7.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=17occurred in iteration=7, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 7 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 51.5s InterpolantComputationTime, 147 NumberOfCodeBlocks, 147 NumberOfCodeBlocksAsserted, 24 NumberOfCheckSat, 134 ConstructedInterpolants, 0 QuantifiedInterpolants, 11290 SizeOfPredicates, 24 NumberOfNonLiveVariables, 1042 ConjunctsInSsa, 309 ConjunctsInUnsatCore, 13 InterpolantComputations, 1 PerfectInterpolantSequences, 0/192 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/chc-lia-0061.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-20_22-56-27-454.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/chc-lia-0061.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-20_22-56-27-454.csv Completed graceful shutdown